数据结构详细讲解(栈和队列)

（1） （2） （3） （4） 栈的定义和特点 栈的抽象数据类型定义 栈的表示和实现 栈的应用
4
栈的定义
定义：限定仅在表尾进行插入或删除操作 的线性表。 表尾—栈顶 表头—栈底 不含元素的空表称空栈
5
栈的特点
特点：先进后出（FILO）或后进先出（LIFO）
进栈 栈顶 出栈 ... an ……... a2 栈底 栈s=(a1,a2,……,an)
第三章 栈和队列
栈和队列
栈和队列是两种特殊的线性表 是操作受限的线性表，称为限定性的数据结构 栈的插入和删除限定在表尾 队列的插入限定在表尾，删除限定在表头
2
第3章 栈和队列
3.1 3.2 3.3 3.4

栈（Stack） 队列（Queue） 本章小结 课后练习
3
3.1 栈（Stack）
int IsEmpty ( SeqStack * s ) { if ( S->top= =-1 ) return 1; else return 0; }
20
顺序栈的判满
int IsFull ( SeqStack * s ) { if ( S->top = = Stack_Size-1 ) return 1; else return 0; }
4 3
2 1 top 0
4 3
2 1 0
D C
B
空栈
A 进栈
栈空时出栈，则下溢（underflow) 栈满时入栈，则上溢（overflow)
16
思考题
设有一个空栈，栈的首地址为1000H(十六进制) ，经过push,push,pop,push,pop,push,pop,push后 ，栈顶元素的地址为多少(sizeof(ElemType)=2)？ 答案： 1002H
后缀表达式：435*+
4
3 4
5 3 4
15 4
19
45
栈的应用5—函数的调用
函数的嵌套调用
主 程 序 s 子 过 程 s t s
子 过 程 t
f t s
子 过 程 f
46
s
t s
default: return(FALSE);
} return(TRUE); }
31
链栈
链栈：栈的操作是线性表的特例，链栈的操作 易于实现。注意分析结点指针的指向。
ai
ai+1 top
ai+1
ai
^
空链栈 … 栈顶 a1 栈底
top
an
^
32
链栈结点类型
typedef struct node {
-12 操作数 运算符
后缀表达式求值
后缀表达式求值步骤（引入一个栈即可）： 1.读入表达式一个字符 2.若是操作数，压入栈，转4 3.若是运算符，从栈中弹出2个数，将运算 结果再压入栈 4.若表达式输入完毕，栈顶即表达式值； 若表达式未输入完，转1
44
后缀表达式求值
例: 计算 4+3*5
4. IsFull（S） 6. Pop（S，x）
12
栈的表示和实现
栈在计算机中主要有两种基本的存储结构： 顺序存储结构和链式存储结构。 顺序存储的栈称为顺序栈 链式存储的栈称为链栈
13
顺序栈
顺序栈：利用一组地址连续的存储单元依次存 放自栈底到栈顶的数据元素，同时附设指针 top指示栈顶元素在顺序栈中的位置。 顺序栈的类型说明： typedef struct { ElemType elem[Stack_Size]; int top; }SeqStack;
a1
6
入栈序列与出栈序列
栈具有LIFO性质，若已知栈的输入序列为1 2 3 ，则输出序列有多少种呢？ 以1为头：123 132 以2为头：213 231 以3为头：321
7
入栈序列与出栈序列
若已知栈的输入序列为1 2 3 4，则输出序列有 多少种呢？ 以1为头：1234 1243 1324 1342 1432 以2为头：2134 2143 2314 2341 2431 以3为头：3214 3241 3421 以4为头：4321 当输入序列为1 2 … n时，经过栈可获得的输 出序列的个数由尤.卡塔南数决定，即：
while(！IsEmpty(S))
{ Pop(&S,&x); printf(“%d”,x); } }
37
十进制数转换成K进制数
void Conversion(int N,int base)
{ Stack S; int x; InitStack(&S); /*S为顺序栈或链栈*/
while(N)
{ x=N%base; Push(&S, x); N=N/base; } while(！IsEmpty(S)) { Pop(&S,&x); if(x<10) printf(“%d”,x);
top[1]
27
两栈共享的数据结构定义
#define M 100 typedef struct
{
ElemType Stack[M];
int top[2];
} DqStack;
28
两栈共享的初始化
void InitStack ( DqStack *S )
{ S->top[0]=-1; S->top[1]=M; }
14
顺序栈的top指针
top==-1，表示栈空； top== stacksize-1，表示栈满； 每插入一元素时，top加1； 每删除一元素时，top减1；
15Leabharlann 顺序栈的操作过程示意栈满
5 top top top top top top F E 5 top top top top top top top F E D C B A 出栈 栈空 5 4 3 2 1 0
17
顺序栈的基本操作
顺序栈的初始化操作 顺序栈的判空操作 顺序栈的判满操作 顺序栈的插入操作（入栈） 顺序栈的删除操作（出栈） 顺序栈的读取栈顶元素操作
18
顺序栈的初始化
void InitStack ( SeqStack * s ) { S->top= -1; }
19
顺序栈的判空
23
顺序栈中读取栈顶元素
int GetTop ( SeqStack *s, ElemType *e ) { if ( S->top== -1 ) return FALSE; *e=S->elem[S->top]; return TRUE; }
24
两栈共享技术
若在一个程序中要同时使用多个栈，如果采用 顺序存储结构 会因为栈空间大小难以准确估计，产生有的栈 溢出，有的栈还很空闲的情况 解决措施：两栈共享技术
答案：D
10
栈的抽象数据类型定义
数据元素：
可以是任意类型的数据，但必须属于同一 个数据对象。
关系： 栈中数据元素之间是线性关系。 基本操作：
11
栈的基本操作
1. InitStack（S）
3. IsEmpty（S） 5. Push（S，x） 7. GetTop（S，x）
2. ClearStack（S）
top->next=temp;
return TRUE; }
/* 修改当前栈顶指针 */
34
链栈的出栈操作
int Pop(LinkStack top, ElemType *x) { temp=top->next; if(temp==NULL) return FALSE; /*栈为空*/ top->next=temp->next; *x=temp->data;
39
栈的应用2 — 括号匹配问题
如此反复，直到：
输入序列和栈同时变为空，说明所有括号完 全匹配；
输入序列已读尽，而栈中仍有等待匹配的左 括号，说明括号不匹配，表达式不合法； 或者读入了一个右括号，而栈中已无等待匹 配的左括号，同样属不合法的情况。
40
栈的应用3—回文游戏
顺读与逆读字符串一样（不含空格） 读入字符串 去掉空格（原串） 压入栈 原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，回文
ElemType
data;
struct node *next; }LinkStackNode， *LinkStack;
33
链栈的入栈操作
int Push(LinkStack top, ElemType x) { temp=( )malloc(sizeof(LinkStackNode)); if(!temp) return FALSE; temp->data=x; temp->next=top->next;
d a d
top
41
栈的应用4—表达式求值
中缀表达式 a*b+c a+b*c a+(b*c+d)/e 后缀表达式 ab*c+ abc*+ abc*d+e/+
42
中缀表达式求值
操作数栈和运算符栈
例 计算 2+4-3*6
4 + 2 操作数 运算符 18 6 操作数 运算符
43
6 操作数 运算符
6 3 * 6 操作数 运算符
25
两栈共享技术
主要利用了栈“栈底位置不变，而栈顶位置 动态变化”的特性。 首先为两个栈申请一个共享的一段存储空间 S[M] 然后将两个栈的栈底分别放在存储空间的两 端，分别是0，M-1。
26
共享栈的空间示意
top[0]和top[1]分别为两个栈顶指示器
Stack：0 M-1