连续出现的两个操作数和在它 例如：Exp= a ×b + (c –d /e) ×f 们之前且仅靠它们的运算符构 前缀式(波兰式)：+ ×ab ×-c/def 成一个最小表达式 中缀式：a ×b + c –d /e ×f 后缀式（逆波兰式）：ab × cde/-f ×+
结论：1）操作数之间的相对次序不变 2）运算符的相对次序不同 3）中缀式丢失了括号信息，致使运算的次序变得不确定 4）前缀式的运算规则为： 5）后缀式的运算规则为： 运算符在式中出现的顺序恰为表达式的运算顺序
a1称为栈底元素 强调：插入和删除都只能在表 的一端（栈顶）进行！
an称为栈顶元素
插入元素到栈顶的 操作，称为入栈。 从栈顶删除最后一 个元素的操作，称 为出栈。
想一想：要从栈中取出a1， 应当如何操作？
栈的存储结构
• 顺序栈 – 实现：一维数组s[M] top top F 5 top E 4 top D 3 top 2 C
栈底
Struct SNode * next; } Node; Node *st, *p; int m=sizeof(Node);
(2) 操作
链栈 入栈 函数
Push (SElemType e) { p=(Node*)malloc(m); if(!p){上溢} else{ p->data=e; p->next=st; st=p;} }
“进”＝插入=压入=PUSH（an+1) “出”＝删除=弹出=POP(an)
Q2：顺序表和顺序栈的操作有何区别？
以线性表 S= (a1 , a2 , …. , an-1 , an )为例 顺序表S 顺序栈S 表尾 高地址 an+1 高地址 an an …… …… S[i] ai ai ……
低地址
栈顶top 栈顶top
Q1：堆栈是什么？它与一般线性表有什么不同？
堆栈是一种特殊的线性表，它只能在表的一端（即 栈顶）进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。
一般线性表 逻辑结构：1:1 存储结构：顺序表、链表 运算规则：随机存取 堆栈 逻辑结构： 1:1 存储结构：顺序栈、链栈 运算规则：后进先出(LIFO)
4. 运算规则
5. 实现方式
基本操作有：建栈、判断栈满或栈空、入栈、出栈、 读栈顶元素值，等等。
栈 是仅在表尾进行插入、删除操作的线性表。 表尾(即 an 端)称为栈顶 /top ; 表头(即 a1 端)称为栈底/base 例如： 栈 S= (a1 , a2 , a3 , ……….,an-1 , an )
栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈
data next
(1) 链栈的构造方式——以头指针为栈顶，在头指针处插入或删除. st
an an-1
栈顶
链栈中每个结点由两个域构成： data域和next域，其定义为： typedef Struct SNode{
SElemType
data;
a2 a1
每个运算符和它之前出现且仅靠它的两 个操作数构成一个最小表达式
后缀表达式求值步骤： 如何求后缀表 1、读入表达式一个字符 达式呢？ 2、若是操作数，压入栈，转4 3、若是运算符，从栈中弹出2个数，将运算结果再压入栈 4、若表达式输入完毕，栈顶即表达式值； 若表达式未输入完，转1
例 计算 4+3*5=
等价于 --s.top e=*s.to p
top
低地址L
核心语句： Pop ( ); Pop ( ); Printf( Pop () );
顺序栈出栈函数POP() status Pop( ) { if(top=L) { 下溢 } else { e=* --s.top; return(e);} }
链栈的入栈操作和出栈操作
初始条件：栈s已经存在 操作结果：若栈为空栈，则返回TRUE,否则FALSE
Push（&s,e）
初始条件：栈s已经存在且非空 操作结果：插入元素e为新的栈顶元素
StackLength（s）
初始条件：栈s已经存在 操作结果：返回栈的元素个数，即栈的长度
Pop（&s,&e）
初始条件：栈s已经存在且非空 操作结果：删除s的栈顶元素， 并用e返回其值
插入表头
链栈 出栈 函数
Status Pop( ) { if(st==NULL){下溢} else{e=st->data;p=st; st=st->next; free(p); return(e);} }
从表头删除
由此可以看出：一个链栈由其栈顶指针唯一指定 设st指向栈顶元素，当st=NULL时表示栈空
数 据 结 构
李
鑫
辽宁工程技术大学
辽宁工程技术大学电信学院
数据结构课程的内容
第三章 栈和队列
3.1 栈（Stack） 3.2 队列（Queue）
1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式
1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式
3.1 栈
基本操作
InitStack（&s）
操作结果：构造一个空栈
DestroyStack(&s)
初始条件：栈s已经存在 操作结果：栈s被销毁
ClearStack（&s）
初始条件：栈s已经存在 操作结果：将s清为空
GetTop（s,&e）
初始条件：栈s已经存在且非空 操作结果：用e返回s的栈顶元素
StackEmpty(s)
Q3：什么叫“向上生成”的栈？ “向下生成”又是何意？
若入栈动作使地址向高端增长，称为“向上生成”的栈； 若入栈动作使地址向低端增长，称为“向下生成”的栈；
对于向上生成的堆栈:
入栈口诀：堆栈指针top ―先压后加” : S[ top++ ]=an+1 出栈口诀：堆栈指针top ―先减后弹” : e=S[ --top ]
本节重点：顺序栈和链栈的基本操作
栈的抽象数据类型定义: (教材P44-45） ADT Stack{ 数据对象：D={D={ai | ai∈ElemSet, i=1,2,…,n,n≥0} 数据关系：R=={< ai –1, ai > | ai ห้องสมุดไป่ตู้1, ai ∈D, i=2,…,n}} 约定an端为栈顶，a1端为栈底。 入栈、出栈、 基本操作： 建栈初始化、 …… 判断栈满或栈空、 读栈顶元素值等。 } ADT Stack
几点说明:
1) 链栈不必设头结点，因为栈顶（表头）操作频繁；
2) 链栈一般不会出现栈满情况，除非没有空间导致 malloc分配失败。
3) 链栈的入栈、出栈操作就是栈顶的插入与删除操作， 修改指针即可完成。 4) 采用链栈存储方式的优点是，可使多个栈共享空间； 当栈中元素个数变化较大，且存在多个栈的情况下， 链栈是栈的首选存储方式。
动态数组 顺序栈的存储表示（教材P46)： #define #define STACK-INIT-SIZE STACKINCREMENT 100 //存储空间初始分配量 10 //存储空间分配增量
//栈的基址即栈底指针
//栈顶指针
typedef struct{
SElemType
SElemType int
*base;
*top;
stacksize; //当前分配的空间
}SqStack;
顺序栈的入栈操作——例如用堆栈存放（A，B，C，D）
高地址M
top B top A top C B A top D C B A
低地址L
top A
核心语句： top=L; Push (A); Push (B); Push (C); Push (D);
Ａ）a，b，c，d Ｃ）b，c，d，a
Ｂ）c，d，a，b Ｄ）a，c，d，b
答： A）、D）可以， B）、C）不行。 讨论：有无通用的判别原则？ 有！若输入序列是 …,Pj…Pk…Pi …(Pj<Pk<Pi) ， 一定不存在这样的输出序列 …,Pi…Pj…Pk …
即对于输入序列1，2，3，不存在输出序列3，1，2
1 0 栈空 top B A 进栈 栈满 5 4 3 2 1 0 top top F E D C
栈空
5
top
top top
4 3
2 1 0
top
top
B
A 出栈
top=0
栈顶指针top,指向实际栈顶 后的空位置，初值为0
设数组维数为M top=0,栈空，此时出栈，则下溢（underflow) top=M,栈满，此时入栈，则上溢（overflow)
a2 a1
表头
低地址
…… a2 a1
栈底base
写入：S[i]= ai 读出： e= S[i]
压入(PUSH): S[top++]=an+1 弹出( POP) : e=S[--top]
前提：一定要预设栈顶指针top
顺序栈S
高地址
栈顶top
an+1 an …… ai …… a2 a1
低地址
栈底base 栈不存在的条件： base=NULL; 栈为空 的条件 ： base=top; 栈满的条件 ： top-base=stacksize;
例 把十进制数159转换成八进制数
8 159 余7 余3 top top 7 2 3 7 top 3 7
top
8 19 8 2 0
余2
2 3 7
(159)10=(237)8
Void conversion（）{ //对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。 InitStack（s）//构造空栈 scanf(“%d”,N); while(N){ Push(s,N%8); N=N/8;} While（!StackEmpty(s)）{ pop(s,e); printf(“%d”,e); } } //conversion