数据结构知识总结笔记------第三章：栈和队列（1） 栈和队列的基本概念，栈和队列的顺序存储与链式存储结构_双端队列catalan函数

第三章 栈和队列

3.1、栈

3.1.1栈的基本概念

（1）栈（Stack）的定义
栈是只可以在一端进行插入或删除操作的线性表。栈本质上是一种线性表，但这种线性表限定只能在某一端进行插入和删除操作。
栈顶（Top）：允许进行插入或删除操作的一端称为栈顶。
栈底（Bottom）：不允许进行插入和删除一端称为栈底。
空栈：不含任何元素的空表。

（2）栈（Stack）的特性
栈的主要特性是后进先出（Last In First Out，LIFO），也可称为先进后出（First In Last Out ，FILO）。

（3）栈的存储结构
栈可用顺序表和链表来存储，栈可以依照存储结构分为两种：顺序栈和链式栈。栈是一种在操作上限制的线性表，栈本质上属于线性表的一种，参考线性表的两种主要的存储结构-----顺序表和链表，栈也同样有对应的两种存储结构-----顺序栈和链栈。

（4）栈的数学特性
当n个元素以某种顺序进栈，并且可在任意时刻出栈（在满足先进后出的前提下）时，所获得的元素排列的数目N恰好满足函数Catalan()的计算，即

（5）栈的基本操作

InitStack（&S）：初始化一个空栈s。

StackEmpty（S）：判断一个栈是否为空，若栈s为空则返回true，否则返回false。

Push（&S，x）：进栈，若栈s未满，则将x加入使之成为新栈顶。

Pop（&S，&x）：出栈，若栈s非空，则弹出栈顶元素，并用x返回。

GetTop（S，&x）：读栈顶元素，若栈s非空，则用x返回栈顶元素。

DestroyStack（&S）：销毁栈，并释放栈s占用的存储空间（“s”表示引用调用）。

在解答算法题时，若题干未做出限制，则可直接使用这些基本的操作函数。

3.1.2、栈的顺序存储结构

（1）顺序栈的实现
采用顺序存储的栈称为顺序栈，顺序栈是用一组地址连续的存储单元存储从栈底到栈顶的数据元素，同时有一个指针（top）指示当前栈顶元素的位置。
栈的顺序存储类型结构定义：

#define  MaxSize  50  // 定义栈中元素的最大个数
typedef struct{
	Elemtype data[Maxsize]; // 存放栈中元素 MaxSize为已定义的常量
	int top;  // 栈顶指针
} SqStack；
1
2
3
4
5

栈顶指针：S.top，初始时设置S.top = -1；
栈顶元素：S.data[S.top]。
进栈操作：栈不满时，栈顶指针先加1，再存储值到栈顶元素。
出栈操作：栈不为空时，先取栈顶元素值，再将栈顶指针减1。
栈空条件：S.top==-1；
栈满条件：S.top ==Maxsize-1；
栈长：S.top +1。
顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，会发生栈上溢，此时应及时提示，以便及时处理，避免出错。

（2）顺序栈的基本运算
栈操作的示意图如图3.2所示。
图3.2（a）是空栈。
图3.2（c）是A、B、C、D、E共5个元素依次入栈后的结果。
图3.2（d）是在图3.2（c）之后E、D、C的相继出栈，此时栈中还有2个元素，或许最近出栈的元素C、D、E仍在原先的单元存储着，但top指针已经指向了新的栈顶，元素C、D、E已不在栈中。

1）初始化顺序栈

Void  InitStack（SqStack &S）{
	S.top = -1;  // 初始化栈顶指针
}
1
2
3

2）判断顺序栈是否为空

Bool  stackEmpty（Sqstack  S）{
	if(S.top== -1){
		return  true;  // 顺序栈为空，返回true
	else
		return  false;  // 顺序栈不为空，返回false
	}
}
1
2
3
4
5
6
7

3）顺序栈进栈操作

Bool  Push（SqStack  &S，Elemrype  x）{
	if（S.top==Maxsize-1）// 顺序栈已经满，返回false
		return false；
	s.data[++S.top]=x； // 栈顶指针先加1，再入栈
	return  true   // 进栈成功返回true
}
1
2
3
4
5
6

4）顺序栈出栈操作

Bool  Pop（SqStack  &S，Elemrype  &x）{
	if(S.top== -1){
			return  false;  // 顺序栈为空，返回false
    x= S.data[S.top--];  // x存储栈顶元素
    return  true;  // 出栈成功返回true
}
1
2
3
4
5
6

5）顺序栈读取栈顶元素

Bool  Pop（SqStack  &S，Elemrype  &x）{
	if(S.top== -1){
			return  false;  // 顺序栈为空，返回false
    x= S.data[S. top];  // x存储栈顶元素
    return  true;  // 读取成功返回true
}
1
2
3
4
5
6

（3）共享栈

利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，如图3.3所示。

两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=Maxsize时1号栈为空；仅当两个栈顶指针相邻（top1-top0=1）时，判断为栈满。当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减1再赋值；出栈时则刚好相反。
共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为O（1），对存取效率无影响。

3.1.3、栈的链式存储结构

采用链式存储的栈称为链栈，链栈便于多个栈共享存储空间和提高其效率，链栈不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点，Lhead指向栈顶元素，如图3.4所示。

栈的链式存储类型定义：

typedef  struct  Linknode{
	Elemrype  data;  // 数据域
	struct  Linknode *next;  // 指针域
}  *LiStack;
1
2
3
4

采用链式存储，便于结点的插入与删除。链栈的操作与链表类似，入栈和出栈的操作都在链表的表头进行。需要注意的是，对于带头结点和不带头结点的链栈，具体的实现会有所不同。

3.2 队列

3.2.1、队列的基本概念

（1）队列的定义
队列（Queue）简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。其操作的特性是先进先出（First In First Out，FIFO），如图3.5所示。

队头（Front）。允许删除的一端，又称队首。
队尾（Rear）。允许插入的一端。
空队列。不含任何元素的空表。

（2）队列的特性
队列的特点概括起来就是先进先出（FIFO）。队列就好像开进隧道的一列火车，各节车厢就是队中的元素，最先开进隧道的车厢总是最先驶出隧道。

（3）队列的存储结构
队列可用顺序表和链表来存储，队列按存储结构可分为顺序队和链队两种存储结构。

（4）队列的基本操作

InitQueue（&Q）：初始化队列，构造一个空队列Q。

QueueEmpty（Q）：判队列空，若队列Q为空返回true，否则返回false。

EnQueue（&Q，x）：入队，若队列Q未满，将x加入，使之成为新的队尾。

DeQueue（&Q，&x）：出队，若队列Q非空，删除队头元素，并用x返回。

GetHead（Q，&x）：读队头元素，若队列Q非空，则将队头元素赋值给x。

3.2.2、队列的顺序存储结构

（1）队列的顺序存储
队列的顺序存储实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置。
队列的顺序存储类型定义：

#define  Maxsize  50  //定义队列中元素的最大个数
typedef  struct{
	Elemrype  data[MaxSize]；// 存放队列元素
	int  front;  // 队头指针
	int  rear;/ / 队尾指针
} SqQueue；
1
2
3
4
5
6

初始状态（队空条件）：Q.front==Q.rear==0。
进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。
出队操作：队不空时，先取队头元素值，再将队头指针加1。

图3.6（a）所示为队列的初始状态，有Q.front==Q.rear==0成立，该条件可以作为队列判空的条件。但能否用Q.rear==Maxsize作为队列满的条件呢？显然不能，图3.6（d）中，队列中仅有一个元素，但仍满足该条件。这时入队出现“上溢出”，但这种溢出并不是真正的溢出，在data数组中依然存在可以存放元素的空位置，所以是一种“假溢出”。

（2）循环队列
将顺序队列想象为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。当队首指针Q.front=MaxSize-1后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。
初始时：Q.front=Q.rear=0。
队首指针进1：Q.front=（Q.front+1）%MaxSize。
队尾指针进1：Q.rear=（Q.rear+1）%Maxsize。
队列长度：（Q.rear+Maxsize-Q.front）%MaxSize。
出队入队时：指针都按顺时针方向进l（如图3.7所示）。

区分循环队列队空和队满的情况，有三种处理方式：
1）牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法，约定以“队头指针在队尾指针的下一位置作为队满的标志”，如图3.7（d2）所示。
队满条件：（Q.rear+1）%Maxsize==Q.front。
队空条件仍：Q.front==Q.rear。
队列中元素的个数：（Q.rear-Q.front+MaxSize）Maxsize。
2）类型中增设表示元素个数的数据成员。这样，队空的条件为Q.size==0；队满的条件为Q.size==MaxSize。这两种情况都有Q.front==Q.rear。
3）类型中增设tag数据成员，以区分是队满还是队空。tag等于0时，若因删除导致Q.front==Q.rear，则为队空；tag等于1时，若因插入导致Q.front==Q.rear，则为队满。

（3）循环队列的操作

1）循环队列初始化

Void  InitQueue（SqQueue  &Q）{
	Q.rear=Q.front=0；// 初始化队首、队尾指针
}
1
2
3

2）判断循环队列是否为空

Bool  isEmpty（SqQueue  Q）{
	if（Q.rear==Q.front）
		return  true； // 循环队列为空，返回true
	else 
		return  false；  // 循环队列不为空，返回false
}
1
2
3
4
5
6

3）循环队列入队操作

Bool   EnQueue（SqQueue  &Q，ElemType  x）{
	if（(Q.rear+1）%MaxSize==Q.front）
		return false；// 循环队列已满，返回false
	Q.data[Q.rear]=x；//将x赋值给队尾元素
	Q.rear=（Q.rear+1）%Maxsize； ∥队尾指针加1取模
	return true；  // 循环队列入队成功，返回true
}
1
2
3
4
5
6
7

4）循环队列出队操作

Bool  DeQueue（SqQueue  &Q，ElemType  &x）{
	if（Q.rear==Q.front）
		return  false;  //循环队列为空，返回false
	x=Q.data[Q.front]； // 将队头元素赋值给x 
	Q.front=（Q.front+1）%Maxsize；//队头指针加1取模
	return true； // 循环队列出队成功，返回true
}
1
2
3
4
5
6
7

3.2.3、队列的链式存储结构

（1）队列的链式存储
队列的链式存储结构表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。
队列的链式存储结构如图3.8所示。

队列的链式存储类型定义：

typedef  struct {    //链式队列结点
	ElemType  data;  // 数据域
	struct  LinkNode  *next；// 指针域
} LinkNode;   // 链式队列队结点类型定义
1
2
3
4

typedef  struct{  // 链式队列
	LinkNode  *front;  // 队列的队头指针
	LinkNode  *rear；// 队列的队尾指针
}  LinkQueue;  // 链式队列类型定义
1
2
3
4

当Q.front==NULL且Q.rear==NULL时，链式队列为空。
出队时，需要先判断队是否为空，若不为空，则取出队头元素，将其从链表中摘除，并让Q.front指向下一个结点（若该结点为最后一个结点，则置Q.front和Q.rear都为NULL）。入队时，建立一个新结点，将新结点插入到链表的尾部，并改让Q.rear指向这个新插入的结点（若原队列为空队，则令Q.front也指向该结点）。
通常将链式队列设计成一个带头结点的单链表，这样插入和删除操作就统一了，如图3.9所示。

单链表表示的链式队列适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。

（2）链式队列的基本操作

1）链式队列初始化

Void  InitQueue（LinkQueue  &Q）{
	Q.front=Q.rear=（LinkNode*）malloc（sizeof（LinkNode））;  // 建立头结点
	Q.front->next=NULL； // 初始为空
}  
1
2
3
4

2）判断链式队列是否为空

Bool  IsEmpty（LinkQueue  Q）{
	if（Q.fronta=Q.rear）
		return  true;  //链式队列为空，返回true
	else
		return  false;  //链式队列不为空，返回false
}
1
2
3
4
5
6

3）入队

void  EnQueue（Linkeueue  &Q，Elemrype  x）{
	LinkNode  *s=（LinkNode*）malloc（sizeof（LinkNode））；
	s->data=x；             
	s->next=NULL；//创建新结点，插入到链尾
	Q.rear->next=s；Q.rear=s；
}
1
2
3
4
5
6

4）出队

Bool  DeQueue（LinkQueue  &Q，Elemrype  &x）{
	if（Q.front==Q.rear）
		return false； //空队
	LinkNode  *p=Q.front->next；
	x=p->data；
	Q.front->next=p->next；
	if（Q.rear==p）
		Q.rear=Q.front；/若原队列中只有一个结点，删除后变空
	free（p）；
	return  true；
}
1
2
3
4
5
6
7
8
9
10
11

3.2.4、双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列，如图3.10所示。其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。

在双端队列进队时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时，无论是前端还是后端出队，先出的元素排列在后出的元素的前面。思考：如何由入队序列a，b.c.d得到出队序列d.c.a b？输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列称为输出受限的双端队列，如图3.11所示。

输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列称为输入受限的双端队列，如图3.12所示。若限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈。