lc225

225-Implement Stack using Queue

Description
Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

  • void push(int x) Pushes element x to the top of the stack.
  • int pop() Removes the element on the top of the stack and returns it.
  • int top() Returns the element on the top of the stack.
  • boolean empty() Returns true if the stack is empty, false otherwise.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class MyStack {
public:
queue<int> q1;
queue<int> q2;
int topV;

MyStack() {

}

void push(int x) {
q1.push(x);
topV = x;
}

int pop() {
while (q1.size() > 1) {
int x = q1.front();
q1.pop();
q2.push(x); // Make a copy of q1
topV = x;
}

int popValue = q1.front();
q1.pop();

swap(q1, q2);

return popValue;
}

int top() {
return topV;
}

bool empty() {
return q1.empty();
}
};

/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
Author

Joe Chu

Posted on

2023-11-06

Updated on

2024-03-24

Licensed under

Comments