Stacks and Queues in C++

Stacks and queues are essential data structures in C++ used for managing data elements in a specific order. In this guide, we'll introduce you to stacks and queues, including explanations and sample code.

1. Stacks

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. In C++, you can use the std::stack container to work with stacks:

#include <iostream>
#include <stack>
int main() {
    std::stack<int> myStack;
    // Push elements onto the stack
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);
    // Pop elements from the stack
    while (!myStack.empty()) {
        std::cout << myStack.top() << ` `; // Print the top element
        myStack.pop(); // Remove the top element
    }
    return 0;
}
    

2. Queues

A queue is another linear data structure, but it follows the First-In-First-Out (FIFO) principle. In C++, you can use the std::queue container to work with queues:

#include <iostream>
#include <queue>
int main() {
    std::queue<int> myQueue;
    // Enqueue elements into the queue
    myQueue.push(1);
    myQueue.push(2);
    myQueue.push(3);
    // Dequeue elements from the queue
    while (!myQueue.empty()) {
        std::cout << myQueue.front() << ` `; // Print the front element
        myQueue.pop(); // Remove the front element
    }
    return 0;
}
    

3. Implementing Stacks and Queues

You can also implement stacks and queues using arrays or linked lists. For example, here's a simple implementation of a stack using a dynamic array:

#include <iostream>
#include <vector>
class Stack {
public:
    Stack() {}
    void push(int value) {
        elements.push_back(value);
    }
    void pop() {
        if (!empty()) {
            elements.pop_back();
        }
    }
    int top() {
        if (!empty()) {
            return elements.back();
        }
        return -1; // Handle empty stack
    }
    bool empty() {
        return elements.empty();
    }
private:
    std::vector<int> elements;
};
int main() {
    Stack myStack;
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);
    while (!myStack.empty()) {
        std::cout << myStack.top() << ` `;
        myStack.pop();
    }
    return 0;
}
    

4. Use Cases

Stacks are often used for tasks like tracking function calls in recursion, managing undo/redo functionality, and evaluating expressions. Queues are used for tasks like managing tasks in a print spooler, scheduling processes, and implementing breadth-first search algorithms.

Conclusion

Stacks and queues are fundamental data structures in C++ that serve various purposes. By understanding their principles and using C++ containers or implementing your own, you can efficiently manage and manipulate data in a stack-like or queue-like manner in your C++ programs.