Stack and Queue Fundamentals

A stack operates on a last-in-first-out (LIFO) principle, whereas a queue follows a first-in-first-out (FIFO) approach.

Both stack and queue are fundamental data structures available in the Standard Template Library (STL).

There are three widely recognized implementations of STL:

1. HP STL: The initial implementation of C++ STL, open-sourced and serves as a reference for other versions.
2. P.J. Plauger STL: Developed by P.J. Plauger, used by Visual C++ compiler, not open-source.
3. SGI STL: Created by Silicon Graphics, adopted by GCC compiler on Linux systems, fully open-source and highly readable.

In SGI STL, stacks and queues are implemented as container adaptors.

Stacks do not support iterators, unlike containers, which makes them adaptors rather than containers themselves.

Stacks can utilize various underlying containers like vector, deque, or list. By default, deque is used because it allows one end to be sealed off to simulate stack behavior.

To specify a different container type, such as vector or list, initialization syntax is as follows:

std::stack<int, std::vector<int>> third;  // Stack using vector as base container

Similarly, for queues:

std::queue<int, std::list<int>> third;  // Queue using list as base container

Implementing a Queue Using Two Stacks

The core idea involves using two stacks to reverse the order of elements sothat popping mimics queue behavior.

#include <stack>

class MyQueue {
private:
    std::stack<int> input;
    std::stack<int> output;

public:
    MyQueue() {}

    void push(int x) {
        input.push(x);
    }

    int pop() {
        if (output.empty()) {
            while (!input.empty()) {
                output.push(input.top());
                input.pop();
            }
        }
        int val = output.top();
        output.pop();
        return val;
    }

    int peek() {
        int res = this->pop();
        output.push(res);
        return res;
    }

    bool empty() {
        return input.empty() && output.empty();
    }
};

Key points:

1. Elements are added to the input stack.
2. When removing an element, if the output stack is empty, all elements from the input stack are moved to the output stack.
3. The peek() function reuses pop() logic and restores the element back into the output stack.

Implementing a Stack Using One Queue

The concept uses a single queue to simulate LIFO behavior by rotating elements during the pop operation.

#include <queue>

class MyStack {
private:
    std::queue<int> q;

public:
    MyStack() {}

    void push(int x) {
        q.push(x);
    }

    int pop() {
        int size = q.size();
        --size;
        while (size--) {
            q.push(q.front());
            q.pop();
        }
        int val = q.front();
        q.pop();
        return val;
    }

    int top() {
        return q.back();
    }

    bool empty() {
        return q.empty();
    }
};

In this approach:

1. New elements are pushed to the queue.
2. During pop, all but the last element are rotated to the back of the queue.
3. The final element is removed and returned.
4. The top() function simply returns the rear element of the queue.