【笔记】数据结构_栈和队列
本帖最后由 sphao 于 2017-10-19 20:57 编辑**【概要】**
+ （一）栈和队列的基本概念
+ （二）栈和队列的顺序存储结构T
+ （三）栈和队列的链式存储结构
+ （四）栈和队列的应用
+ （五）特殊矩阵的压缩存储
---
## 栈
### 栈的基本概念
#### 栈的定义
**栈(Stack)：**只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但是限定这种线性表只能在某一端进行插入和删除操作。
**栈顶(top)：**线性表允许进行插入和删除的那一端。
**栈底(bottom)：**固定的，不允许进行插入和删除的另一端。
**空栈：**不含任何元素的空表。
假设某个栈S= (a1, a2, a3, a4, a5)，如图所示，则a1为栈底元素，a5为栈顶元素。由于栈只能在栈顶进行插入和删除操作，故进栈次序依次为a1、a2、a3、a4、a5，而出栈次序为a5、a4、a3、a2、al。由此可见，栈的一个明显的操作特性可以概括为**后进先出**(Last In First Out, **LIFO**)，故又称为后进先出的线性表。
#### 栈的基本操作
InitStack(&S)：初始化一个空栈S。
StackEmpty(S)：判断一个栈是否为空，若栈S为空返回true，否则返回false。
Push(&S, x)：进栈，若栈S未满，将x加入使之成为新桟顶。
Pop(&S, &x)：出栈，若栈S非空，弹出栈顶元素，并用x返回。
GetTop(S, &x)：读栈顶元素，若栈S非空，用x返回栈顶元素。
ClearStack(&S)：销毁栈，并释放栈S占用的存储空间。
---
### 栈的顺序存储结构
#### 顺序栈的实现
栈的顺序存储称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据 元素，同时附设一个指针(top)指示当前栈顶的位置。
栈的顺序存储类型描述：
```
#define MaxSize 50//定义栈中元素的最大个数
typedef struct{
Elemtype data;//存放找中元素
int top;// 栈顶指针
}SqStack
```
栈顶指针：S.top，初始时设置S.top=-1；栈顶元素：S.data。
进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。
出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1。
栈空条件：S.top=-1；栈满条件：S.top==MaxSize-1；栈长：S.top+1。
由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能 发生栈上溢，此时应及时向用户报告消息，以便及时处理，避免出错。
---
#### 顺序栈的基本运算
+ 初始化：
```
void InitStack(&S){
s.top=-1;//初始化栈顶指针
}
```
+ 判栈空
```
bool StackEmpty(S){
if(s.top==-1)//栈空
return true;
else//不空
return false;
}
```
+ 进栈
```
bool Push(SqStack &S, ElemType x) {
if(S.top==MaxSize-1)//栈满，报错
return false;
S.data[++S.top] = x;//指针先加 1，再入栈
return true;
}
```
+ 出栈
```c
bool Pop(SqStack &S, ElemType &x){
if(S.top==-1)// 栈空，报错
return false;
x=S.data ;//先出栈，指针再减1
return true;
}
```
+ 读栈顶元素
```c
bool GetTop(SqStack S,ElemType &x){
if (S.top==-1)//找空，报错
return false;
x=S.data;//x记录栈顶元素
return true;
}
```
**注意：**这里栈顶指针指向的就是栈顶元素，所以进栈时的操作是S.data[++S.top]=x，出栈时的操作是x=S.data。如果栈顶指针初始化为S.top=0，即栈顶指针指向栈顶元素 的下一个位置，则入栈操作变为S.data=x，出栈操作变为x=S.data[--S.top]。相应的 栈空、栈满条件也会发生变化。
#### 共享栈
利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的 栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
两个栈的栈顶指针都指向栈顶元素，top0=-1 时0号桟为空，top1=MaxSize时1号栈为 空；仅当两个栈顶指针相邻**(top1-top0=1) 时**，判断为**栈满**。当0号栈进栈时top0先加1 再赋值，1号栈进栈时top1先减1再赋值；出栈时则刚好相反。
共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被 占满时才发生上溢。其存取数据的时间复杂度均为O(1)，所以对存取效率没有什么影响。
---
### 栈的链式存储结构
釆用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且 不存在栈满上溢的情况。通常釆用单链表实现，并规定所有操作都是在单链表的表头进行的。 这里规定链栈没有头结点，Lhead指向栈顶元素。
栈的链式存储类型：
```c
typedef struct Linknode{
ElemType data;//数据域
struct Linknode *next;//指针域
} *LiStack;//栈类型定义
```
## 队列
### 队列的基本概念
#### 队列的定义
队列(Queue)：队列简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。
这和我们日常生活中的排队是一致的，最早排队的也是最早离队的。其操作的特性是**先进先出** (First In First Out, **FIFO**)，故又称为先进先出的线性表。
队头(Front)：允许删除的一端，又称为队首。
队尾(Rear)：允许插入的一端。
空队列：不含任何元素的空表。
#### 队列常见的基本操作
InitQueue(&Q)：初始化队列，构造一个空队列Q。
QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
EnQueue(&Q, x)：入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue(&Q, &x)：出队，若队列Q非空，删除队头元素，并用x返回。
GetHead(Q, &x)：读队头元素，若队列Q非空，则将队头元素赋值给X。
需要注意的是，队列是操作受限的线性表，所以，不是任何对线性表的操作都可以作为队列的操作。比如，不可以随便读取队列中间的某个数据。
### 队列的顺序存储结构
####队列的顺序存储
队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针front 和rear分别指示队头元素和队尾元素的位置。设队头指针指向队头元素，队尾指针指向队尾 元素的下一个位置（也可以让rear指向队尾元素，front指向队头元素的前一个位置）。
队列的顺序存储：
```c
#define MaxSize 50//定义队列中元素的最大个数
typedef struct{
ElemType data;//存放队歹I]元素
int front, rear;//队头指针和队尾指针
}SqQueue;
```
初始状态（队空条件）：Q.front==Q.rear==0。
进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。
出队操作：队不空时，先取队头元素值，再将队头指针加1。
如图(a)所示为队列的初始状态，有Q.front==Q.rear==0成立，该条件可以作为队 列判空的条件。但能否用Q.rear==MaxSize作为队列满的条件呢？显然不能，图(d)中， 队列中仅有1个元素，但仍满足该条件。这时入队出现“上溢出”，但这种溢出并不是真正 的溢出，在data数组中依然存在可以存放元素的空位置，所以是一种“假溢出”。
####循环队列
前面已指出了顺序队列的缺点，这里我们引出循环队列的概念。将顺序队列臆造为一个 环状的空间，即把存储队列元素的表从逻辑上看成一个环,称为循环队列。当队首指针Q.ftont =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
出队入队时：指针都按顺时针方向进1 (如图所示)
那么，循环队列队空和队满的判断条件是什么呢？显然，队空的条件是Q.front==Q.rear。 如果入队元素的速度快于出队元素的速度，队尾指针很快就赶上了队首指针，如图(d1)，此时可以看出队满时也有Q.front==Q.rear。循环队列出入队示意图如图所示。
为了区分队空还是队满的情况，有三种处理方式：
**1)** 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的 做法，约定以“队头指针在队尾指针的下一位置作为队满的标志”，如图(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则为队满。
####循环队列的操作
+ 初始化
```
void InitQueue(&Q){
Q.rear=Q.front=0;//初始化队首、队尾指针
}
```
+ 判队空
```
bool isEmpty(Q) {
if(Q.rear == Q.front) return true;//队空条件
else return false;
}
```
+ 入队
```
bool EnQueue(SqQueue &Q, ElemType x){
if((Q.rear+1)%MaxSize == Q.front) return false; //队满
Q.data=x;
Q.rear= (Q.rear+1)%MaxSize; //队尾指针加 1 取模
return true;
}
```
+ 出队
```
bool DeQueue(SqQueue &Q, ElemType &x){
if(Q.rear == Q.front) return false;//队空，报错
x=Q.data;
Q.front= (Q.front+1)%MaxSize;//队头指针加 1 取模
return true;
}
```
---
### 队列的链式存储结构
#### 队列的链式存储
队列的链式表示称为链队列，它实际上是一个同时带队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表最后一个结点。 SupKevin 发表于 2017-10-20 11:59
楼主有博客吗，可以互相加一下友链
没空弄呢。。等明年看看有没有空 棒棒哒！！ 要完整版笔记 内容很详细 最近课刚好上到这哇 不错谢谢分享 感谢楼主分享 和我这学期学的数据结构进度一样哎！感谢LZ 一看就是大佬。。财务专业表示完全看不懂。 感谢楼主的这篇文章
页:
[1]
2