剑指 Offer 09. 用两个栈实现队列

</br></br>

题目：

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例1：

输入：
["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
[[],[3],[],[],[]]
输出：[null,null,3,-1,-1]

示例2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：

• 1 <= values <= 10000
• 最多会对appendTail、deleteHead进行10000 次调用

</br></br>

思路一：

双栈。栈是先进后出的机构，队列是先进先出的结构。

CQueue()作为一个构造函数，在本题中不用管。

1.定义两个栈pushst和popst，将pushst栈作为输入栈用于appendTail操作，popst栈作为输出栈用于deleteHead操作；

2.进行appendTail操作时，直接将数据压入pushst栈中；

3.进行deleteHead操作时：

• 先检查popst和pushst是否为空，如果为空直接返回-1；

• 如果popst为空且pushst不为空，将pushst中的数据从栈顶开始放入popst中，然后再进行删除返回操作。

• 如果popst不为空，直接删除并返回栈顶元素。

代码如下：

class CQueue {
public:
    CQueue() {
        
    }
    
    void appendTail(int value) {
        pushst.push(value);
    }
    
    int deleteHead() {
        if(pushst.empty() && popst.empty())
            return -1;
        //如果popst中为空，则将pushst中的数据都倒入popst中
        if(popst.empty() && !pushst.empty())
        {
            while(!pushst.empty())
            {
                int tmp = pushst.top();
                popst.push(tmp);
                pushst.pop();
            }
        }
        //如果popst中不为空，直接删除并返回
        int tmp = popst.top();
        popst.pop();
        return tmp;
    }
private:
    stack<int> pushst;//实例化一个pushst栈，用于压入数据
    stack<int> popst;//实例化一个popst栈，用于删除数据
};

插入：

时间复杂度：O(1)

空间复杂度：O(1)

删除：

时间复杂度：O(N)，要将pushst中的数据全部压入popst中。

空间复杂度：O(N)，使用了辅助栈的空间。