# 225. Implement stack with queue

Title Link: 225. Implement stack with queue (simple)

## Title Description

Please use only two queues to implement a last in first out (LIFO) stack, and support all four operations of the ordinary stack (push, top, pop and empty).

Implement MyStack class:

• void push(int x) pushes element X to the top of the stack.

• int pop() removes and returns the top of stack element.

• int top() returns the stack top element.

• boolean empty() returns true if the stack is empty; Otherwise, false is returned.

be careful:

• You can only use the basic operations of the queue -- that is, push to back, peek/pop from front, size and is empty.

• Your language may not support queues. You can use list or deque to simulate a queue, as long as it is a standard queue operation.

Example:

`Input:["MyStack", "push", "push", "top", "pop", "empty"][[], , , [], [], []]Output:[null, null, null, 2, 2, false]​Explanation:MyStack myStack = new MyStack();myStack.push(1);myStack.push(2);myStack.top(); //  Return 2myStack.pop(); //  Return 2myStack.empty(); //  Return False`

Tips:

• 1 <= x <= 9

• Call push, pop, top, and empty up to 100 times

• Ensure that the stack is not empty every time pop and top are called

## Problem solution

Idea: according to the meaning of the topic, use a common queue and a queue for backing up data (in fact, using a queue for this topic is enough).

Two queues are used: for push(), just push the elements into the normal queue one by one; For pop(), first pop up the first n-1 elements in the ordinary queue (assuming there are n elements in the ordinary queue) and push them into the backup queue, and then pop up the last element; For top(), just return the end of line element; For empty(), you only need to judge whether the normal queue is empty.

Using a queue: push(), top(), empty() is the same as "using two queues"; for pop(), first pop up the first n-1 elements in the queue (assuming there are n elements in the queue) in order, push them from the end of the queue, and then pop up the last element.

Code (C + +)

```//Use two queues
class MyStack {
public:
deque<int> deq1;//Normal queue
deque<int> deq2;//Backup queue
​
MyStack() {
​
}
​
void push(int x) {
deq1.push_back(x);
}
​
int pop() {
//If queue 1 is not empty, the first in the queue is deleted n-1 Elements(Suppose there are n element)Push queue 2 and pop the last element
while (deq1.size() - 1 > 0) {
deq2.push_back(deq1.front());
deq1.pop_front();
}
int result = deq1.front();
deq1.pop_front();
//Push all the elements in queue 2 into queue 1
while (deq2.size() > 0) {
deq1.push_back(deq2.front());
deq2.pop_front();
}
return result;
}
​
int top() {
return deq1.back();
}
​
bool empty() {
if (deq1.empty()) return true;
else return false;
}
};```

analysis:

• Time complexity: push(): O(1); pop(): O(N); top(): O(1); empty(): O(1); N is the number of elements in the queue

• Spatial complexity: O(N), two queues are required.

```//Use a queue
class MyStack {
public:
deque<int> deq;
​
MyStack() {
​
}
​
void push (int x) {
deq.push_back(x);
}
​
int pop() {
int size = deq.size();
while (size - 1 > 0) {
deq.push_back(deq.front());
deq.pop_front();
size--;
}
int result = deq.front();
deq.pop_front();
return result;
}
​
int top() {
return deq.back();
}
​
bool empty() {
return deq.empty();
}
​
};```

analysis:

• Time complexity: push(): O(1); pop(): O(N); top(): O(1); empty(): O(1); N is the number of elements in the queue

• Spatial complexity: O(N), a queue is required.

Keywords: leetcode