1、数据结构数据结构 李李 萍萍 第三章第三章 栈和队列栈和队列主要学习内容主要学习内容:掌握栈和队列是两种操作受限的线性表掌握栈和队列是两种操作受限的线性表掌握栈和队列的两种存储实现算法掌握栈和队列的两种存储实现算法理解递归算法执行过程中栈的变化过程理解递归算法执行过程中栈的变化过程 3.1 栈栈1.概念概念是限定仅在表尾进行插入和删除操作的线性表是限定仅在表尾进行插入和删除操作的线性表.允许插入允许插入和删除的一端为栈顶（和删除的一端为栈顶（top),另一端称为栈底（另一端称为栈底（bottom).2.图示图示一、定义一、定义an-1an-2a1a0bottomtop退栈退栈（弹出）（弹出）进
2、栈进栈（压入）（压入）3.特性特性逻辑结构：一对一逻辑结构：一对一存储结构：顺序和链式存储（顺序栈和链栈）存储结构：顺序和链式存储（顺序栈和链栈）运算规则：先进后出运算规则：先进后出基本操作：入栈、出栈、读栈顶、判栈空、判栈满基本操作：入栈、出栈、读栈顶、判栈空、判栈满等等一、定义一、定义3.1 栈栈1.顺序栈的静态定义顺序栈的静态定义#define MAXSIZE 1024 typedef struct datatype dataMAXSIZE;int top;SqStack定义一个指向顺序栈的变量：定义一个指向顺序栈的变量：SqStack sq;二、栈的表示和实现（顺序栈）二、栈的表示和实
3、现（顺序栈）3.1 栈栈2.顺序栈的基本操作顺序栈的基本操作 栈空栈空栈空：栈空：top=-1 0 栈满：栈满：top=sq.MAXSIZE-1 读栈顶元素读栈顶元素sq.datatop,top的值未变的值未变 出栈出栈sq.top-top的值改变的值改变 入栈入栈sq.top+sq.datatop=e二、栈的表示和实现（顺序栈）二、栈的表示和实现（顺序栈）3.1 栈栈3.顺序栈的动态定义顺序栈的动态定义#define MAXSIZE 1024 typedef struct datatype *base;datatype*top;int stacksize;SqStack定义一个指向顺序栈的变
4、量：定义一个指向顺序栈的变量：SqStack sq;二、栈的表示和实现（顺序栈）二、栈的表示和实现（顺序栈）3.1 栈栈4.顺序栈的基本操作顺序栈的基本操作 栈空栈空栈空：栈空：sq.top=sq.base 栈满：栈满：sq.top sq.base=sq.stacksize 读栈顶元素读栈顶元素*sq.top,top的值未变的值未变 出栈出栈sq.top-入栈入栈sq.top+*sq.top=e二、栈的表示和实现（顺序栈）二、栈的表示和实现（顺序栈）3.1 栈栈二、栈的表示和实现（链栈）二、栈的表示和实现（链栈）top空栈：空栈：top指向空指向空无栈满无栈满:因为可以分配结点因为可以分配结点
5、入栈：在栈顶进行入栈，相当于在链表头插入结点入栈：在栈顶进行入栈，相当于在链表头插入结点出栈：在栈顶进行出栈，相当于在链表头删除结点出栈：在栈顶进行出栈，相当于在链表头删除结点3.1 栈栈习题 考题：1、若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（）A、dcebfa B、cbdaefC、bcaefd D、afedcb一 选择题 1.对于栈操作数据的原则是（对于栈操作数据的原则是（）。）。A.先进先出先进先出 B.后进先出后进先出 C.后进后出后进后出 D.不分顺序不分顺序 2.一个栈的输入序列为一个栈的输入序列为12
6、3n，若输出序列的第一个元，若输出序列的第一个元素是素是n，输出第，输出第i（1=icount=M)/判队满if(q.rear+1)%M=q.front)printf(“over flow“);exit(0);q-data q-rear =x;q-rear=(q-rear+1)%M;/插入元素 xq-count+;/修改表长3.4队列队列四、循环队列的实现四、循环队列的实现2.基本操作基本操作 出队datatype dequeue(cirqueue*q)if(q-count=0)/判队空if(q.rear=q.front)printf(“queue null“);exit(0);q-front
7、=(q-front+1)%m;/删除队头元素 q-count-;/修改表长 return(q-data q-font );3.4队列队列四、循环队列的实现四、循环队列的实现2.基本操作基本操作 读队头元素datatype getqueue(cirqueue q)return(q.data q.front);3.4队列队列五、链队列五、链队列1.定义定义限制在表头删除，表尾插入的单链表。由一个头指针和一个尾指针确定链表的头和尾frontrear data link3.4队列队列五、链队列五、链队列2.语言描述语言描述 结点类型描述typedef struct node datatype data
8、;struct node*next;queuenode;头尾指针描述typedef structqueuenode*front;queuenode*rear;linkqueue;3.4队列队列五、链队列五、链队列3.图示图示(a)非空队rearfronta1ana2rearfronta1rearfront(b)空队(c)链队中只有一个元素结点 头尾指针封装在一起的链队3.4队列队列五、链队列五、链队列4.算法实现算法实现 创建一个带头结点的空队：LinkQueue *Init_LQueue()queuenode*s;linkqueue p;s=(queuenode*)malloc(sizeof
9、(queuenode);/申请结点 s-next=NULL;p.front=s;p.rear=s;return&p;3.4队列队列五、链队列五、链队列4.算法实现算法实现入队 void In_LQueue(linkqueue*q,datatype x)QNode*p;p=malloc(sizeof(QNnode);/申请新结点 p-data=x;p-next=q-rear-next;q-rear-next=p;/插入尾部 q-rear=p;/改变尾指针3.4队列队列五、链队列五、链队列4.算法实现算法实现出队int Out_LQueue(linkqueue*q,datatype *x)queu
10、ennode*p;if(Empty_LQueue(q)printf(队空)；return 0;/队空，出队失败 else p=q-front-next;q-front-next=p-next;*x=p-data;/队头元素放x中 free(p);if(q-front-next=NULL)q-rear=q-front;/只有一个元素时，出队后队空，此时还要要修改队尾指针参考 return 1;习题习题 考题：1.设栈S和队列Q的初始状态均为空，元素a，b，c，d，e，f，g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是A.1 B
11、.2 C.3 D.4习题习题 考题：2、某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺顺序是（）A、bacde B、dbaceC、dbcae D、ecbad习题习题 1.用链接方式存储的队列，在进行删除运算时（用链接方式存储的队列，在进行删除运算时（）。）。A.仅修改头指针仅修改头指针 B.仅修改尾指针仅修改尾指针 C.头、尾指针都要修改头、尾指针都要修改 D.头、尾指针可能都要修改头、尾指针可能都要修改 2.用不带头结点的单链表存储队列时用不带头结点的单链表存储队列时,其队头指针指向队其队头指针指向队头结点头结点,其队尾指针指向队尾结点，则在进行删除操作时其队尾
12、指针指向队尾结点，则在进行删除操作时()。A仅修改队头指针仅修改队头指针 B.仅修改队尾指针仅修改队尾指针 C.队头、队尾指针都要修改队头、队尾指针都要修改 D.队头队头,队尾指针都可能要修队尾指针都可能要修改改习题习题 3.假设以数组假设以数组Am存放循环队列的元素存放循环队列的元素,其头尾指针分别其头尾指针分别为为front和和rear，则当前队列中的元素个数为（，则当前队列中的元素个数为（）。）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m 17.若用一个大小为若用一个大小为6的数组来实现循环队列，且当
13、前的数组来实现循环队列，且当前rear和和front的值分别为的值分别为0和和3，当从队列中删除一个元素，再，当从队列中删除一个元素，再加入两个元素后，加入两个元素后，rear和和front的值分别为多少？的值分别为多少？()A.1和和 5 B.2和和4 C.4和和2 D.5和和1 18.若以若以1234作为双端队列的输入序列，则既不能由输入作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是的输出序列是()。A.1234 B.4132 C.4231 D.4213 1.已知链队列的头尾指针分别是已知链队列的头尾指针分别是f和和r，则将值，则将值x入入队的操作序列是队的操作序列是_。2区分循环队列的满与空，只有两种方法，它区分循环队列的满与空，只有两种方法，它们是们是_和和_。3设循环队列用数组设循环队列用数组A1.M表示，队首、队尾表示，队首、队尾指针分别是指针分别是FRONT和和TAIL，判定队满的条件为，判定队满的条件为_。习题习题谢谢谢谢!
