数据结构c语言版栈和队列（精）.ppt

学习目标与重点 ◆理解栈和队列的定义、特点； ◆掌握栈和队列的各种存储结构； ◆重点掌握在顺序栈和链栈上实现进栈、出栈、判栈空和判栈满等基本操作； ◆重点掌握在循环队列中实现进队列、出队列、判队列空和判队列满等基本操作； ◆了解栈和队列在计算机软件设计中的应用。 3.1 栈 3.1.1 栈的定义及其运算 3.2 算术表达式求值 3.3.1 队列的定义及其运算 3.3.2 队列的链式存储结构 3.3.3 队列的顺序存储结构 学习目标与重点 ◆理解栈和队列的定义、特点； ◆掌握栈和队列的各种存储结构； ◆重点掌握在顺序栈和链栈上实现进栈、出栈、判栈空和判栈满等基本操作； ◆重点掌握在循环队列中实现进队列、出队列、判队列空和判队列满等基本操作； ◆了解栈和队列在计算机软件设计中的应用。 本章小结 习 题 三 请指出下面的过程执行p(5)和p(6)时分别输出的结果。 void P(int n); { if n0 { p(n-2); printf(“%d”,n); } } 假定用一个循环单链表表示队列（称此为循环链队），该队列只设一个队尾指针， 不设队首指针，试编写下列算法： 向循环链队插入一个元素为x的结点； 试题库题第三章 栈和队列 栈和队列 单选题 1、在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针， 则当做退栈处理时，top变化为_____。 2、向顺序栈中压入元素时，是_____。 3、在一个顺序存储的循环队列中，队首指针指向队首元素的_____。 4、若进栈序列为1,2,3,4,进栈过程中可以出栈，则_____不可能是一个出栈序列。 1、top不变| top＝-n | top＝top-1| top=top+1 C 2、先移动栈顶指针，后存入元素| 先存入元素，后移动栈顶指针 B 3、前一个位置| 后一个位置| 队首元素位置| 队尾元素位置 C 4、3,4,2,1| 2,4,3,1| 1,4, 2, 3 | 3,2,1,4 C 栈和队列 单选题 5、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是_____。 6、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是_____。 5、front= =rear+1| front+1= =rear| front= =rear| front= =0 C 6、rear % n= =front| (rear-1) % n= =front| (rear-1) % n= =rear| (rear+1) % n= =front D 栈和队列 单选题 7、向一个栈项指针为hs的链栈中插入一个*s结点时，则执行_____。 8、在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执行_____。 7、hs-next=s;| s-next=hs-next; hs-next=s;| s-next=hs；hs=s;| s-next=hs; hs=hs-next; C 8、front-next=s; front=s;| rear-next=s; rear=s;| front=front-next;| front=rear-next; B 栈和队列 单选题 9、栈的特点是_______队