03 第3章 栈和队列

-退栈输出，退栈 到（止
/ 进栈 （ 进栈 输出7 - 进栈 输出4 -退栈输出，退栈 到（止
19
20
*
1 2 + 8 2 - 7 4 - /
}
2013年8月8日星期四 18
3.1.5
链栈
1、链栈结构及数据类型
栈的链式存贮结构,也称为链栈，它是一种限制运算的链 表，即规定链表中的扦入和删除运算只能在链表开头进行。 链栈结构见图3-5。 以下的输入序列为an,an-1,…a1
top
头
a1
a2
……
an ^
栈顶 图 3-5 链栈结构示意图
2013年8月8日星期四
2013年8月8日星期四
13
（5）判栈空否
int empty(seqstack s)
{
if (s.top= =0) return 1; else return 0;
}
2013年8月8日星期四 14
3、栈的共享存储单元
有时，一个程序设计中，需要使用多个同一类型的栈, 这时候，可能会产生一个栈空间过小，容量发生溢出，而 另一个栈空间过大，造成大量存储单元浪费的现象。 为了 充分利用各个栈的存储空间，这时可以采用多个栈共享存 储单元，即给多个栈分配一个足够大的存储空间，让多个 栈实现存储空间优势互补。
2013年8月8日星期四
22
（3）退栈运算
void pop(link *top) { link *s; s=top->next; if(s!=NULL) { top->next=s->next; delete(s); }}
2013年8月8日星期四 23
（4）取栈顶元素 elemtype gettop(link *top) { if(top->next!=NULL) return(top->next->data); else return(NULL);
详细的示意图 见书P59的图3.1
退出
进入
栈 讨论输入序列为1 2 3的有关 顶
an
情况： 反序： 正序：其他
栈 底
2013年8月8日星期四
a1
5
课堂作业： 1.把输入序列 1 2 3 经过栈的操作可能的所 有结果进行讨论
注意逻辑思维的规律思想方法
2013年8月8日星期四
6
3.1.2
栈的运算
1、初始化栈：INISTACK(&S)
2013年8月8日星期四 7
3.1.3 栈的抽象数据类型描述
ADT Stack is Data： 含有n个元素a1,a2,a3,…,an,按LIFO规则存放，每个元素的类型都为elemtype。 Operation： Void inistack(&s) Void Push(&s,x) “压入” Void Pop(&s) “弹出” //将栈S臵为一个空栈(不含任何元素) //将元素X插入到栈S中，也称为 “入栈”、 “插入”、 //删除栈S中的栈顶元素，也称为”退栈”、 “删除”、
栈底
19
课堂作业： 1. 编写链栈的进栈和出栈操作的算法
2013年8月8日星期四
20
2、链栈的五种栈运算
（1）栈初始化 void inistack(link *top) { top->next=NULL;}
2013年8月8日星期四
21
（2）进栈运算 void push(link *top,int x) { link *s; s=new link; s->data=x; s->next=top->next; top->next=s; }
else if (k==0) { s.top[0]++;s.stack[s.top[0]]=x;} else {s.top[1]--; s.stack[s.top[1]]=x;} }
2013年8月8日星期四 17
（2）两个栈共享存储单元的退栈算法
void pop(duseqstack &s, int k)
栈1底 栈1顶 图 3-3 两个栈共享存储单元示意图
2013年8月8日星期四 15
栈2底 栈2顶
两个栈共享存储单元可用如下C++语句描述：
CONST int maxsize=maxlen;
//maxlen为共享单元的最大长度
Struct
duseqstack
stack[maxsize];
{ elemtype int ……… };
if (s.top= =0) cout<<”underflow”;
else
s.top--;
}
2013年8月8日星期四 12
（４）取栈顶元素
elemtype gettop(seqstack s)
{
if (s.top= =0) {cout<<”underflow”;return 0;} else return s.stack[s.top]; }
2013年8月8日星期四 10
（２）进栈 void push(seqstack &s, elemtype x) {
if (s.top==maxsize-1} cout<<”overflow”;
else
{
s.stack[s.top]=x;
s.top++;
}
}
2013年8月8日星期四 11
（３）退栈 void pop(seqstack &s) {
将中缀表达式(1+2)*((8-2)/(7-4))变成等价的后缀表达式。
现在用栈来实现该运算，栈的变化及输出结果如下
2013年8月8日星期四
31
步骤
1
2 3 4 5 6 7 8 9 10
栈中元 素 ( ( (+ (+ 1 1 1 2
输出结果
说明
（进栈
输出1 +进栈 输出2 +退栈输出，退栈 到（止 *进栈 （进栈 （进栈 输出8 - 进栈
Struct seqstack
{ elemtype elemtype类型 stack[maxsize]; //将栈中元素定义为
int top;
}
//:指向栈顶位臵的指针
2013年8月8日星期四
9
2、栈的五种运算
（1）初始化栈
void inistack(seqstack &s)
{ s.top=0;
}
2013年8月8日星期四
3
根据栈的定义可知，最先放入栈中元素在栈 底，最后放入的元素在栈顶，而删除元素刚好相 反，最后放入的元素最先删除，最先放入的元素 最后删除。
也就是说，栈是一种后进先出(Last First Out)的线性表，简称为LIFO表。
In
没有元素时称为空栈
2013年8月8日星期四
4
7
1+6进入操作数栈
28
2013年8月8日星期四
步骤 10 11 12 13 14 15 16 17
操作数栈 7 7 4 7 4 7 4 2 7 7 2
运算符栈 - / - / -
说明 -进入运算符栈 4进入操作数栈 /进入运算符栈 2进入操作数栈 退栈 4/2进入操作数栈 退栈
5
7-2进入操作数栈
}
2013年8月8日星期四 24
（5）判栈空
int empty(link *top)
{
if(top->next==NULL)
return(1);
else return(0); }
2013年8月8日星期四 25
3.1.6
栈的应用
栈在日常生活中和计算机程序设计中有着许多 应用，下面仅介绍栈在计算机中的应用。
29
2013年8月8日星期四
以下内容目前不做要求 当然，算术表达式除了简单求值外，还会涉及到算术表达式的两 种表示方法，即中缀表示法和后缀表示法。刚才的例3-3中的表达式就 是中缀表达式，中缀表达式求值较麻烦（须考虑运算符的优先级，甚 至还要考虑圆括号），而后缀表达式求值较方便（无须考虑运算符的 优先级及圆括号）。下面将介绍算术表达式的中缀表示和后缀表示及 它们的求值规律，
例如，对于下列各中缀表达式： （1）3/5+8 （2）18-9*(4+3) （3）(25+x)*(a*(a+b)+b) 对应的后缀表达式为： （1）3 5 / 8 + （2）18 9 4 3 + * （3）25 x + a a b + * b + *
2013年8月8日星期四 30
2、中缀表达式变成等价的后缀表达式
第3章
栈和队列
2013年8月8日星期四
1
主要内容
栈
队列
这两种结构都是特殊的线性表
2013年8月8日星期四
2
3.1
栈
3.1.1 栈的定义
栈(stack)是限制线性表中元素的插入和删除 只能在线性表的同一端进行的一种特殊线性表。
允许插入和删除的一端，为变化的一端，称为 栈 顶 (Top) ， 另 一 端 为 固 定 的 一 端 ， 称 为 栈 底 (Bottom)。
2013年8月8日星期四
top[2] ; //两个栈的栈顶指针
16
（1）两个栈共享存储单元的进栈算法
void dupush(duseqstack &s, elemtype x, int k) //将元素x进入到以S为栈空间的第k个栈中 { if (s.top[0]+1==s.top[1]) cout<<“overflow”
将栈S臵为一个空栈(不含任何元素)。