用两个栈实现队列（C++简单区）

用两个栈实现队列

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

题目解读

刚开始看到题目后有点懵，一时不知道例子是什么意思，在看完别人的解析后才明白例子的含义。

[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”] ：这里表示的是按顺序执行每一步函数操作。然后[[],[3],[],[]]代表每一个函数所需要的参数。

举例：

CQueue 表示新建一个CQueue对象，对应的所需参数为[]，即此操作不需要参数。

appendTail 表示执行一个appendTail()操作，函数对应要所需要的参数为3。

deleteHead 表示执行一个deleteHead操作，对应的所需参数为[]，即此操作不需要参数。

deleteHead 表示执行一个deleteHead操作，对应的所需参数为[]，即此操作不需要参数。

解题思路

我们知道栈满足的是先进后出（FILO）规则，而队列满足的则是先进先出（FIFO）规则。所以要想实现用两个栈实现队列就要让一个栈完成添加元素的操作，另一个栈实现删除元素的操作。

这里我们定义栈s1完成压入元素操作，栈s2完成去除元素操作。

首先完成两个栈的初始化操作，使其初始化为两个空栈。当有数据压入s1时，我们直接将元素压入栈s1，但是由于先进的元素会压入栈底，所以为了实现队列先进先出的特点，我们在要删除元素时将s1中的元素全部压入到s2中，这样就实现了类似于将s1中元素反转压入s2，就能很好的满足队列的特点。不过在将s1元素压入s2中要确保s2此时是空栈，因为如果s2中有元素时，在我们要再次向s2中压入元素时，会将先前压入的元素又处于s2的栈底，这样就又不满足队列的特点了。

在s2为空栈的前提下，我们将s1中元素全部压入s2，完成这部操作后如果此时s2仍然为空栈，则说明s1、s2中都没有元素存在，此时则返回-1。

若s2不为空栈时，我们获取s2栈顶元素后将其栈顶元素删除，最后返回先前保留住的栈顶元素。

下面用动图来描述一下整个压入和删除的过程：

代码展示

代码如下：

class CQueue {
public:
/*s1栈用作添加元素
 *s2栈用作删除元素
 */
    stack<int>s1,s2;
    CQueue() {
        //初始化s1
        while(!s1.empty())
        {
            s1.pop();
        }
        //初始化s2
        while(!s2.empty())
        {
            s2.pop();
        }
    }
    //将添加的元素直接压入s1
    void appendTail(int value) {
        s1.push(value);
        return;
    }
    
    int deleteHead() {
        //如果s2栈为空时直接将s1中元素全部压入s2
        if(s2.empty())
        {
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
        }
        //如果此时栈s2还是为空，则说明两个栈中都没有元素，返回-1
        if(s2.empty())
        {
            return -1;
        }
        //如果s2不为空，则将栈顶元素取出并返回栈顶元素
        else
        {
            int elem=s2.top();
            s2.pop();
            return elem;
        }
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */
 执行用时：644 ms, 在所有 C++ 提交中击败了90.54%的用户
 内存消耗：103.6 MB, 在所有 C++ 提交中击败了78.96%的用户