top top 栈空 F E D C B A
栈满 top-base=stacksize
top
F
E
D C B
top top top top top top base
入栈PUSH(s,x):s[top++]=x; top 出栈 POP(s,x):x=s[--top]; top
base
4
A
3.1 栈
例1:一个栈的输入序列为1,2,3,若在入栈的过程中 允许出栈,则可能得到的出栈序列是什么? 答: 可以通过穷举所有可能性来求解:
3.2 栈的应用举例
二、表达式求值
“算符优先法”
一个表达式由操作数、运算符和界限符组成。 # 例如:3*(7-2*3) (1)要正确求值,首先了解算术四则运算的规则 a.从左算到右 b.先乘除后加减 c.先括号内,后括号外 所以,3*(7-2*3)=3*(7-6)=3*1=3
9
3.2 栈的应用举例
InitStack(S); while (!QueueEmpty(Q))
{DeQueue(Q,d);push(S,d);}
while (!StackEmpty(S)) {pop(S,d);EnQueue(Q,d);} }
第3章 栈和队列
教学要求:
1、掌握栈和队列的定义、特性,并能正确应用它们解决实 际问题;
用一组地址连续的存储单元依次存放从队头到队尾的元素, 设指针front和rear分别指示队头元素和队尾元素的位置。
Q.rear 5 4 Q.rear 3 2 3 2 5 4 Q.rear 3 3 5 4 5 4
F E D C
C B A
Q.front
2 1 0
C B
Q.front 2 1 0