文档介绍：——是限定仅在表尾进行插入或删除操作的线性表。栈顶——表尾。栈底——表头。空栈——不含元素的空表。…a1a2an栈底栈顶进栈出栈栈s=(a1,a2,…,an)后进先出(LIFO)栈和队列2、什么是队列定义:一种特殊的线性结构,限定只能在表的一端进行插入,在表的另一端进行删除的线性表。此种结构称为先进先出(FIFO)表。a1,a2,a3,a4,…………an-1,an队列示意图队头队尾e3e4(c)e1,e2出队,e4入队队满rear=3fronte1e2e3(b)rearfront(b)e1,e2,e3入队(a)rear=front=-1(队空)rearfront空队列:非空队列:队列元素个数:rear=front=-1front始终指向队头元素前一个位置,而rear始终指向队尾元素的位置rear-front2、循环队列及其运算基本思想:把队列设想为一个循环的表,实现首尾相连。……frontrearMaxsize-101e3e4rear=3front0012345frontABCDEFrear上溢0012345frontrear下溢front=rear队满front=“满”队列“空”=?????队列的顺序存储循环队列解决方法:一是为队列另设一个标志s,用来区分队列是“空”还是“满”s=0队空,s=1队满;二是少用一个元素空间,当队列头指针在队列尾指针的下一个单元时就认为队“满”。此时,队尾指针只差一步追上队头指针。即:本教材用第一种方法。判空条件:==0判满条件:==1方法一队列元素=(尾指针-头指针+队列容量)%队列容量(-+MAXQSIZE)%MAXSIZE方法二1).尾指针大于头指针:元素个数=尾指针-头指针设某循环队列的容量为50,头指针front=5(指向队头元素的前一位置),尾指针rear=29(指向队尾元素),则该循环队列中共有多少个元素。元素个数=尾指针-头指针=29-5=242).头指针大于尾指针:元素个数=总容量-头指针+尾指针设某循环队列的容量为50,如果头指针front=45(指向队头元素的前一位置),尾指针rear=10(指向队尾元素),则该循环队列中共有多少个元素。元素个数=总容量-头指针+尾指针=50-45+10=15队列元素个数计算栈和队列的共同特点是A)都是先进先出B)都是先进后出C)只允许在端点处插入和删除元素D)没有共同点如果进栈序列为e1,e2,e3,e4,则可能的出栈序列是A)e3,e1,e4,e2 B)e2,e4,e3,e1C)e3,e4,e1,e2 D)任意顺序一些重要的程序语言(如C语言和Pascal语言)允许过程的递归调用。而实现递归调用中的存储分配通常用A)栈 B)堆C)数组 D)链表例题讲解栈底至栈顶依次存放元素A、B、C、D,在第五个元素E入栈前,栈中元素可以出栈,则出栈序列可能是A)ABCED B)DCBEAC)DBCEA D)CDABE栈通常采用的两种存储结构是A)线性存储结构和链表存储结构 B)散列方式和索引方式C)链表存储结构和数组D)线性存储结构和非线性存储结构栈和队列通常采用的存储结构是【1】。下列数据结构中,按先进后出原则组织数据的是A)线性链表B)栈C)循环链表 D)顺序表▽当循环队列非空且队尾指针等于队头指针时,说明循环队列已满,不能进行入队运算。这种情况称为【2】。链表存储结构和数组上溢