9. 用两个栈实现队列
1. 描述
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
2. 例子
示例 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]
3 提示
- 1 <= values <= 10000
- 最多会对 appendTail、deleteHead 进行 10000 次调用
4. 题解
n 是存储的元素个数，对于单次的插入或删除操作：
时间复杂度: O(1)
空间复杂度: O(n)
class CQueue
{
private:
stack<int> pushStack;
stack<int> popStack;
public:
CQueue()
{
}
void appendTail(int value)
{
pushStack.push(value);
}
int deleteHead()
{
if(popStack.empty())
{
while(!pushStack.empty())
{
popStack.push(pushStack.top());
pushStack.pop();
}
}
if(popStack.empty()) return -1;
int frontValue = popStack.top();
popStack.pop();
return frontValue;
}
};