LeetCode 相关的文章：

1. LeetCode | 206.反转链表
2. LeetCode | 24.两两交换链表中的节点
3. LeetCode | 141.环形链表
4. LeetCode | 20.有效的括号

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

一、题目描述

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

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

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

    /** Push element x onto stack. */
    void push(int x) {
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
    }

    /** Get the top element. */
    int top() {
    }

    /** Returns whether the stack is empty. */
    bool empty() {
    }
};

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

从上面的类定义可以看出，这次的实现和之前几篇文章中的题目有所不同，之前的是要求实现一个函数体，而这次是实现一个完整的类定义。

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

二、问题分析

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

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

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

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

在第一幅图中有四个元素在队列中，我们要模拟栈结构执行 pop 操作的话，应该将元素 4 出队，但是队列的 pop 操作出队的却是元素 1，因此，我们没有办法直接让元素 4 出队。

当然了，直接让元素 4 出队是不可能了，但是我们可以利用其他的方式让其出队。在元素 4 出队前，依次让元素 1、2 和 3 出队再入队，此时元素 4 就到了队头，这时让元素 4 出队就可以了。用一组图演示一下元素 4 出队的情况。

我们要让元素 4 出队，就需要将元素 4 移动到队头，那么就需要将元素 1 出队，然后再入队到队尾，然后依次这样操作元素 2 和元素 3。然后元素 4 就到了队头，执行队列的 pop 操作就可以让其出队了。

下次出队的时候，可以将元素 3 移动到队头，然后出队。此时队列中还剩元素 1 和元素 2。如果有入队的，那么就直接放到队列的队尾即可。

通过这样的操作，就让队列实现了栈的操作。

三、代码实现

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

class MyStack {
private:
    queue<int> q;
public:
    /** Initialize your data structure here. */
    MyStack() {

    }

    /** Push element x onto stack. */
    void push(int x) {
        q.push(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int size = q.size();
        int n = 0;
        int tmp;

        while (n < size - 1) {
            tmp = q.front();
            q.pop();
            q.push(tmp);

            n ++;
        }

        tmp = q.front();
        q.pop();

        return tmp;
    }

    /** Get the top element. */
    int top() {
        return q.back();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return q.empty();
    }
};


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

我直接使用了 C++ 的 queue 这个队列，queue 支持队列的所有操作。queue 支持队列常用操作有：

• push()： 队尾入队
• pop()： 队头出队
• size()： 队列长度
• empty()：队列是否为空
• front()： 返回队头元素的值
• back()： 返回队尾元素的值

整个题目中最复杂的部分应该就是出栈的操作，而整个出栈的操作其实一个循环就可以了。

四、提交结果

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

这个题目重点就是在考察思路了，有谁在实际的项目中会这么玩数据结构呢？