hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Implement Queue using Stacks


  • Approach:

    1. Initiate two stack base and reverse.

      • When a new push occurs we will insert that element into base.

      • The reverse will contain the elements of base in reversed order. Because we will use this to get the top and popped element. As per the operation of queue, we need to do FIFO operation. So, the first element that will be entered in the stack will remove first. As the stack follows the LIFO operation, to get the elements inserted lately, we need to transfer them to another stack reverse.

    2. While calling the push(x) operation push x into the stack base.

    3. While calling the peek() and pop(), we have to check if the reverse contains any elements. If contains then we need to return the top element of it and pop it if pop() is called.

    4. If not then we need to insert the elements of reverse into the base in reverse order. Now, the reverse has elements inside it. Return the top element of it and pop it if pop() is called.

    5. If empty() is called, then check if both base and reverse are empty or not.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(N)


Code [C++]

class MyQueue {

public:


stack<int>base, reverse;

MyQueue() {

}

void push(int x) {

base.push(x);

}


void insert_on_reverse(){

while(!base.empty()){

reverse.push(base.top());

base.pop();

}

}

int pop() {

if(reverse.empty()){

insert_on_reverse();

}

int top = reverse.top();

reverse.pop();

return top;

}

int peek() {

if(reverse.empty()){

insert_on_reverse();

}

return reverse.top();

}

bool empty() {

return (base.empty() && reverse.empty());

}

};


/**

* 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();

*/