第3章 栈和队列1-栈.ppt

第3章栈和队列-栈
主讲教师
艾彦迪
数据结构讲义
栈(stack)
一、栈的定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶,表头—栈底,不含元素的空表称空栈
特点:先进后出(FILO)或后进先出(LIFO)
an
a1
a2
……...
栈底
栈顶
...
出栈
进栈
栈s=(a1,a2,……,an)
栈的基本操作
:INISTACK(&S)
将栈S置为一个空栈(不含任何元素)。
:PUSH(&S,X)
将元素X插入到栈S中,也称为“入栈”、“插入”、“压入”。
: POP(&S)
删除栈S中的栈顶元素,也称为”退栈”、“删除”、“弹出”。
: GETTOP(S,&e)
取栈S中栈顶元素。
: StackEmpty(S)
判断栈S是否为空,若为空,返回值为true,否则返回值为false。
栈的操作演示
问题
一个栈的输入序列是12345,若在入栈的过程中允许出栈,则栈的输出序列43512可能实现吗?12345的输出呢?
43512不可能实现,主要是其中的12顺序不能实现;
12345的输出可以实现,只需压入一个立即弹出一个即可。
栈的应用:数制转换
如十进制数N转换成d进制数C:
dn + cn-1dn-1 +…+ c1d1+ c0
C=(-1 … c0)
例如:
(14)10= 1*23 + 1*22 + 1*21 + 0 =(1110)2
(1348)10=2*83 + 5*82 + 0*81 + 4 =(2504)8
(1348)10=2*83 + 5*82 + 0*81 + 4 =(2504)8
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
最后得到的“2”最先输出:2504
栈的应用:表达式计算
例如:3*(7 – 2 )
(1)要正确求值,首先了解算术四则运算的规则:
a. 从左算到右
b. 先乘除,后加减
c. 先括号内,后括号外
由此,此表达式的计算顺序为:
3*(7 – 2 )= 3 * 5 = 15
(2)根据上述三条运算规则,在运算的每一步中,对任意相继出现的运算符1和2 ,都要比较优先权关系。
栈的顺序实现
顺序栈的类型定义如下:
# define StackSize 100
typedef struct {
ElemType data[StackSize];
int top;
}SqStack;
顺序栈的操作演示flash
top指向栈顶的上一个元素。
top==0表示空栈。
top== StackSize-1表示栈满。
当栈满时再做进栈运算必定产生空间溢出,简称“上溢”;当栈空时再做退栈运算也将产生溢出,简称“下溢”。
上溢是一种出错状态,应该设法避免之;下溢一般是正常现象,常常用来作为程序控制转移的条件。