用两个栈实现队列
题目描述
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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();
}
}
|