用两个栈实现队列

用两个栈实现队列

题目描述

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1)

示例

示例 1:

1
2
3
4
输入:
["CQueue", "appendTail", "deleteHead", "deleteHead"]
[[], [3], [], []]
输出:[null, null, 3, -1]

示例 2:

1
2
3
4
输入:
["CQueue", "deleteHead", "appendTail", "appendTail", "deleteHead", "deleteHead"]
[[], [], [5], [2], [], []]
输出:[null, -1, null, null, 5, 2]

限制

1 <= values <= 10000

最多会对 appendTail、deleteHead 进行 10000 次调用

题目来源:力扣(LeetCode)
题目链接:https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
题目著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法一

直接使用两个栈 A、B,栈 A 用来存放 push 进的元素,需要 pop 时再将栈 A 中的元素先 pop 到栈 B 中,再在栈 B 进行 pop,这样就可以实现队列的顺序。

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
class CQueue {
private final Stack<Integer> stack1;
private final Stack<Integer> stack2;

public CQueue() {
this.stack1 = new Stack<>();
this.stack2 = new Stack<>();
}

public void appendTail(int value) {
this.stack1.push(value);
}

public int deleteHead() {
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
}
if (stack2.empty()) {
return -1;
}
return stack2.pop();
}

public int count() {
return stack1.size() + stack2.size();
}
}