## Similar Problems

Similar Problems not available

# Implement Queue Using Stacks - Leetcode Solution

LeetCode: Implement Queue Using Stacks Leetcode Solution

Difficulty: Easy

## Implement Queue using Stacks Link

Implement the following operations of a queue using stacks.

- push(x) — Push element x to the back of queue.
- pop() — Removes the element from in front of queue.
- peek() — Get the front element.
- empty() — Return whether the queue is empty.

#### Example:

MyQueue queue = new MyQueue();

queue.push(3);

queue.push(4);

queue.peek(); // returns 3

queue.pop(); // returns 3

queue.empty(); // returns false

**Notes:**

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

Problem Statement:

Implement the following operations of a queue using stacks.

- push(x) -- Push element x to the back of queue.
- pop() -- Removes the element from in front of queue.
- peek() -- Get the front element.
- empty() -- Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);

queue.push(2);

queue.peek(); // returns 1

queue.pop(); // returns 1

queue.empty(); // returns false

Solution:

We can use two stacks to implement a queue. We will call them "input" and "output". The idea is to push the elements into the "input" stack while the "output" stack is empty. When we need to perform an operation such as pop or peek, we will move the elements from the "input" stack to the "output" stack so that the first element that was pushed into the "input" stack will be at the top of the "output" stack, which will be the first element to be popped or peeked.

The following is the implementation of the MyQueue class:

class MyQueue { Stack<Integer> input; Stack<Integer> output;

```
/** Initialize your data structure here. */
public MyQueue() {
input = new Stack<>();
output = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
input.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
peek();
return output.pop();
}
/** Get the front element. */
public int peek() {
if (output.isEmpty()) {
while (!input.isEmpty()) {
output.push(input.pop());
}
}
return output.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return input.isEmpty() && output.isEmpty();
}
```

}

Explanation:

- In the constructor, we initialize the "input" and "output" stacks.
- The push operation is simple. We just need to push the element into the "input" stack.
- The pop operation needs the first element of the queue to be removed and returned. To do this, we first call the peek operation to move the elements from the "input" stack to the "output" stack. Then, we pop the top element from the "output" stack and return it.
- The peek operation is similar to the pop operation. We call this operation to move the elements from the "input" stack to the "output" stack, and then return the top element from the "output" stack.
- The empty operation checks if both "input" and "output" stacks are empty. If they are, the queue is considered empty.

The time complexity for push, pop, peek and empty operations is O(1). The space complexity is O(n), where n is the number of elements in the queue.

## Implement Queue Using Stacks Solution Code

`1`