数据结构-3、栈、队列和数组

3.1、栈

3.1.1、栈的基本概念：

1、栈的定义：

栈是只允许在一端进行插入或删除操作的线性表。首先，栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作，如下图：

在这里插入图片描述

栈顶（Top）。线性表允许进行插入删除的那一端。

栈底（Bottom）。固定的，不允许进行插入和删除的另一端。

空栈。不包含任何元素的空表。

假设某个栈 $S=(a_1,a_2,a_3,a_4,a_5)$ ，如上图所示，则 $a_1$ 为栈底元素， $a_5$ 为栈顶元素。由于栈只能在栈顶进行插入和删除操作，进栈次序依次为 $a_1,a_2,a_3,a_4,a_5$ ，而出栈次序则与入栈次序相反。由此可见，栈的操作特性可以明显地概括为后进先出（LIFO）。

栈的数学性质：n 个不同元素进栈，出栈元素不同排列的个数为 $\frac{1}{n+1}C^n_2n$ 。上述公式称为卡特兰数，可采用数学归纳法证明。

2、栈的基本操作：

栈的基本操作：

InitStack(&S)		//初始化一个空栈。
StackEmpty(S)		//判断一个栈是否为空，若栈 S 为空则返回 ture ，否则返回 false。
Push(&S,x)			//进栈，若栈 S 未满，则将 x 加入使之成为新栈顶。
Pop(&S,&x)			//出栈，若栈 S 非空，则弹出栈顶元素，并用 x 返回。
GetTop(S,&x)		//读取栈顶元素，若栈 S 非空，则用 x 返回栈顶元素。
DestroyStack(&S)	//销毁栈，并释放栈 S 占用的存储空间（“& 表示引用调用”）。

3.1.2、栈的顺序存储结构：

栈是一种操作受限的线性表，类似于线性表，它也有对应的两种存储方式。

1、顺序栈的实现：

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈顶到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。

栈的顺序存储类型可描述为：

#define MaxSize 50
typedef struct{Elemtype data[MaxSize];int top;
} SqStack;

栈顶指针：s.top，初始时设置 S.top=-1；栈顶元素：S.data[S.top]。

进栈操作：栈不满时，栈顶指针先加 1 ，再送值到栈顶元素。

出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减 1.

栈空条件：S.top==-1；栈满条件：S.top==MaxSize-1；栈长：S.top+1.

由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生栈上溢，此时应及时向用户报告信息，以便及时处理，避免出错。

2、顺序栈的基本运算：

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

在这里插入图片描述

下面是顺序栈上常用的基本运算实现：

#include "stdio.h"#define MaxSize 50typedef struct{int data[MaxSize];int top;
} SqStack;void InitStack(SqStack *S);
int StackEmpty(SqStack *S);
int Push(SqStack *S,int x);
int Pop(SqStack *S,int *x);
int GetTop(SqStack *S,int *x);int main(){SqStack S;int x;InitStack(&S);for (int i = 1;i <= 6;i++){Push(&S,i);}if(GetTop(&S,&x))printf("%d",x);
}//初始化栈
void InitStack(SqStack *S){S->top = -1;
}//判断栈是否为空
int StackEmpty(SqStack *S){if (S->top == -1)return 1;elsereturn 0;
}//入栈操作
int Push(SqStack *S,int x){if(S->top == MaxSize -1)return 0;S->data[++S->top] = x;return 1;
}//出栈操作
int Pop(SqStack *S,int *x){if(S->top == -1)return 0;*x = S->data[S->top--];return 1;
}//读取栈顶元素
int GetTop(SqStack *S,int *x){if(S->top == -1)return 0;*x = S->data[S->top];return 1;
}

3、共享栈：

利用栈底位置相对不变的特性，可让两个顺序栈共享一个以为数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间眼神，如下图：

在这里插入图片描述

两个栈的栈顶指针都指向栈顶元素，top0=-1 时 0 号栈为空，top1=MaxSize 时 1 号栈为空；仅当两个栈顶指针相邻（top0-top1=1）时，判断为栈满。当 0 号栈进栈时 top0 先加 1 再赋值，1 号栈进栈时 top1 先减 1 再赋值；出栈时则刚好相反。

共享栈时为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度为 O(1) ，所以对存取效率没有什么影响。

3.1.3、栈的链式存储结构：

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

在这里插入图片描述

栈的链式存储类型可描述为：

typedef struct Linknode{ElemType data;struct LinkNode *next;
} *LiStack;

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

3.2、队列;

3.2.1、队列的基本概念：

1、队列的定义：

队列，也是一种操作受限的线性表，只允许在表的一端进行插入，而表的另一端进行删除。向队列中插入元素成为入队或进队；删除元素称为出队或离队。这和我们日常生活中的排队时一致的，最早排队的也是最早离队的，其操作的特性是先进先出（FIFO），如下图：

在这里插入图片描述

对头。允许删除的一端，又称队首。

队尾。允许插入的一端。

空队列。不含任何元素的空表。

2、队列常见的基本操作：

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{ElemType data[MaxSize];int front,rear;
} SqQueue;

初始时：Q.front = Q.rear = 0。

进队操作：队不满时，先送值到队尾元素，再将队尾指针加 1。

出队操作：队不空时，先取队头元素值，再将队头指针加 1.

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

在这里插入图片描述