C++: Implement Queue using Stacks

Thought Process

To implement a queue using stacks, we use two stacks: st1 and st2. The 'push' operation directly adds elements to st1. For 'pop' and 'peek', we transfer all elements from st1 to st2 to reverse their order, allowing us to access the front of the queue. After performing the operation, we transfer elements back to st1 to maintain the correct order for future operations. The 'empty' operation simply checks if st1 is empty. 

class MyQueue {
public:

    stack<int> st1, st2;
    MyQueue() {
        
    }
    
    void push(int x) {
        st1.push(x);
    }
    
    int pop() {
        while(!st1.empty()){
            st2.push(st1.top());
            st1.pop();
        }
        int ans = st2.top();
        st2.pop();

        while(!st2.empty()){
            st1.push(st2.top());
            st2.pop();
        }
        return ans;
    }
    
    int peek() {
        while(!st1.empty()){
            st2.push(st1.top());
            st1.pop();
        }
        int ans = st2.top();

        while(!st2.empty()){
            st1.push(st2.top());
            st2.pop();
        }
        return ans;
    }
    
    bool empty() {
        if(st1.empty())
            return true;
        else
            return false;
    }
};
    
    /**
     * Your MyQueue object will be instantiated and called as such:
     * MyQueue* obj = new MyQueue();
     * obj->push(x);
     * int param_2 = obj->pop();
     * int param_3 = obj->peek();
     * bool param_4 = obj->empty();
     */

Code Complexity

Time Complexity: O(n)

The pop and peek operations involve transferring elements between two stacks, making them linear in time complexity.

Space Complexity: O(n)

The two stacks together store up to 'n' elements, where 'n' is the number of elements in the queue.

Code copied!