题目内容
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。
(若队列中没有元素，deleteHead 操作返回 -1 )
示例1:
- 输入：
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[3],[],[]] - 输出：
[null,null,3,-1]
- 输入：
示例2:
- 输入：
[“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[],[5],[2],[],[]] - 输出：
[null,-1,null,null,5,2]
- 输入：
提示：
- 1 <= values <= 10000
- 最多会对 appendTail、deleteHead 进行 10000 次调用
解题思路
- 栈先进后出，无法实现队列功能
- 双栈实现队列，定义两个栈
- 一个栈
inStack实现入队，一个栈outStack实现出队 - 循环把
inStack的元素出栈到outStack中，实现inStack的倒序 outStack的出栈即为队列的出队
- 一个栈
- appendTail() 函数，直接把value添加到
inStack中 - deleteTail() 函数，有三种情况
- 当
outStack不为空，outStack中还有已完成倒序的元素，即没有全部出队，出队操作即为outStack的出栈 - 当
inStack为空，即两个栈都为空，则返回-1 - 否则，将
inStack全部倒序到outStack中，并返回outStack的栈顶
- 当
代码解法
Java
import java.util.LinkedList;
class CQueue {
LinkedList<Integer> inStack, outStack;
public CQueue() {
inStack = new LinkedList<>();
outStack = new LinkedList<>();
}
public void appendTail(int value) {
inStack.add(value);
}
public int deleteHead() {
if (!outStack.isEmpty()) {
return outStack.removeLast();
} else if (inStack.isEmpty()) {
return -1;
}
while (!inStack.isEmpty()) {
outStack.addLast(inStack.removeLast());
}
return outStack.removeLast();
}
}
/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.appendTail(value);
* int param_2 = obj.deleteHead();
*/
Python
class CQueue:
def __init__(self):
self.in_stack = []
self.out_stack = []
def appendTail(self, value: int) -> None:
self.in_stack.append(value)
def deleteHead(self) -> int:
if self.out_stack:
return self.out_stack.pop()
if not self.in_stack:
return -1
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
return self.out_stack.pop()