AlgoPressAppearance
09-用两个栈实现队列
题目描述
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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 次调用
思路分析
栈是先进后出，队列是先进先出。
使用两个栈实现队列，我们可以定义 leftStack 和 rightStack，当执行 appendTail的时候，我们不停的往 leftStack 中插入数据，当执行 deleteHead的时候，我们就发leftStack中后面的数字，按顺序弹出并且插入到 rightStack中，然后弹出rightStack中最上面那个，然后再将 rightStack中的数据按照顺序插入到 leftStack中去。
中间我们可以优化为，延缓rightStack往 leftStack插入的步骤，这样连续执行 deleteHead的时候，我们可以连续从 rightStack弹出，直到用户执行 appendTail的时候，就先将 rightStack中的数据转入到 leftStack中去
实现代码
常规解法
csharp
public class CQueue {
private Stack<int> leftStack = new Stack<int>();
private Stack<int> rightStack = new Stack<int>();
public CQueue() {
}
public void AppendTail(int value) {
while (rightStack.Count > 0)
{
leftStack.Push(rightStack.Pop());
}
leftStack.Push(value);
}
public int DeleteHead() {
while(leftStack.Count > 0)
{
rightStack.Push(leftStack.Pop());
}
return rightStack.Count > 0 ? rightStack.Pop() : -1;
}
}
优化操作
leftStack 只负责插入， rightStack负责DeleteHead，当不够的时候，再从 leftStack中导数据
csharp
public class CQueue {
private Stack<int> leftStack = new Stack<int>();
private Stack<int> rightStack = new Stack<int>();
public CQueue() {
}
public void AppendTail(int value) {
leftStack.Push(value);
}
public int DeleteHead() {
//如果 rightStack 中有数据直接 Pop
if(rightStack.Count > 0){
return rightStack.Pop();
}
//如果 rightStack 中没数据，就从 leftStack中导数据过来
while(leftStack.Count > 0)
{
rightStack.Push(leftStack.Pop());
}
//如果 两个stack都没有数据
return rightStack.Count > 0 ? rightStack.Pop() : -1;
}
}
复习：20220611
csharp
public class CQueue {
Stack<int> leftStack;
Stack<int> rightStack;
public CQueue() {
leftStack = new Stack<int>();
rightStack = new Stack<int>();
}
public void AppendTail(int value) {
leftStack.Push(value);
}
public int DeleteHead() {
if(rightStack.Count > 0){
return rightStack.Pop();
}
else if(leftStack.Count > 0){
while(leftStack.Count > 0){
rightStack.Push(leftStack.Pop());
}
return rightStack.Pop();
}
else{
return -1;
}
}
}