5、栈实现队列

厨子大约 4 分钟数据结构算法算法基地面试栈队列剑指Offer数据结构设计刷题程序厨校招社招

栈实现队列

题目解析

今天给大家带来一个有意思的题目，思路很 easy，但是刚刷题的小伙伴，示例理解起来可能会有点费劲，花里胡哨一大堆是啥意思啊。在之前的文章《不知道这篇文章合不合你的胃口》中写了栈是先进后出，队列是先进先出。本题让我们用两个先进后出的栈，完成一个先进先出的队列。我们应该怎么实现呢？

废话不多说，大家看图

这就是具体思路，然后我们来看一下题目示例及官方提供的函数都是什么意思。

代码

class CQueue {
    //创建队列
    public CQueue() {

    }
    //入队
    public void appendTail(int value) {

    }
    //出队
    public int deleteHead() {

    }
}

示例 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]

其实也很容易理解，输入有两行第一行，为执行的函数，Cqueue 代表创建队列(代表我们初始化两个栈)，appendTail 代表入队操作（代表 stackA 入栈），deleteHead 代表出队操作（代表我们 stackB 出栈）

第二行输入代表值，分别给每个函数传入的参数，我们发现只有 appendTail 函数下有对应值，因为只有该函数传入参数。

大家可以点击该链接剑指 Offer 09. 用两个栈实现队列open in new window去实现一下，下面我们看代码。

Java Code:

class CQueue {
     //初始化两个栈
    Stack<Integer> stack1,stack2;
    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();

    }
    //入队，我们往第一个栈压入值
    public void appendTail (int value) {
        stack1.push(value);
    }
    //出队
    public int deleteHead() {
        //大家可以自己思考一下为什么if条件为stack2.isEmpty(),细节所在
        if (stack2.isEmpty()) {
           //如果此时A栈没有值，则直接-1，我们可以看示例
           if (stack1.isEmpty()) {
               return -1;
           }
           //将A栈的值，压入B栈中
           while (!stack1.isEmpty()) {
               stack2.push(stack1.pop());
           }
        }
        return stack2.pop();
    }
}

C++：

#include <stack>
using namespace std;

class CQueue {
private:
    stack<int> stack1; // 入队栈：负责接收新元素
    stack<int> stack2; // 出队栈：负责弹出元素（维护队列的先进先出特性）

public:
    // 构造函数：初始化两个空栈（C++栈默认构造函数自动完成）
    CQueue() {}
    
    // 入队操作：将元素压入stack1
    void appendTail(int value) {
        stack1.push(value);
    }
    
    // 出队操作：从stack2弹出元素，若stack2为空则将stack1所有元素转移到stack2
    int deleteHead() {
        // 若出队栈stack2为空，需将入队栈stack1的所有元素转移过来（反转顺序）
        if (stack2.empty()) {
            // 若入队栈stack1也为空，说明队列为空，返回-1
            if (stack1.empty()) {
                return -1;
            }
            // 将stack1的元素全部弹出并压入stack2（此时stack2的栈顶为最早入队的元素）
            while (!stack1.empty()) {
                stack2.push(stack1.top()); // stack1的栈顶元素压入stack2
                stack1.pop(); // 弹出stack1的栈顶元素
            }
        }
        
        // 从stack2弹出栈顶元素（即最早入队的元素）
        int topVal = stack2.top(); // 先获取栈顶值（C++的pop无返回值）
        stack2.pop(); // 弹出栈顶元素
        return topVal;
    }
};

5、栈实现队列

# 栈实现队列

# 题目解析

# 代码

栈实现队列

题目解析

代码