河南中医药大学：《数据结构与算法》课程PPT教学课件（C#语言描述）第3章 栈和队列

第3章和队列 3.1栈 311栈的定义 栈是一种只能在一端进行插入或删除操作的线性表。 表中允许进行插入、删除操作的一端称为栈顶。表的另 端称为栈底。当栈中没有数据元素时,称为空栈。 栈的插入操作通常称为进栈或入栈,栈的删除操作通 常称为退栈或出栈

第3章 栈和队列 3.1 栈 3.1.1 栈的定义 栈是一种只能在一端进行插入或删除操作的线性表。 表中允许进行插入、删除操作的一端称为栈顶。表的另一 端称为栈底。当栈中没有数据元素时，称为空栈。 栈的插入操作通常称为进栈或入栈，栈的删除操作通 常称为退栈或出栈

栈的主要特点是“后进先出”,即后进栈的元素先弹出。 每次进栈的数据元素都放在原当前栈顶元素之前成为新的栈顶 元素,每次出栈的数据元素都是原当前栈顶元素。栈也称为后 进先出表。 下图是一个栈的动态示意图,图中箭头表示当前栈顶元素 位置 432 432 cba 0 a|0 (a)空栈 (b)元素a进栈(c)元素b、c、d进栈(d)元素d出栈

栈的主要特点是“后进先出”，即后进栈的元素先弹出。 每次进栈的数据元素都放在原当前栈顶元素之前成为新的栈顶 元素，每次出栈的数据元素都是原当前栈顶元素。栈也称为后 进先出表。 下图是一个栈的动态示意图，图中箭头表示当前栈顶元素 位置。 4 3 2 1 0 （a）空栈 a （b）元素 a 进栈 d c b a （c）元素 b、c、d 进栈 c b a （d）元素 d 出栈 -1 4 3 2 1 0 -1 4 3 2 1 0 -1 4 3 2 1 0 -1

抽象数据类型栈的定义如下: ADT Stack 数据对象 D={a1|1sn,n>0,a.为 ElemType类型}/假设 Elem Type为 string 数据关系: REr r={|a;2a+1∈D,i=1,,n-1} 基本运算 bool StackEmpty(string e):判断栈是否为空,若空栈返回真;否则返回假。 bool Push(string e):进栈,将元素e插入到栈中作为栈顶元素。 bool Pop( restring e):出栈,从栈中退出栈顶元素,并将其值赋给e Geop( ref string e):取栈顶元素,返回当前的栈顶元素,并将其值赋给e

抽象数据类型栈的定义如下： ADT Stack { 数据对象： D={ai | 1≤i≤n,n≥0,ai为ElemType类型} //假设ElemType为string 数据关系： R={r} r={ | ai ,ai+1∈D, i=1,…,n-1} 基本运算： bool StackEmpty(string e)：判断栈是否为空，若空栈返回真；否则返回假。 bool Push(string e)：进栈，将元素e插入到栈中作为栈顶元素。 bool Pop(ref string e)：出栈，从栈中退出栈顶元素，并将其值赋给e。 GetTop(ref string e)：取栈顶元素，返回当前的栈顶元素，并将其值赋给e。 }

【例3.1】若元素进栈顺序为1234,能否得到3142的出 栈顺序? 解:为了要让3作为第一个出栈元素,1、2先进栈 此时要么2出栈,要么4进栈后出栈,出栈的第2个元素不 可能是1。所以得不到3142的出栈顺序

【例3.1】 若元素进栈顺序为1234，能否得到3142的出 栈顺序？ 解：为了要让3作为第一个出栈元素，1、2先进栈， 此时要么2出栈，要么4进栈后出栈，出栈的第2个元素不 可能是1。所以得不到3142的出栈顺序

312栈的顺序存储结构及其基本运算实现 和顺序表一样,顺序栈类 SqStack Classi定义如下: class sqstackclass const int maxSize=100;/栈中最多元素个数即栈的大小 public stringl data; /1放栈中元素 public int top 栈顶指针 public sqstackClasso 构造函数,用于栈初始化 data=new string MaxSize l top=-1 /顺序栈的基本运算算法 data下标 MaxSize-1 data数组 a a 空闲

3.1.2 栈的顺序存储结构及其基本运算实现 和顺序表一样，顺序栈类SqStackClass定义如下 ： class SqStackClass { const int MaxSize=100; //栈中最多元素个数即栈的大小 public string[] data; //存放栈中元素 public int top; //栈顶指针 public SqStackClass() //构造函数，用于栈初始化 { data=new string[MaxSize]; top=-1; } //顺序栈的基本运算算法 } a1 a2 … ai … an data 数组 0 1 … i-1 … n-1 … 空闲 MaxSize-1 ngth data 下标

顺序栈存储结构的基本要素如下 ●初始时置栈顶指针tp=1。 ●栈空的条件为op=1; ●栈满的条件为op= Maxsize-1; ●元素进栈操作是先将栈顶指针增1,然后将元素e放在 栈顶指针处; ●出栈操作是先将栈顶指针处的元素取出,然后将栈顶指 针减1

顺序栈存储结构的基本要素如下： 初始时置栈顶指针top=-1。 栈空的条件为top==-1； 栈满的条件为top==MaxSize-1； 元素e进栈操作是先将栈顶指针增1，然后将元素e放在 栈顶指针处； 出栈操作是先将栈顶指针处的元素取出，然后将栈顶指 针减1

顺序栈的基本运算算法如下。 (1)判断栈是否为空 StackEmptyo 若栈顶指针top为-表示空栈。对应的算法如下: public bool StackEmptyO return(top

顺序栈的基本运算算法如下。 （1）判断栈是否为空StackEmpty() 若栈顶指针top为-1表示空栈。对应的算法如下： public bool StackEmpty() { return(top==-1); }

(2)进栈Push(e) 元素进栈只能从栈顶进,不能从栈底或中间位置进栈, 如下图所示。 元素e进栈后的结果 栈底 栈顶 栈顶 曾曾留 元素e进栈 會會會曾會

（2）进栈Push(e) 元素进栈只能从栈顶进，不能从栈底或中间位置进栈， 如下图所示。 栈底 栈顶 元素 e 进栈 元素 e 进栈后的结果 栈底 栈顶

在进栈运算中,当栈不满的条件下,先将栈顶指针增1, 然后在该位置上插入元素e对应的算法如下: public bool Push(string x) if(top==MaxSize-1) /栈上溢出时返回 false return false top+t 栈顶指针增1 data topl=x; return true;

在进栈运算中，当栈不满的条件下，先将栈顶指针增1， 然后在该位置上插入元素e。对应的算法如下： public bool Push(string x) { if (top==MaxSize-1) //栈上溢出时返回false return false; top++; //栈顶指针增1 data[top]=x; return true; }

(3)出栈Pope) 元素出栈只能从栈顶出,不能从栈底或中间位置出栈,如 下图所示。 元素e出栈后的结果 栈底 栈顶 栈底 栈顶 元素e出栈

（3）出栈Pop(e) 元素出栈只能从栈顶出，不能从栈底或中间位置出栈，如 下图所示。 栈底 栈顶 元素 e 出栈 栈底 栈顶 元素 e 出栈后的结果