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

题目描述

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

思路

deleteHead函数

当需要删除元素时

• 如果s2为空，如图1 a、b、c所示，只需要将s1中的所有元素依次出栈，再入栈到s2中，这样s2中，先入栈的在栈顶，，后入栈的在栈顶，只需要直接弹出s2栈顶的元素即可完成队列的头部删除功能。
• 如果s2不为空，如图1 d、e、c所示,此时队列的实际顺序为从s2栈顶到栈底，再从s1的栈底到栈顶。也就是图中的2,3,4,此时s2栈顶的元素仍然为队列的头部元素，弹出即可完成队列的头部删除功能。

appendTail函数

设s1，s2为两个队列

• 如果s2为空，如图1 a所示，添加元素1,2,3只需要在s1中依次入栈，此时队列的顺序为s1栈底到栈顶。

• 如果s2不为空，如图1 e、f所示，添加元素5同样只需要在s1中依次入栈，此时队列的顺序为从s2栈顶到栈底，再从s1的栈底到栈顶。

综上，对于尾部添加元素，只需要在s1直接入栈。

代码实现

class CQueue
{
private:
    // 定义两个栈
    stack<int> s1;
    stack<int> s2;
    // 定义两个栈的元素数量
    int len1;
    int len2;

public:
    CQueue()
    {
        // 初始化栈长度均为零
        len1 = len2 = 0;
    }

    void appendTail(int value)
    {
        // 添加元素直接在s1添加
        s1.push(value);
        // 元素数量+1
        ++len1;
    }

    int deleteHead()
    {
        // 如果两个栈均为空，无元素删除
        if((len1 + len2) == 0){
            return -1;
        }
        // 如果栈s2为空，则把s1倒入s2，s2栈底为后入元素，栈顶为先入元素
        if (len2 == 0)
        {
            while (len1 > 0)
            {
                s2.push(s1.top());
                s1.pop();
                --len1;
                ++len2;
            }
        }
        // 直接删除、返回s2栈顶值
        int ans = s2.top();
        --len2;
        s2.pop();
        return ans;
    }
};

通过截图