This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Implement the following operations of a stack using queues.

- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- empty() -- Return whether the stack is empty.

- You must use
*only*standard operations of a queue -- which means only`push to back`

,`peek/pop from front`

,`size`

, and`is empty`

operations are valid. - Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
- You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

**Credits:**

Special thanks to @jianchao.li.fighter for adding this problem and all test cases.

b'

\n## Summary

\n## Solution

\n

\n#### Approach #1 (Two Queues, push - , pop )

\n\n\n

\n#### Approach #2 (Two Queues, push - , pop )

\n\n\n\n\n

\n#### Approach #3 (One Queue, push - , pop )

\n\n\n\n\n

'
\n\n

\nThis article is for beginners. It introduces the following ideas:\nStack, Queue.

\n\n

**Intuition**

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

.\nIn 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**

private Queue<Integer> q1 = new LinkedList<>();\nprivate Queue<Integer> q2 = new LinkedList<>();\nprivate int top;\n\n// Push element x onto stack.\npublic void push(int x) {\n q1.add(x);\n top = x;\n}\n

**Complexity Analysis**

- \n
- \n
Time complexity : . Queue is implemented as linked list and

\n`add`

operation has time complexity. \n - \n
Space complexity : \n

\n \n

**Pop**

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

.\nBecause 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**

// Removes the element on top of the stack.\npublic void pop() {\n while (q1.size() > 1) {\n top = q1.remove();\n q2.add(top);\n }\n q1.remove();\n Queue<Integer> temp = q1;\n q1 = q2;\n q2 = temp;\n}\n

**Complexity Analysis**

- \n
- Time complexity : . The algorithm dequeues n elements from
`q1`

and enqueues elements to`q2`

, where is the stack size. This gives operations. \n - Space complexity : . \n

\n

**Algorithm**

**Push**

The algorithm inserts each new element to queue `q2`

and keep it as the `top`

element. In case queue `q1`

is not empty (there are elements in the stack), we remove all elements from `q1`

and add them to `q2`

. In this way the new inserted element (`top`

element in the stack) will be always positioned at the front of `q2`

. We swap `q1`

with `q2`

to avoid copying all elements from `q2`

to `q1`

.

*Figure 3. Push an element in stack*

**Java**

public void push(int x) {\n q2.add(x);\n top = x;\n while (!q1.isEmpty()) { \n q2.add(q1.remove());\n }\n Queue<Integer> temp = q1;\n q1 = q2;\n q2 = temp;\n}\n

**Complexity Analysis**

- \n
- \n
Time complexity : . The algorithm removes n elements from

\n`q1`

and inserts elements to`q2`

, where n is the stack size. This gives operations. The operations`add`

and`remove`

in linked lists has complexity. \n - \n
Space complexity : .

\n \n

**Pop**

The algorithm dequeues an element from queue `q1`

and keeps front element of `q1`

as `top`

.

*Figure 4. Pop an element from stack*

**Java**

// Removes the element on top of the stack.\npublic void pop() {\n q1.remove();\n if (!q1.isEmpty()) {\n top = q1.peek();\n }\n}\n

**Complexity Analysis**

- \n
- Time complexity : . \n
- Space complexity : . \n

In both approaches `empty`

and `top`

operations have the same implementation.

**Empty**

Queue `q1`

always contains all stack elements, so the algorithm checks `q1`

size to return if the stack is empty.

// Return whether the stack is empty.\npublic boolean empty() {\n return q1.isEmpty();\n}\n

Time complexity : .

\nSpace complexity : .

\n**Top**

The `top`

element is kept in constant memory and is modified each time when we push or pop an element.

// Get the top element.\npublic int top() {\n return top;\n}\n

Time complexity : .\n The `top`

element has been calculated in advance and only returned in `top`

operation.

Space complexity : .

\n\n

The mentioned above two approaches have one weakness, they use two queues. This could be optimized as we use only one queue, instead of two.

\n**Algorithm**

**Push**

When we push an element into a queue, it will be stored at back of the queue due to queue\'s properties.\nBut we need to implement a stack, where last inserted element should be in the front of the queue, not at the back. To achieve this we can invert the order of queue elements when pushing a new element.

\n\n*Figure 5. Push an element in stack*

**Java**

private LinkedList<Integer> q1 = new LinkedList<>();\n\n// Push element x onto stack.\npublic void push(int x) {\n q1.add(x);\n int sz = q1.size();\n while (sz > 1) {\n q1.add(q1.remove());\n sz--;\n }\n}\n

**Complexity Analysis**

- \n
- \n
Time complexity : . The algorithm removes n elements and inserts elements to

\n`q1`

, where n is the stack size. This gives operations. The operations`add`

and`remove`

in linked lists has complexity. \n - \n
Space complexity : .

\n \n

**Pop**

The last inserted element is always stored at the front of `q1`

and we can pop it for constant time.

**Java**

// Removes the element on top of the stack.\npublic void pop() {\n q1.remove();\n}\n

**Complexity Analysis**

- \n
- Time complexity : . \n
- Space complexity : . \n

**Empty**

Queue `q1`

contains all stack elements, so the algorithm checks if `q1`

is empty.

// Return whether the stack is empty.\npublic boolean empty() {\n return q1.isEmpty();\n}\n

Time complexity : .

\nSpace complexity : .

\n**Top**

The `top`

element is always positioned at the front of `q1`

. Algorithm return it.

// Get the top element.\npublic int top() {\n return q1.peek();\n}\n

Time complexity : .

\nSpace complexity : .

\nAnalysis written by: @elmirap.

\n