Implementing a Queue with Two Stacks

To simulate FIFO behavior using LIFO structures, maintain two stacks: inputStack for enqueue operations and outputStack for dequeue operations. When outputStack is empty during a pop or peek, transfer all elements from inputStack to outputStack to reverse their order.

class MyQueue {
    stack<int> inputStack, outputStack;

public:
    void push(int x) {
        inputStack.push(x);
    }

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

    int peek() {
        if (outputStack.empty()) {
            while (!inputStack.empty()) {
                outputStack.push(inputStack.top());
                inputStack.pop();
            }
        }
        return outputStack.top();
    }

    bool empty() {
        return inputStack.empty() && outputStack.empty();
    }
};

Implementing a Stack with Two Queues

Use two queues where one holds the main data (mainQ) and the other acts as temporary storage (tempQ). For pop/top operations, move all but the last element from mainQ to tempQ, then swap the queues.

class MyStack {
    queue<int> mainQ, tempQ;

public:
    void push(int x) {
        mainQ.push(x);
    }

    int pop() {
        while (mainQ.size() > 1) {
            tempQ.push(mainQ.front());
            mainQ.pop();
        }
        int val = mainQ.front();
        mainQ.pop();
        swap(mainQ, tempQ);
        return val;
    }

    int top() {
        while (mainQ.size() > 1) {
            tempQ.push(mainQ.front());
            mainQ.pop();
        }
        return mainQ.front();
    }

    bool empty() {
        return mainQ.empty() && tempQ.empty();
    }
};

Alternative: Single-Queue Implementation

Maitnain only one queue. After each push, rotate the queue by moving existing elements to the back, ensuring the newly added element becomes the front (top of the stack).

class MyStack {
    queue<int> q;

public:
    void push(int x) {
        int size = q.size();
        q.push(x);
        for (int i = 0; i < size; ++i) {
            q.push(q.front());
            q.pop();
        }
    }

    int pop() {
        int val = q.front();
        q.pop();
        return val;
    }

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

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