目录

一、题目描述

二、思路讲解

三、算法描述

四、Java代码实现

五、时空复杂度分析

        1、时间复杂度

        2、空间复杂度

六、其他代码实现

        1、C++

        2、C#

        3、Python3

一、题目描述

        用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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 次调用

二、思路讲解

        首先要明确栈是先进后出的，与队列的先进先出刚好相反。

        第一个函数功能是在队列尾部插入整数，那么无论是队列还是栈，直接push就实现了这个功能；

        第二个函数功能是在队列头部删除整数，那么仅靠一个栈就不能完成了。我们可以换个角度，由于栈的进出规则和队列是刚好相反的，那么我们再借助一个栈，将第一个栈中的元素逐一弹出，再逐一压入第二个栈中，再弹出，那么，从这两个栈的外部看来，是不是就实现了先进先出的功能呢？

三、算法描述

        要实现在队列尾部插入整数，直接将元素压入第一个栈中即可；

        要实现在队列头部删除整数，先判断第二个栈是否为空，若为空，则将第一个栈中的元素逐一弹出，再压入第二个栈中；

        如果此时第二个栈仍为空，说明第一个栈中没有元素，返回-1；如果不为空，则弹出第二个栈中的一个元素（stack2栈顶元素即为队列尾部元素）即可。

四、Java代码实现

class CQueue {Deque<Integer> stack1;Deque<Integer> stack2;public CQueue() {stack1 = new LinkedList<Integer>();stack2 = new LinkedList<Integer>();}//在队列尾部插入整数public void appendTail(int value) {stack1.push(value);}//在队列头部删除整数public int deleteHead() {if(stack2.isEmpty()) {//将stack1中元素一一弹入stack2中while(!stack1.isEmpty()) {stack2.push(stack1.pop());}} //此时为空，说明stack1中没有元素；否则stack2栈顶元素即为队列尾部元素if(stack2.isEmpty()) {return -1;} else {return stack2.pop();}}
}

五、时空复杂度分析

        1、时间复杂度

        对于插入和删除操作，时间复杂度均为O(1)。插入不多说，对于删除操作，虽然看起来是 O(n) 的时间复杂度，但是仔细考虑下每个元素只会至多被插入和弹出 stack2 一次，因此均摊下来每个元素被删除的时间复杂度仍为 O(1)。

        2、空间复杂度

        O(n)。需要使用两个栈存储已有的元素。

六、其他代码实现

从力扣偷的其他语言的代码，以供参考。

        1、C++

class CQueue {stack<int> stack1,stack2;
public:CQueue() {while (!stack1.empty()) {stack1.pop();}while (!stack2.empty()) {stack2.pop();}}void appendTail(int value) {stack1.push(value);}int deleteHead() {// 如果第二个栈为空if (stack2.empty()) {while (!stack1.empty()) {stack2.push(stack1.top());stack1.pop();}} if (stack2.empty()) {return -1;} else {int deleteItem = stack2.top();stack2.pop();return deleteItem;}}
};

        2、C#

public class CQueue 
{private Stack<int> stack1;private Stack<int> stack2;public CQueue() {stack1 = new Stack<int>();stack2 = new Stack<int>();}public void AppendTail(int value) {stack1.Push(value);}public int DeleteHead() {if (stack2.Count == 0) {while (stack1.Count != 0) {stack2.Push(stack1.Pop());}} if (stack2.Count == 0) {return -1;} else {int deleteItem = stack2.Pop();return deleteItem;}}
}

        3、Python3

class CQueue:def __init__(self):self.stack1 = []self.stack2 = []def appendTail(self, value: int) -> None:# 1 -> 2while self.stack1:self.stack2.append(self.stack1.pop())# add valueself.stack1.append(value)# 1 <- 2while self.stack2:self.stack1.append(self.stack2.pop())return self.stack1def deleteHead(self) -> int:if not self.stack1: return -1return self.stack1.pop()