用队列实现栈
LeetCode225. 用队列实现栈
题目描述
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push
、top
、pop
和 empty
)。
实现 MyStack 类:
void push(int x)
将元素 x 压入栈顶。
int pop()
移除并返回栈顶元素。
int top()
返回栈顶元素。
boolean empty()
如果栈是空的,返回 true
;否则,返回 false
。
注意:
-
你只能使用队列的基本操作 —— 也就是 push to back
、peek/pop from front
、size
和 is empty
这些操作。
-
你所使用的语言也许不支持队列。 你可以使用 list
(列表)或者 deque
(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
示例:
1
2
3
4
5
|
输入:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 2, 2, false]
|
解释:
1
2
3
4
5
6
|
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
|
提示:
1 <= x <= 9
- 最多调用
100
次 push
、pop
、top
和 empty
- 每次调用
pop
和 top
都保证栈不为空
思路
题目要求
- 用两个队列来实现栈,该栈类具有四个方法:压栈、弹栈、返回栈顶元素、判断栈空
队列是先进先出,栈是先后进先出。用队列模拟栈,其实一个队列就够了
压栈就是将元素放入队尾;弹栈就是取出队尾元素;返回栈顶元素就是返回队尾元素;队列中没有元素即栈空。
代码
Go
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
|
// MyStack 栈类
type MyStack struct {
queue []int
}
// Constructor 构造方法
func Constructor() MyStack {
queue := make([]int, 0)
return MyStack{queue}
}
// Push 压栈
func (this *MyStack) Push(x int) {
this.queue = append(this.queue, x)
}
// Pop 弹栈
func (this *MyStack) Pop() int {
result := this.queue[len(this.queue)-1]
this.queue = this.queue[:len(this.queue)-1]
return result
}
// Top 返回栈顶元素
func (this *MyStack) Top() int {
return this.queue[len(this.queue)-1]
}
// Empty 判断栈空
func (this *MyStack) Empty() bool {
if len(this.queue) == 0 {
return true
}
return false
}
|
Link
GitHub