数据结构与算法学习笔记 4.栈和队列

4.栈和队列

4.1 栈

4.1.1 栈模型

​ 栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫作栈的顶(top)。 对栈的基本操作有Push(进栈)和Pop(出栈)，前者相当于插入，后者则是删除最后插入的元素。

​ 栈有时又叫做LIFO(后进先出)表。理解栈的定义需要注意: **首先它是—个线性表,也就是说,栈元素具有线性关系,即前驱后继关系。只不过它是—种特殊的线性表而已。**定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶而不是栈底。

​ 它的特殊之处就在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。 这也就使得:栈底是固定的，最先进栈的只能在栈底。栈的插入操作，叫作进栈、也称压栈、入栈。类似子弹入弹夹。栈的删除操作，叫作出栈，有的也叫作弹栈。如同弹夹中的子弹出夹，具体可参照下图所示。

4.1.2 进栈出栈的变化形式

思考：假设有3个元素1, 2, 3，入栈顺序是1, 2, 3, 则它们的出栈顺序有几种可能?

1. 第一种：1、2、3进，再3、2、1出。这是最简单最好理解的一种, 出栈次序为 3、2、1。
2. 第二种：1进，1出，2进，2出，3进，3出。也就是进一个就出一个，出栈次序为1、2、3。
3. 第三种：1进，2进，2出，1出，3进，3出。出栈次序为2、1、3。
4. 第四种：1进，1出，2进，3进，3出，2出。出栈次序为1、3、2。
5. 第五种：1进，2进，2出，3进，3出，1出。出栈次序为2、3、1。

**有没有可能是3、1、2这样的次序出栈呢?**答案是肯定不会。因为3先出栈就意昧3曾经进栈，既然3都进栈了，那也就意昧着, 1和2已经进栈了。此时，2—定是在1 的上面，就是更接近栈顶，那么出栈只可能是3、2、1。不然不满足1、2、3依次进栈的要求，所以此时不会发生1比2先出栈的情况。 从这个简单的例子就能看出，只是3个元素就有5种可能的出栈次序’如果元素数量多，其实出栈的变化将会更多。

4.1.3 栈的实现-顺序存储结构

​ 既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。

栈的结构定义：

typedef int SELemType;//SELemType类型根据实际情况而定,这里假设为int
//顺序栈结构
typedef struct
{
	SElemType data[MAXSIZE];
	int top; //用于栈顶指针
}SqStack;
1
2
3
4
5
6
7

进栈操作：

对于栈的插入，即进栈操作，其实就是做了如下图所示的处理：

因此对于进栈操作push，其代码如下：

//插入元素e为新的栈顶元素
Status Push(SqStack* S, SElemType e) {
	if (S->top == MAXSIZE - 1) { //栈满
		return error;
	}
	S->top++; //栈顶指针增加1
	S->data[S->top] = e;  //将新元素赋值给栈顶空间
	return OK;
}
1
2
3
4
5
6
7
8
9

出栈操作：

出栈操作pop代码如下：

//若栈不为空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
Status Pop(SqStack* S, SElemType* e) {
	if (S->top == - 1) { 
		return ERROR;
	}
	*e = S->data[S->top];//将要删除的栈顶元素赋值给e
	S->top--;  //栈顶指针减1
	return OK;
}
1
2
3
4
5
6
7
8
9

两者没有涉及任何循环语句，因此时间复杂度为O(1)。

4.1.3 栈的实现-链式存储结构

​ 栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？由于单链表有头指针，而栈顶指针也是必须的，所以最好的办法是把栈顶放在单链表的头部，如下图。另外，都已经有了栈顶在头部了，单链表中常用的头节点也就失去了意义，通常对于链栈来说，是不需要头节点的。

对于链栈来说，基本不存在栈满的情况，除非内存已pic_center经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临 死机崩溃的情况，而不是这个链栈是否溢出的问题。

但对于空栈来说，链表原定义是头指针指向空，那么链栈的孔其实就是top = NULL的时候。

链栈的结构代码如下：

//链栈结构
typedef struct StackNode {
	SElemType data;
	struct StackNode* next;
}StackNode, *LinkStackPtr;

typedef struct {
	LinkStackPtr top;
	int count;
}LinkStack;
1
2
3
4
5
6
7
8
9
10

进栈操作：

对于链栈的进栈push操作，假设元素值为e的新结点时s，top为栈顶指针，示意图如下，代码如下：

//插入元素e为新的栈顶元素
Status Push(LinkStack* S, SElemType e) {
	LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
	s->data = e;
	s->next = S->top;//把当前的栈顶元素赋值给新结点的直接后继，如上图
	S->top = s;      //把新结点s赋值给栈顶指针，如上图
	S->count++;
	return OK;
}
1
2
3
4
5
6
7
8
9

出栈操作：

至干链栈的出栈pop操作，也是很简单的三句操作。假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可，如下图所示，代码如下：

//若栈不空，则删除S的栈顶元素，用e返回其值，并饭后OK；否则返回ERROR
Status Pop(LinkStack* S, SElemType* e) {
	LinkStackPtr p;
	if (StackEmpty(*S)) {
		return ERROR;
	}
	*e = S->top->data;
	p = S->top;      //将栈顶结点赋值给p
	S->top = S->top->next; //使得栈顶指针下移一位，指向后一节点，如上图
	free(p);
	S->count--;
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

链栈的进栈push和出栈pop操作都很简单，没有任何循环操作，时间复杂度均为O(1)。

​ 对比—下顺序栈与链栈，它们在时间复杂度上是一样的，均为O(1)。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便。而链栈则要求每个元素都有指针域，这同时也增加了—些内存开销，但对于栈的长度无限制。所以它们的区别和线性表中讨论的—样，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

4.2 队列

4.2.1 队列模型

​ 队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

​ 队列是种先进先出（FIFO）的线性表.允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q＝（a1，a2，…an），那么a1就是队头元素, 而an是队尾元素。这样我们就可以删除时总是从a1开始，而插入时列在最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后，如下图所示。

4.2.2 队列的实现-顺序存储结构

​ 我们假设—个队列有n个元素，则顺序存储的队列需建立—个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O(1)，如下图所示。

​ 与栈不同的是，队列元素的出列是在队头，即下标为0的位置，那也就意昧着队列中的所有元素都得向前移动，以保证队列的队头也就是下标为0的位置不为空，此时时间复杂度为O(n)，如下图所示。

​ 出队列时—定要全部移动呢？如果不去限制队列的元素必须存储在数组的前n个单元这一条件，出队的性能就会大大增加。也就是说，队头不需要一定在下标为0的位置，如下图所示。

​ 为了避免当只有一个元素时，队头和队尾重台使处理变得麻烦，所以引入两个指 针，front指针指向队头元素,，rear指针指向队尾元素的下一个位置，这样当front等干rear 时，此队列不是还剩一个元素，而是空队列。

​ 但这样会产生数组越界的错误如下图出队a1、a2,，则front指针指向下标为2的位置， rear不变，如左下图所示，再入队a5，此时front指针不变，rear指针移动到数组之外，如右下图所示。可实际上我们的队列在别的地方还有空闲的，我们把这种现象叫做“假溢出”。

​ 所以解决假溢出的办法就是后面满了就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

​ 刚才的例子继续，上图的rear可以改为指向下标为0的位置，这样就不会造成指针指向不明的问题了，如下图所示。

​ 接着入队a6，将它放置于下标为0处, rear指针指向下标为1处，如左下图所示。若再入队a7，则rear指针就与front指针重合,同时指向下标为2的位置，如右下图所示。

​ 此时问题又出来了，我们刚才说空队列时，front等于rear。现在当队列满时，也是front等于rear，那么如何判断此时的队列究竟是空还是满呢? 办法一是设置一个标志变量flag，当front＝rear，且flag＝O时为队列空，当front＝ rear且flag＝1时为队列满。 **办法二是当队列空时，条件就是front＝rear，当队列满时，我们修改其条件，保留一个元素空间。**也就是说，队列满时，数组中还有—个空闲单元。例如左下图所示，我们就认为此队列已经满了，也就是说，我们不允许右上图情况。

​ 我们重点来讨论第二种方法：由干rear可能比front大，也可能比front小。所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为QueueSize，那么队列满的条件是 (rear + 1) % QueueSize == front（取模的目的就是为了整合rear与front大小为—个问题）。比如上面这个例子，QueueSize ＝ 5，左上图中front = 0 ，而rear＝4，（4＋1）％ 5＝0，所以此时队列满。再比如右上图，front＝2而rear＝ 1。（1＋1）％ 5＝2，所以此时队列也是满的。而对于下图front＝2而rear＝0，(0＋1) ％ 5＝ 1，1≠2，所以此时队列并没有满。

​ 另外，当rear＞front时,即下图的图1和图2，此时队列的长度为rear-front。但当 rear＜front时，如上图和下图的图3，队列长度分为两段，—段是QueueSize - front，另段是0＋rear，加在一起队列长度为rear - front＋QueueSize。

因此通用的计算队列长度的公式为: （rear - front＋QueueSize）％ QueueSize

经过上面的详述，循环队列的顺序存储结构代码如下：

typedef int QElemType; //QElemType类型根据实际情况而定，这里假设为int
//循环队列的顺序存储结构
typedef struct {
	QElemType data[MAXSIZE];
	int front; //头指针
	int rear; //尾指针，若队列不为孔，指向队列元素的下一个位置
}SqQueue;
1
2
3
4
5
6
7

循环队列初始化代码如下：

//初始化一个孔队列
Status InitQueue(SqQueue* Q) {
	Q->front = 0;
	Q->rear = 0;
	return OK;
}
1
2
3
4
5
6

循环队列求队列长度代码如下：

//返回Q的元素个数，也就是队列的当前长度
int QueueLength(SqQueue Q) {
	return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}
1
2
3
4

循环队列的入队代码如下：

//多队列未满，则插入元素e为Q的新队尾元素
Status EnQueue(SqQueue* Q, QElemType e) {
	if ((Q->rear + 1) % MAXSIZE == Q->front){//队列满的判断
		return ERROR;
	}
	Q->data[Q->rear] = e;//将元素e赋给队尾
	Q->rear = (Q->rear + 1) % MAXSIZE; //rear指针向后移动一位
	                                   //若到最后则转移到数组头部
	return OK;
}
1
2
3
4
5
6
7
8
9
10

循环队列的出队代码如下：

//若队列不空，则删除Q中队头元素，用e返回其值
Status DeQueue(SqQueue* Q, QElemType* e) {
	if (Q->rear == Q->front){//队列空的判断
		return ERROR;
	}
	*e = Q->data[Q->front];//将队头元素赋值给e
	Q->front = (Q->front + 1) % MAXSIZE; //front指针向后移动一位
	                                   //若到最后则转移到数组头部
	return OK;
}
1
2
3
4
5
6
7
8
9
10

4.2.3 队列的实现-链式存储结构

​ 队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点，如下图。

​ 空队列时，front和rear都指向头结点。

链队列的结构代码为：

typedef int QElemType; //QElemType类型根据实际情况而定，这里假设为int
//结点结构
typedef struct QNode {
	QElemType data;
	struct QNode* next;
}QNode, *QueuePtr;

//队列的链表结构
typedef struct {
    QueuePtr front,rear;//队头、队尾指针
}LinkQueue;
1
2
3
4
5
6
7
8
9
10
11

队列链式存储入队代码如下：

//插入元素e为Q的新的队尾元素
Status EnQueue(LinkQueue* Q, QElemType e) {
	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
	if (!s) exit(OVERFLOW);//存储分配失败
	s->data = e;
	s->next = NULL;
	Q->rear->next = s;//把拥有元素e的新结点s赋值给原队尾结点的后继，如上图
	Q->rear = s;//把当前的s设置为队尾结点，rear指向s，如上图
	return OK;
}
1
2
3
4
5
6
7
8
9
10

队列链式存储出队代码如下：

出队操作时,就是头结点的后继结点出队,将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素，需将rear指向头结点，如下图所示。

//若队列不空，，则删除Q中队头元素，用e返回其值，返回OK,否则返回ERROR
Status DeQueue(LinkQueue* Q, QElemType* e) {
	QueuePtr p;
	if (Q->front == Q->rear) return ERROR;
	p = Q->front->next;//将欲删除的队头结点暂时保存给p，如上图
	*e = p->data;//将值赋给e
	Q->front->next = p->next;//将原队头结点的后继p->next赋值给头结点后继，如上图
	if (Q->rear == p) Q->rear = Q->front;
	free(p);
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11

4.3 应用

4.3.1 C++中相关问题

1. C++中stack 是容器么？
2. 我们使用的stack是属于哪个版本的STL？
3. 我们使用的STL中stack是如何实现的？
4. stack 提供迭代器来遍历stack空间么？

首先大家要知道栈和队列是STL（C++标准库）里面的两个数据结构。

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

那么来介绍一下，三个最为普遍的STL版本：

1. HP STL 其他版本的C++ STL，一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码。
2. P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。
3. SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。

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

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

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

所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

那么问题来了，STL 中栈是用什么容器实现的？

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

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

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

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

我们也可以指定vector为栈的底层实现，初始化语句如下：

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

刚刚讲过栈的特性，对应的队列的情况是一样的。

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

也可以指定list 为起底层实现，初始化queue的语句如下：

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

所以STL 队列也不被归类为容器，而被归类为container adapter（ 容器适配器）。

4.3.2 应用例题