LeetCode (225)：用队列实现栈
source link: https://mp.weixin.qq.com/s/mUSSg6ZkwuvoD7CbZAQS5Q
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LeetCode 相关的文章：
这次来写一下 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 类后，点击右下角的 “ 执行代码 ”，然后观察 “输出” 和 “预期结果” 是否一致，一致的话就点击 “ 提交 ” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体， 如果所有的测试用例都通过了，那么就会给出 “通过” 的字样， 如果没有通过，会给出失败的那一组测试用例，我们继续修改代码 。我们以上代码 “提交” 以后的截图如下：
这个题目重点就是在考察思路了，有谁在实际的项目中会这么玩数据结构呢？
喜欢就点在看哦~
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK