数据结构【栈和队列】

第三章 栈与队列

一、栈
1.定义：只允许一端进行插入和删除的线性表，结构与手枪的弹夹差不多，可以作为实现递归函数（调用和返回都是后进先出）调用的一种数据结构；

• 栈顶：允许插入删除的那端；
• 栈底：固定的，不允许插入或删除；
• 空栈：不含元素；

2.特点：后进先出；
3.操作：入栈（push）、出栈（pop）
4.应用：递归、进制转换、迷宫求解、括号匹配。
5.栈的顺序存储（顺序栈）

• 定义：利用一组地址连续的存储单位存放自栈底到栈顶的数据元素，同时用一指针指示栈顶位置；
• 栈顶指针：S.top，初始值=-1，栈顶元素S.data[S.top]； 进栈操作：栈不满时，栈顶指针+1，再送栈到栈顶元素；
• 出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针-1；
• 栈空条件：S.top=-1；栈满条件：S.top==MaxSize-1；栈长：S.top+1。
  6.共享栈
• 定义：两共享栈共享一个一维数组空间，两个栈顶指针都指向栈顶元素，top=-1时0号栈为空，top1=MaxSize时1号栈为空；当两栈指针相邻top1-top0=1时，满栈；共享栈是为了更好的利用存储空间，两个栈的空间相互调节，只有整个存储空间都被占满时才发生上溢。
  

7.链栈

• 定义：采用链式存储的栈，便于多个栈共享存储空间和提高效率，且不存在栈满上溢问题，采用单链表实现，所有操作都在单链表表头进行，操作与链表相似；

二、队列
1.定义：简称队，一种操作受限制的线性表，只允许在表的一端插入，在表另一端删除。

• 队头：允许删除的一端，队头指针指向队头元素；
• 队尾：允许插入的一端，队尾指针指向队尾元素下一个位置；
• 空队列：无元素 ；
• 初始条件（队空条件）：Q.frontQ.rear0，front队头，rear队尾;
• 假溢出：一维数组队列的尾指针已达到数组上界，不能入队，其实数组中还有空位置；

2.特点：先进先出（怎么进怎么出）；
3.应用：缓冲区、页面替换算法；
4.操作：进队（队不满时，先送值到队尾元素，队尾指针+1）；出队（队不空时，先取队头元素值，队头指针+1）；
5.循环队列：把存储队列元素的表从逻辑上看成一个环，循环队列的引入是为了防止假溢出；

• 初始时：Q.front=Q.rear=0;
• 队首指针进1（出队）：Q.front=(Q.front+1)%MaxSize;
• 队尾指针进1（入队）：Q.rear=(Q.rear+1)%MaxSize;
• 队列长度（队列中元素个数）：(Q.rear-Q.front+MaxSize)%MaxSize【(尾-头+M)%M】；
• 队空：Q.frontQ.rear0；
• 队满：(Q.rear+1)%MaxSize==Q.front；
• 出队入队指针按顺时针进1；
• 例题：循环队列存储在数组A[0…n]中，则入队操作为rear=(rear+1)mod(n+1)。
  6.链队列：同时带队头指针和队尾指针的单链表，无假溢出现象；
  

7.双端队列：允许两边都可以入队和出队。