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