第3章栈与队列
第3章 栈与队列
目录 栈 2,栈的应用举例 3.栈与递归 k4,队列 5应用实例
目录 1.栈 2. 栈的应用举例 3. 栈与递归 4. 队列 5. 应用实例
3.1 栈 311栈的定义及其运算 栈(Stak)是限定插入和删除运算只能在表尾 进行的线性表。 通常称允许插入、删除的这一端为栈顶,另一端 称为栈底。 当表中没有元素时称为空栈。 其中数据元素的个数n定义为表的长度
3.1 栈 3.1.1 栈的定义及其运算 栈（Stack）是限定插入和删除运算只能在表尾 进行的线性表。 通常称允许插入、删除的这一端为栈顶，另一端 称为栈底。 当表中没有元素时称为空栈。 其中数据元素的个数n定义为表的长度
图3.1是一个栈的示意图,通常用指针top指示栈顶的位 置,用指针 bottom指向栈底。栈顶指针top动态反映栈 的当前位置。 进栈 出栈 图3.1所示的栈中,元素是以a1, a ,an的顺序进栈,而出栈 栈顶 的次序却是an,an1,…,a1 也就是说,栈的修改是按后进先 a2 ai 出的原则进行的。因此,栈又称为 图3.1栈栈底 后进先出( Last in first out)的线性表,简称为 LIFO表
图3.1是一个栈的示意图，通常用指针top指示栈顶的位 置，用指针bottom指向栈底。栈顶指针top动态反映栈 的当前位置。 图3.1所示的栈中，元素是以a1， a2，…，an的顺序进栈，而出栈 的次序却是an，an-1，…，a1。 也就是说，栈的修改是按后进先 出的原则进行的。因此，栈又称为 后进先出（Last In First Out）的线性表，简称为 LIFO表
栈的ADT声明如下: ADTS七ack i Typedef struct Stack s; Initstack(s, maxSize)i 说明:构造空栈S,即栈的初始化 Stacks主ze(S); 说明:求栈中元素的数目 isEmpty(s) 说明:判栈s是否为空栈 isFull(s) 说明:判栈s是否已“满
ADT Stack { Typedef struct Stack S; InitStack(S,maxSize); 说明：构造空栈S，即栈的初始化 StackSize(S); 说明：求栈中元素的数目 isEmpty(S); 说明：判栈S是否为空栈 isFull(S); 说明：判栈S是否已“满” 栈的ADT声明如下：
GetT。P(S,e); 说明:取栈顶元素 Push (S,e) 说明:值为e的数据元素进栈(插入、压栈) P。p(S) 说明:栈顶元素出栈(删除、退栈) }
GetTop(S,e); 说明：取栈顶元素 Push (S,e); 说明：值为e的数据元素进栈（插入、压栈） Pop(S); 说明：栈顶元素出栈（删除、退栈） };
312栈的顺序存储结构 栈的顺序存储结构称为顺序栈,是用一组地址连续的 存储单元依次存放自栈底到栈顶的数据元素。 因为栈底位置是固定不变的,栈顶位置是随着进栈和退栈 操作而变化的,故需用一个变量top来指示当前栈顶位置, 通常称top为栈顶指针,参看图3.2。 a5 目 a4 a 3 2. top a al0 top top-l (a)空栈(b)al进栈(c)a2-a5相继进栈(d)a5a3相继出栈 图32顺序栈中栈顶指针和栈中数据元素之间的关系
栈的顺序存储结构称为顺序栈，是用一组地址连续的 存储单元依次存放自栈底到栈顶的数据元素。 3.1.2 栈的顺序存储结构 因为栈底位置是固定不变的，栈顶位置是随着进栈和退栈 操作而变化的，故需用一个变量top来指示当前栈顶位置， 通常称top为栈顶指针，参看图3.2
我们先以整数元素为例,给出顺序栈的基本 算法,在下一节,将给出顺序栈的模板类接口 定义以及基本运算的实现代码和应用实例。 typedef struct int*elem;//elem是数据元素数组 int top;//′栈顶指针 int maκsize;//栈容量 fsaStacki
Typedef struct { int *elem; // elem是数据元素数组 int top; // 栈顶指针 int maxSize; // 栈容量 }sqStack; 我们先以整数元素为例，给出顺序栈的基本 算法，在下一节，将给出顺序栈的模板类接口 定义以及基本运算的实现代码和应用实例
void Initstack(S, maxsize)∥/栈初始化 I s top=-li selem=new int[maxSize], F bool isEmpty(s)∥判栈空否? i return s top==-1; J bool isU11(S)∥/判栈满否? I return top==S. maxSize-li J bool Push(sqStack s, int e) ∥/值为e的数据元素进栈(插入、压栈) if(isFu11(s))∥/栈满(溢出)无法进栈,返回 false {cout<" ERROR:over￡1。w!!n"; return false; 1 s elem [++S top] return true ∥/栈顶指针增1元素进栈返回true
void InitStack(S,maxSize) // 栈初始化 { S.top=-1; S.elem=new int[maxSize]; } bool isEmpty(S) // 判栈空否？ { return S.top==-1; } bool isFull (S) // 判栈满否？ { return top==S.maxSize-1; } bool Push (sqStack S, int e) // 值为e的数据元素进栈(插入、 压栈) { if(isFull(S)) // 栈满（溢出）无法进栈,返回false { cout << " ERROR: overflow !!\n"; return false; } S.elem[++S.top] = e ; return true ; //栈顶指针增1元素进栈,返回true }
bool Pop( tsTack S)//栈顶元素出栈(删除) 主f( isEmpty(s)//栈空无法删除,返回fa1se cout<<“ ERROR: unders1ow!!n”; return false s. top--i return true; //元素出栈 bool GetTop(sastack s, int &e) //取栈s的栈顶元//素 if( isEmpty(s))/栈空(下溢) cout < ERROR: underflow !!\n return false i e=selem[s top] i return true /元素存e,栈顶指针不变(元素没出栈)
bool Pop(sqStack S) // 栈顶元素出栈(删除) { if(isEmpty(S)) // 栈空无法删除, 返回false { cout << “ ERROR: underflow !!\n” ; return false ; } S.top--; return true; // 元素出栈 } bool GetTop(sqStack S, int &e) // 取栈S的栈顶元//素 { if(isEmpty(S)) // 栈空（下溢） { cout << “ ERROR: underflow !!\n” ; return false ; } e=S.elem[S.top] ; return true ; // 元素存e, 栈顶指针不变(元素没出栈) }