Leetcode学习之栈和队列

1. 栈和队列理论基础

队列是先进先出&＃xff0c;栈是先进后出。

如图所示&＃xff1a;

首先大家要知道 栈和队列是STL&＃xff08;C&＃43;&＃43;标准库&＃xff09;里面的两个数据结构。

C&＃43;&＃43;标准库是有多个版本的&＃xff0c;要知道我们使用的STL是哪个版本&＃xff0c;才能知道对应的栈和队列的实现原理。

那么来介绍一下&＃xff0c;三个最为普遍的STL版本&＃xff1a;

HP STL 其他版本的C&＃43;&＃43; STL&＃xff0c;一般是以HP STL为蓝本实现出来的&＃xff0c;HP STL是C&＃43;&＃43; STL的第一个实现版本&＃xff0c;而且开放源代码。

P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的&＃xff0c;被Visual C&＃43;&＃43;编译器所采用&＃xff0c;不是开源的。

SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现&＃xff0c;被Linux的C&＃43;&＃43;编译器GCC所采用&＃xff0c;SGI STL是开源软件&＃xff0c;源码可读性甚高。

接下来介绍的栈和队列也是SGI STL里面的数据结构&＃xff0c; 知道了使用版本&＃xff0c;才知道对应的底层实现。

来说一说栈&＃xff0c;栈先进后出&＃xff0c;如图所示&＃xff1a;

栈提供push 和 pop 等等接口&＃xff0c;所有元素必须符合先进后出规则&＃xff0c;所以栈不提供走访功能&＃xff0c;也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。

栈是以底层容器完成其所有的工作&＃xff0c;对外提供统一的接口&＃xff0c;底层容器是可插拔的&＃xff08;也就是说我们可以控制使用哪种容器来实现栈的功能&＃xff09;。

所以STL中栈往往不被归类为容器&＃xff0c;而被归类为container adapter&＃xff08;容器适配器&＃xff09;。

那么问题来了&＃xff0c;STL 中栈是用什么容器实现的&＃xff1f;

从下图中可以看出&＃xff0c;栈的内部结构&＃xff0c;栈的底层实现可以是vector&＃xff0c;deque&＃xff0c;list 都是可以的&＃xff0c; 主要就是数组和链表的底层实现。

我们常用的SGI STL&＃xff0c;如果没有指定底层实现的话&＃xff0c;默认是以deque为缺省情况下栈的低层结构。

deque是一个双向队列&＃xff0c;只要封住一段&＃xff0c;只开通另一端就可以实现栈的逻辑了。

SGI STL中 队列底层实现缺省情况下一样使用deque实现的。

我们也可以指定vector为栈的底层实现&＃xff0c;初始化语句如下&＃xff1a;

std::stack<int, std::vector<int> > third; // 使用vector为底层容器的栈


刚刚讲过栈的特性&＃xff0c;对应的队列的情况是一样的。

队列中先进先出的数据结构&＃xff0c;同样不允许有遍历行为&＃xff0c;不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。

也可以指定list 为起底层实现&＃xff0c;初始化queue的语句如下&＃xff1a;

std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列


所以STL 队列也不被归类为容器&＃xff0c;而被归类为container adapter&＃xff08; 容器适配器&＃xff09;。

我这里讲的都是C&＃43;&＃43; 语言中情况&＃xff0c; 使用其他语言的同学也要思考栈与队列的底层实现问题&＃xff0c; 不要对数据结构的使用浅尝辄止&＃xff0c;而要深挖起内部原理&＃xff0c;才能夯实基础。

2. 用栈实现队列

题目链接

使用栈实现队列的下列操作&＃xff1a;

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。

示例:

MyQueue queue &＃61; new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false


说明:

你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque&＃xff08;双端队列&＃xff09;来模拟一个栈&＃xff0c;只要是标准的栈操作即可。
假设所有操作都是有效的 &＃xff08;例如&＃xff0c;一个空的队列不会调用 pop 或者 peek 操作&＃xff09;

2.1 思路

这是一道模拟题&＃xff0c;不涉及到具体算法&＃xff0c;考察的就是对栈和队列的掌握程度。

使用栈来模式队列的行为&＃xff0c;如果仅仅用一个栈&＃xff0c;是一定不行的&＃xff0c;所以需要两个栈一个输入栈&＃xff0c;一个输出栈&＃xff0c;这里要注意输入栈和输出栈的关系。

下面动画模拟以下队列的执行过程如下&＃xff1a;

执行语句&＃xff1a;
queue.push(1);
queue.push(2);
queue.pop(); 注意此时的输出栈的操作
queue.push(3);
queue.push(4);
queue.pop();
queue.pop();注意此时的输出栈的操作
queue.pop();
queue.empty();

在push数据的时候&＃xff0c;只要数据放进输入栈就好&＃xff0c;但在pop的时候&＃xff0c;操作就复杂一些&＃xff0c;输出栈如果为空&＃xff0c;就把进栈数据全部导入进来&＃xff08;注意是全部导入&＃xff09;&＃xff0c;再从出栈弹出数据&＃xff0c;如果输出栈不为空&＃xff0c;则直接从出栈弹出数据就可以了。

最后如何判断队列为空呢&＃xff1f;如果进栈和出栈都为空的话&＃xff0c;说明模拟的队列为空了。

在代码实现的时候&＃xff0c;会发现pop() 和 peek()两个函数功能类似&＃xff0c;代码实现上也是类似的&＃xff0c;可以思考一下如何把代码抽象一下。