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