# Implement queue using stack

In last post, we learned about stack data structure, in this post, we will discuss another data structure called queue. However, __problem at hand is to implement queue using stack.__ Implement following functions on queue using stack

1.

*push()*: inserts element at the back of queue.

2.

*pop()*: removes element from front of the queue.

3.

*peek()*: return element at front of the queue.

4.

*empty()*: returns true if there is no element in queue.

Keep in mind that you can only use standard stack operations : push(), pop(), peek() and empty()

Stack is data structure where the element which is entered at `top` is taken out from `top`. It’s called LIFO pattern. Oppose to that queue is a FIFO data structure, where elements are entered at the `rear` and taken out from `front`. So effectively, we have to implement a FIFO data structure using LIFO data structure.

## Implement queue using stack : Line of thoughts

To implement a FIFO using LIFO data structure, we need two stacks.

**Push()**

When element is inserted i.e `push()`

operation, new element has to be pushed down the stack at bottom, as this should be the last element to be popped. So, to push an element in queue, we will take out all existing elements from stack `s1` and put them into stack `s2`. Now, push the new element on to stack `s1`. At last, pop all elements from stack `s2` back to stack `s1`. Below picture shows what happens when you we push 3 to queue and what happens behind the scene using stacks.

Complexity of push operation with this method is `O(n)`

. If there are n elements already inserted into queue, inserting a new element will require n pops from s1, n pushes to s2, then n pops from s2 and then again pushes to s1.

**Pop()**

If we follow the push operation described above, pop operation would be nothing but to return top of `s1`, which is constant operation with complexity of `O(1)`

.

Peek and empty functions also run always on stack s1. For peek, return `s1.peek()`

and for empty return `s1.empty()`

### Queue with stack : Push O(n), pop O(1) implementation

package com.company; import java.util.Stack; /** * Created by sangar on 23.9.18. */ public class QueueWithStack { private Stack<Integer> s1; private Stack<Integer> s2; public QueueWithStack(){ s1 = new Stack<>(); s2 = new Stack<>(); } public void push(int x){ if(s1.empty()) s1.push(x); else{ while(!s1.empty()){ s2.push(s1.pop()); } s2.push(x); while(!s2.empty()){ s1.push(s2.pop()); } } } public int pop(){ if(s1.empty()) return -1; return s1.pop(); } public boolean isEmpty(){ return s1.empty(); } public int peek(){ return s1.peek(); } }

Test class for above implementation would be:

package test; import com.company.QueueWithStack; import org.junit.jupiter.api.Test; import static org.junit.jupiter.api.Assertions.assertEquals; /** * Created by sangar on 23.9.18. */ public class QueueWithStackTest { QueueWithStack tester = new QueueWithStack(); @Test public void queueTest() { tester.push(2); tester.push(3); tester.push(5); tester.push(1); assertEquals(2, tester.pop()); assertEquals(3, tester.pop()); assertEquals(5, tester.peek()); assertEquals(false, tester.isEmpty()); } }

Can we do better than `O(n)`

while pushing element in queue?

### Queue with stack : Push O(1), pop amortized complexity O(1) implementation

**Push()**

What if we push on `s1` as it is. What does it change? It make push operation on queue `O(1)`

.

**Pop()**

How does it impacts pop operation? If we pop all element from `s1` and push them onto `s2`, at the top of `s2` is actually the element we need. Also, due to this pop and push operation, `s2` now contains all the elements in correct pop order for queue.

So idea is to always push in `s1` as it is, however when popping out, check if `s2` is empty or not? If not, then pop from `s2` and return, if it is empty, pop all elements from `s1` and push them all on `s2` and return the top.

How does it impact the performance? Well, it is true that if there is not element in `s2`, we have pop and push on `s2`, which has complexity of `O(n)`

. HOwever, all subsequent pop operations are O(1), this is called amortized complexity of `O(1)`

.

**Empty()**

Queue to be empty, there should not any element in either `s1` or `s2`.

**Peek()**

If `s2` is empty, then pop from `s1` and push on to `s2` and then return peek of `s2`.

package com.company; import java.util.Stack; /** * Created by sangar on 23.9.18. */ public class QueueWithStackOptimized { private Stack<Integer> s1; private Stack<Integer> s2; private int front; public QueueWithStackOptimized(){ s1 = new Stack<>(); s2 = new Stack<>(); } public void push(int x){ if(s1.empty()) front = x; s1.push(x); } public int pop(){ if(!s2.empty()) return s2.pop(); if(!s1.empty()) return -1; while(!s1.empty()){ s2.push(s1.pop()); } return s2.pop(); } public boolean isEmpty(){ return s1.empty() && s2.empty(); } public int peek(){ if(!s2.empty()) return s2.peek(); return front; } }

Complexity of peek function is again amortized to `O(1)`

. Can you write test cases for implemented queue?

Reference : Leetcode

Please share if there is something wrong or missing. If you want to have personal coaching from our experienced coaches, please reach out to us at [email protected]