第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={<a1a1+1>|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> | 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 下标