Sitemap

Implement Stack using Queue

Naive to Optimised approaches to implement Stack using Queue.

--

Press enter or click to view image in full size
Photo by Kimberly Farmer on Unsplash

Problem Statement:

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, pop and peek).

Get Everus Lainus’s stories in your inbox

Join Medium for free to get updates from this writer.

Implement the MyStack class:

  • void push(int x) Pushes element x to the top of the stack.
  • int pop() Removes the element on the top of the stack and returns it.
  • int top() Returns the element on the top of the stack.

Implement Stack using Queues

Approach:

In the push() method, we can have two queues — queue1 and queue2. To push an element to stack, we add it to the empty queue2 .Then remove all the elements of queue1 and add it to queue2. Swap the two queues. This way the elements in the queue1 are arranged in an order such that the adding and removing elements from queue1 acts as adding and removing elements from stack.

If the element to push to stack in order are [1, 2, 3, 4, 5]

- add 1 to q2: so q2 = [1]
- swap q1 and q2: so q2 = [1] and q1=[]

- add 2 to q2:q2 = [2]
- add elts of q1 to q2.
- swap q1 and q2: so q1=[2, 1]

- add 3 to q2:q2 = [3]
- add elts of q1 to q2.
- swap q1 and q2: so q1=[3, 2, 1]

- add 4 to q2:q2 = [4]
- add elts of q1 to q2.
- swap q1 and q2: so q1=[4, 3, 2, 1]

- add 5 to q2:q2 = [5]
- add elts of q1 to q2.
- swap q1 and q2: so q1=[5, 4, 3, 2, 1]

Time complexity of Push() operation is O(n), of pop() and peek() is O(1). Space Complexity is O(n).

  Queue<Integer> queue1 = new LinkedList<>();
Queue<Integer> queue2 = new LinkedList<>();

Queue<Integer> temp = new LinkedList<>();

public void push(int data){

queue2.add(data);
while(!queue1.isEmpty()){
queue2.add(queue1.remove());
}

temp = queue1;
queue1=queue2;
queue2 = temp;
}

public void pop(){
queue1.remove();
}

public int top(){
return queue1.peek();
}

In the above approach we use two queues, we can use a single approach to simulate the same process. Find the size of the queue, add the new element to the queue, remove all the element in the queue till the size previously calculated and add it to that queue.

Time complexity of Push() operation is O(n) and pop() and peek() is O(1). Space Complexity is O(n).

  Queue<Integer> queue = new LinkedList<>();

public void push(int data){
int n = queue.size();

queue.add(data);

for(int i=0; i<n; i++){
queue.add(queue1.remove);
}
}

public void pop(){
queue.remove();
}

public int top(){
return queue.peek();
}

For any queries and suggestions please leave a reply.

--

--