LeetCode | 232.用栈实现队列

这次来写一下 LeetCode 的第 232 题，用栈实现队列。

题目描述

题目直接从 LeetCode 上截图过来，题目如下：

image

上面的题就是用栈实现队列题目的截图，同时 LeetCode 给出了一个类的定义，然后要求实现用栈实现队列的完整的数据结构。这次我同样没有使用 C 语言，而是使用了 C++ 语言，整个类的定义如下：

class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {

    }

    /** Push element x to the back of queue. */
    void push(int x) {

    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {

    }

    /** Get the front element. */
    int peek() {

    }

    /** Returns whether the queue is empty. */
    bool empty() {

    }
};


/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

从上面的类定义可以看出，这次实现的也是一个完整的数据结构，需要把题目给出的类的所有成员函数进行实现。

类定义中有几个要实现的成员函数，分别是，push 完成入队，pop 完成出队，peek** 用来获取队首的元素，empty 用来判断队列是否为空**。

这些都是队列最基本的功能了。

问题分析

这次的题目和上次的用栈实现队列的题目很相似，所以基础性的描述也都基本一致。

在数据结构中，队列和栈是两个完全不同的数据结构。队列是一个先进先出的数据结构，具有从队尾入队，从队头出队的特性。而栈是一个后进先出（先进后出）的数据结构，无论出栈还是入栈，始终都是在栈顶进行操作。

队列和栈这两种数据结构的操作如下图所示。

image.gif

image

上面的第一幅图是队列，队列只能从队尾入队，从队头出队。

上面的第二幅图是栈，入栈和出栈只能在栈顶的位置进行操作。

栈的入栈和出栈都在栈的一端进行操作，而队列的操作则在队首和队尾进行操作，即入栈和出栈都在栈顶进行操作。如果是栈结构，当元素 1、元素 2 和元素 3 都入栈以后，出栈的顺序是元素 3、元素 2 和元素 1。但是如果是队列的话，那么出队的顺序仍然是元素 1、元素 2 和元素 3，那么此时栈就很为难了。

但是如果此时还有一个栈的话，就可以实现队列的功能了。当元素 1、元素 2 和元素 3 入栈以后的情况是这样的，如下图。

image

然后要进行“出队”，我们就把当前栈的元素都出栈到另外一个栈中，如下图。

image

左面的栈出栈顺序是元素 3、元素 2 和元素 1，而右面的栈的入栈顺序就是元素 3、元素 2 和元素 1。而“出队”时，我们就将右侧栈中的首个元素出栈即可。

我们将左侧的栈称为 in 栈，将右侧的栈称为 out 栈。****in 栈负责元素的“入队”，out 栈负责元素的“出队”。只要是“入队”操作，就直接入栈到 in 栈，如果时“出队”的话，就先判断 out 栈是否为空，为空则将 in 栈中的元素出栈并入栈到 out 栈，如果不为空就直接出栈 out 栈中的元素。“入队”时，无需进行判断，直接执行入栈操作，将元素入栈到 in 栈即可。

代码实现

依据我的思路来写代码，代码还是比较简单的，代码如下：

class MyQueue {
    stack<int> in; 
    stack<int> out;
public:
    /** Initialize your data structure here. */
    MyQueue() {


    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        in.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int x = 0;


        if (out.empty()) {
            while (!in.empty()) {
                x = in.top();
                out.push(x);
                in.pop();
            }
        }


        x = out.top();
        out.pop();
        return x;
    }
    
    /** Get the front element. */
    int peek() {
        int x = 0;


        if (out.empty()) {
            while (!in.empty()) {
                x = in.top();
                out.push(x);
                in.pop();
            }
        }


        return out.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        if (in.empty() && out.empty()) {
            return true;
        }


        return false;
    }
};


/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

整个代码的逻辑并不复杂，这里就不再讲解了。

提交结果

在写完 MyQueue 类后，点击右下角的 “执行代码”，然后观察 “输出” 和 “预期结果” 是否一致，一致的话就点击 “提交” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体，如果所有的测试用例都通过了，那么就会给出 “通过” 的字样，如果没有通过，会给出失败的那一组测试用例，我们继续修改代码。我们以上代码 “提交” 以后的截图如下：

image

微信中搜索 “码农UP2U” 关注我的公众号吧！！！