用两个栈实现队列
来源：牛客网 JZ5
描述
用两个栈来实现一个队列，分别完成在队列尾部插入整数(push)和在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。
示例1
1
2
|
输入：["PSH1","PSH2","POP","POP"]
返回值：1,2
|
思路
所有元素进stack1，然后全部出stack1并进入stack2.实现队列的先进先出即：若stack2非空，我们需要的恰好再栈顶，出栈;
若要给队列添加元素，即先进sack1,要出队时，若stack2不为空就出栈，为空时就把stack1全部进栈到stack2；
若用两个栈实现一个队列， 思路一般如下：
ps: my ugly 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
|
package main
import (
"container/list"
"fmt"
)
/*
两个栈实现一个队列
*/
var list1 = list.New()
var list2 = list.New()
//入队 123
func Push(node int) {
//入栈 123
list1.PushFront(node)
}
//队先进先出 123
func Pop() int {
if list2.Len() == 0 {
for list1.Len() != 0 {
//栈先进后出 321
front := list1.Front()
//入栈 321
list2.PushFront(list1.Remove(front).(int))
}
}
if list2.Len() > 0 {
//栈先进后出 123
first := list2.Front()
return list2.Remove(first).(int)
}
return -1
}
|
自己本地去构建测试的case, 对正确性做一个验证：
1
2
3
4
5
6
7
|
func main() {
Push(1)
Push(2)
// Push(3)
fmt.Println(Pop())
fmt.Println(Pop())
}
|
时间复杂度:O(n)
空间复杂度:O(n),需要使用两个栈存储已有的元素。
借助了Golang的库函数， 实现起来比较方便；
测试用例
- 往空的队列里面添加，删除元素；
- 往非空的队列里面添加，删除元素；
- 连续删除元素直至队列为空；
本题考点
- 考察对栈和队列的理解；
- 考察分析较为复杂问题的能力；本题最好是能通过手动画图来把抽象的问题具体化，从而解决这个比较复杂的问题；
高手解法与赏析
思路：
push操作就直接往stack1中push, pop操作需要分类对待一下：如果stack2为空，就需要把stack1中的数据转移到stack2中，然后再对stack2进行pop、如果stack2不为空，直接pop就OK；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
package main
var stack1 [] int
var stack2 [] int
func Push(node int) {
stack1 = append(stack1, node)
}
func Pop() int {
if len(stack2) == 0 {
for i := len(stack1) - 1; i >= 0; i-- {
stack2 = append(stack2, stack1[i])
}
stack1 = make([]int, 0)
}
if len(stack2) > 0 {
ret := stack2[len(stack2)-1]
stack2 = stack2[0 : len(stack2)-1]
return ret
}
return -1
}
|
这是当前排名第一的Golang代码实现， 简洁无废话， 值得学习；