文档介绍：数据结构涵盖的内容:
栈(Stack) 队列(Queue)
第三章栈和队列
1. 定义
2. 逻辑结构
3. 存储结构
4. 运算规则
5. 实现方式
1. 定义
2. 逻辑结构
3. 存储结构
4. 运算规则
5. 实现方式
1. 定义
栈
与线性表相同,仍为一对一( 1:1)关系。
用顺序栈或链栈存储均可,但以顺序栈更常见
只能在栈顶运算,且访问结点时依照后进先出(LIFO)或先进后出(FILO)的原则。
关键是编写入栈和出栈函数,具体实现因顺序栈或链栈的存储结构有别而不同。
3. 存储结构
4. 运算规则
5. 实现方式
2. 逻辑结构
限定只能在表的一端进行插入和删除运算的线性表。
即栈顶
基本操作有:建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值,等等。
栈是仅在表尾进行插入、删除操作的线性表。
表尾(即 an 端)称为栈顶/top ; 表头(即 a1 端)称为栈底/base
例如: 栈 S= (a1 , a2 , a3 , ……….,an-1 , an )
插入元素到栈顶的操作,称为入栈。
从栈顶删除最后一个元素的操作,称为出栈。
an称为栈顶元素
a1称为栈底元素
想一想:要从栈中取出a1,应当如何操作?
强调:插入和删除都只能在表的一端(栈顶)进行!
例1()一个栈的输入序列为1,2,3,若在入栈的过程中允许出栈,则可能得到的出栈序列是什么?
答:
可以通过穷举所有可能性来求解:
① 1入1出, 2入2出,3入3出, 即123;
② 1入1出, 2、3入,3、2出, 即132;
③ 1、2入,2出, 3入3出, 即231;
④ 1、2入,2、1出,3入3出, 即213;
⑤ 1、2、3入,3、2、1出, 即321;
合计有5种可能性。
例2:一个栈的输入序列是12345,若在入栈的过程中允许出栈,则栈的输出序列43512可能实现吗?12345的输出呢?
答:
43512不可能实现,主要是其中的12顺序不能实现;
12345的输出可以实现,每压入一数便立即弹出即可。
例3:
设依次进入一个栈的元素序列为c,a,b,d,则可得到出栈的元素序列是:
A)a,b,c,d B)c,d,a,b C)b,c,d,a D)a,c,d,b
A)、D)可以, B)、C)不行。
讨论:有无通用的判别原则?
有!若输入序列是…,Pj…Pk…Pi …(Pj<Pk<Pi) ,一定不存在这样的输出序列…,Pi…Pj…Pk …
答:
即对于输入序列1,2,3,不存在输出序列3,1,2
计算机系2001年考研题
Q1:堆栈是什么?它与一般线性表有什么不同?
堆栈是一种特殊的线性表,它只能在表的一端(即栈顶)进行插入和删除运算。
与一般线性表的区别:仅在于运算规则不同。
一般线性表堆栈
逻辑结构:1:1 逻辑结构: 1:1
存储结构:顺序表、链表存储结构:顺序栈、链栈
运算规则:随机存取运算规则:后进先出(LIFO)
“进”=插入=压入=PUSH(an+1)
“出”=删除=弹出=POP(an)
a1
a2
……
an
顺序栈S
ai
……
Q2:顺序表和顺序栈的操作有何区别?
表头
表尾
低地址
高地址
写入:S[i]= ai
读出: e= S[i]
压入(PUSH): S[top++]=an+1
弹出( POP) : e=S[--top]
低地址
高地址
S[i]
a1
a2
ai
an
……
顺序表S
……
an+1
以线性表 S= (a1 , a2 , …. , an-1 , an )为例
栈底base
栈顶top
前提:一定要预设栈顶指针top
栈顶top
栈不存在的条件: base=NULL;
栈为空的条件: base=top;
栈满的条件: top-base=stacksize;
a1
a2
……
an
顺序栈S
ai
……
低地址
高地址
栈底base
栈顶top