**Intuition**

Stack is **LIFO** (last in – first out) data structure, in which elements are added and removed from the same end, called `top`

. In general stack is implemented using array or linked list, but in the current article we will review a different approach for implementing stack using queues. In contrast queue is **FIFO** (first in – first out) data structure, in which elements are added only from the one side – `rear`

and removed from the other – `front`

. In order to implement stack using queues, we need to maintain two queues `q1`

and `q2`

. Also we will keep top stack element in a constant memory.

**Algorithm**

**Push**

The new element is always added to the rear of queue `q1`

and it is kept as `top`

stack element

*Figure 1. Push an element in stack*

**Java**

1 2 3 4 5 6 7 8 9 |
private Queue<Integer> q1 = new LinkedList<>(); private Queue<Integer> q2 = new LinkedList<>(); private int top; // Push element x onto stack. public void push(int x) { q1.add(x); top = x; } |

**Complexity Analysis**

- Time complexity : $O(1)$. Queue is implemented as linked list and
`add`

operation has $O(1)$ time complexity.

- Space complexity : $O(1)$

**Pop** We need to remove the element from the top of the stack. This is the last inserted element in `q1`

. Because queue is FIFO (first in – first out) data structure, the last inserted element could be removed only after all elements, except it, have been removed. For this reason we need to maintain additional queue `q2`

, which will serve as a temporary storage to enqueue the removed elements from q1. The last inserted element in `q2`

is kept as top. Then the algorithm removes the last element in `q1`

. We swap `q1`

with `q2`

to avoid copying all elements from `q2`

to `q1`

.

*Figure 2. Pop an element from stack*

**Java**

1 2 3 4 5 6 7 8 9 10 11 |
// Removes the element on top of the stack. public void pop() { while (q1.size() > 1) { top = q1.remove(); q2.add(top); } q1.remove(); Queue<Integer> temp = q1; q1 = q2; q2 = temp; } |

**Complexity Analysis**

- Time complexity : $O(n)$. The algorithm dequeues n elements from
`q1`

and enqueues $n−1$ elements to`q2`

, where $n$ is the stack size. This gives $2n−1$ operations. - Space complexity : $O(1)$.