Understanding Stack and Queue Implementations

In C++, both stacks and queues are container adapters, typically built upon underlying containers like vector or deque. Their core concepts are Last-In-First-Out (LIFO) and First-In-First-Out (FIFO), respectively.

232. Implement Queue using Stacks

Design a FIFO queue using only two stacks. The implemented queue should support standard operatinos: push, pop, peek, and empty.

#include <stack>
using namespace std;

class QueueFromStacks {
private:
    stack<int> primaryStack;
    stack<int> auxiliaryStack;

    // Helper to move all elements from primary to auxiliary
    void transferElements() {
        while (!primaryStack.empty()) {
            auxiliaryStack.push(primaryStack.top());
            primaryStack.pop();
        }
    }

public:
    QueueFromStacks() {}

    // Push element x to the back of queue
    void push(int x) {
        // To maintain FIFO order, reverse the stack before adding new element
        transferElements();
        primaryStack.push(x);
        // Move elements back to maintain queue front at top
        while (!auxiliaryStack.empty()) {
            primaryStack.push(auxiliaryStack.top());
            auxiliaryStack.pop();
        }
    }

    // Removes the element from the front of queue and returns it
    int pop() {
        int frontElement = primaryStack.top();
        primaryStack.pop();
        return frontElement;
    }

    // Get the front element
    int peek() {
        return primaryStack.top();
    }

    // Return whether the queue is empty
    bool empty() {
        return primaryStack.empty();
    }
};

Notes:

• All operations (push, pop, peek, empty) must use only standard stack operations.
• You can assume all operations are valid (e.g., no pop or peek on an empty queue).

225. Implement Stack using Queues

Design a LIFO stack using queues. The stack should support standard operations: push, pop, top, and empty.

#include <queue>
using namespace std;

class StackFromQueues {
private:
    queue<int> dataQueue;

public:
    StackFromQueues() {}

    // Push element x onto stack
    void push(int x) {
        int currentSize = dataQueue.size();
        dataQueue.push(x);
        // Rotate the queue to make the new element at the front
        for (int i = 0; i < currentSize; ++i) {
            dataQueue.push(dataQueue.front());
            dataQueue.pop();
        }
    }

    // Removes the element on top of the stack and returns it
    int pop() {
        int topElement = dataQueue.front();
        dataQueue.pop();
        return topElement;
    }

    // Get the top element
    int top() {
        return dataQueue.front();
    }

    // Return whether the stack is empty
    bool empty() {
        return dataQueue.empty();
    }
};

Implementation Details:

• The push operation has O(n) time complexity as it requires rotating the queue to maintain the LIFO order.
• Only standard queue operations (push, pop, front, back, size, empty) are used.
• This implementation uses a single queue, satisfying the advanced requirement.