王道408考研数据结构-栈、队列和数组-第三章
3.1 栈
3.1.1 栈的基本概念
1.栈的定义
栈(Stack)是只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作，如图3.1所示。
栈顶(Top)。线性表允许进行插入删除的那一端。
栈底(Bottom)。固定的，不允许进行插入和删除的另一端。
空栈。不含任何元素的空表。
3.1.2 栈的顺序存储结构
栈是一种操作受限的线性表，类似于线性表，它也有对应的两种存储方式。
1.顺序栈的实现
采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针(top)指示当前栈顶元素的位置。
栈的顺序存储类型可描述为：
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.顺序栈的基本操作
栈操作的示意图如图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;
}(2)判栈空
bool StackEmpty(SqStack S){if(s.top==-1)return true;elsereturn false;
}(3)进栈
bool Push(SqStack &S,ElemType x)(if(S.top==MaxSize-1)//栈满，报销 return false;S.data[++S.top]=x;//指针先加1,再入栈 return true;
)(4)出栈
bool Pop(SqStack &S,ElemType &x){if(S.top==-1)//栈空，报错 return false;x=S.data[S.top--];//先出栈，指针再减1return true;
}(5)读栈顶元素
bool GetTop(SqStack S,ElemType &x){if(S.top==-1)//栈空，报错return false;x=S.data[S.top];return true;//x 记录栈顶元素
}3.共享栈
利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，如图3.3 所示。
3.1.3 栈的链式存储结构
采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点，Lhead 指向栈顶元素，如图3.4所示。
栈的链式存储类型可描述为
typedef struct Linknode{ElemType data; //数据域struct Linknode *next;//指针域
}LiStack;采用链式存储，便于结点的插入与删除。链栈的操作与链表类似，入栈和出栈的操作都在链表的表头进行。需要注意的是，对于带头结点和不带头结点的链栈，具体的实现会有所不同。
3.2 队列
3.2.1队列的基本概念
1.队列的定义
队列(Queue)简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。这和我们日常生活中的排队是一致的，最早排队的也是最早离队的，其操作的特性是先进先出(First In First Out,FIFO),如图 3.5 所示。
队头(Front)。允许删除的一端，又称队首。
队尾(Rear)。允许插入的一端。
空队列。不含任何元素的空表。
3.2.2 队列的顺序存储结构
1.队列的顺序存储
队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置(不同教材对front和rear的定义可能不同，例如，可以让rear指向队尾元素、front 指向队头元素。)
队列的顺序存储类型可描述为
#define MaxSize 50
typedef struct{ElemType data[MaxSize]; //用数组存放队列元素int front,rear; //队头指针和队尾指针
}SqQueue;初始时：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)8MaxSize。
- 队尾指针进1:Q.rear=(Q.rear+1)8MaxSize。
- 队列长度：(Q.rear+MaxSize-Q.front)8MaxSize。
- 出队入队时：指针都按顺时针方向进1(如图3.7所示)。
那么,循环队列队空和队满的判断条件是什么呢?显然，队空的条件是Q.front==Q.rear。若入队元素的速度快于出队元素的速度，则队尾指针很快就会赶上队首指针，如图3.7(d1)所示，此时可以看出队满时也有Q.front==Q.rear。循环队列出入队示意图如图3.7所示。
为了区分是队空还是队满的情况，有三种处理方式：
1) 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法， 约定以“队头指针在队尾指针的下一位置作为队满的标志”,如图3.7(d2)所示。
队满条件：(Q.rear+1)8MaxSize==Q.front。
队空条件：Q.front==Q.rear。
队列中元素的个数：(Q.rear-Q.front+MaxSize)8MaxSize。
2) 类型中增设size数据成员，表示元素个数。删除成功 size减1,插入成功 size加1。
队空时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.2.3队列的链式存储结构
1.队列的链式存储
队列的链式表示称为链队列，它实际上是一个同时有队头指针和队尾指针的单链表，如图3.8所示。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。
队列的链式存储类型可描述为
typedef struct LinkNode{ElemType data;struct LinkNode *next;
}LinkNode;
typedef struct{ //链式队列LinkNode *front,*rear;
}LinkQueue;3.2.4 双端队列
双端队列是指允许两端都可以进行插入和删除操作的线性表，如图3.10所示。双端队列两端的地位是平等的，为了方便理解，将左端也视为前端，右端也视为后端。
在双端队列进队时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时，无论是前端还是后端出队，先出的元素排列在后出的元素的前面。
输出受限的双端队列， 许在一端进行插入和删除，但在另一端只允许插入的双端队列称为输出受限的双端队列，如图3.11所示。
输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列称为输入受限的双端队列，如图3.12所示。若限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈。
