第三章栈和队列
第三章 栈和队列
3.1栈 3.2栈的应用举例 3.3队列 3.4队列的应用举例
3.1 栈 3.2 栈的应用举例 3.3 队列 3.4 队列的应用举例
栈（Stack) 只允许在表的一端插入和删除的线性表 ·允许插入和删除 出栈 入栈 的一端称为栈顶 top (top),另一端称 为栈底(bottom) 特点： 后进先出(LIFO) bottom
◼ 只允许在表的一端插入和删除的线性表 ◼ 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) ◼ 特点： 后进先出 (LIFO) 栈 ( Stack ) 出栈 入栈 a1 an an-1 top bottom
举例1：家里吃饭的碗，通常在洗干净后一个一个 地落在一起存放，在使用时，若一个一个 地拿，一定最先拿走最上面的那只碗，而 最后拿出最下面的那只碗。 举例2：在建筑工地上，使用的砖块从底往上一层 一层地码放，在使用时，将从最上面一层 一层地拿取
举例1：家里吃饭的碗，通常在洗干净后一个一个 地落在一起存放，在使用时，若一个一个 地拿，一定最先拿走最上面的那只碗，而 最后拿出最下面的那只碗。 举例2：在建筑工地上，使用的砖块从底往上一层 一层地码放，在使用时，将从最上面一层 一层地拿取
由此可知，最先放入栈中元素的元素在 栈底，最后放入的元素在栈顶，而删除元 素刚好相反，最后放入的元素最先删除， 最先放入的元素最后删除
由此可知，最先放入栈中元素的元素在 栈底，最后放入的元素在栈顶，而删除元 素刚好相反，最后放入的元素最先删除， 最先放入的元素最后删除
1.初始化栈：Init_Stack(S) 将栈S置为一个空栈（不含任何元素）。 栈的基本运算 2.判栈空：Empty._Stack(S) 判断栈S是否为空，若为空，返回值为TRUE,否则返回值为FALSE。 3.入栈：Push_Stack(S,x) 在栈S的顶部插入新元素X,也称为“进栈”、“插入”、“压 入”。 4.出栈：Pop_Stack(S) 删除栈S中的栈顶元素，也称为”退栈”、“删除”、“弹出”。 5.取栈顶元素：Top_Stack(S) 取栈S中栈顶元素作为结果返回，栈不变化
1. 初始化栈：Init_Stack(S) 将栈S置为一个空栈(不含任何元素)。 2. 判栈空： Empty_Stack(S) 判断栈S是否为空，若为空，返回值为TRUE，否则返回值为FALSE。 3. 入栈：Push_Stack( S, x ) 在栈S的顶部插入新元素 x ，也称为 “进栈” 、 “插入” 、 “压 入”。 4. 出栈： Pop_Stack(S) 删除栈S中的栈顶元素，也称为”退栈” 、 “删除” 、 “弹出”。 5. 取栈顶元素： Top_Stack(S) 取栈S中栈顶元素作为结果返回，栈不变化。 栈 的 基 本 运 算
栈的存储结构 顺序栈 用一组地址连续的存储单元依次存放栈中的每个 数据元素，并用起始端作为栈底。 由于栈操作的特殊性，附设一个栈顶指针top来动 态地表示栈顶元素在顺序栈中的位置。 0123456789 MAXSIZE-1 data 1top(栈空)
栈的存储结构 一、 顺 序 栈 用一组地址连续的存储单元依次存放栈中的每个 数据元素，并用起始端作为栈底。 由于栈操作的特殊性，附设一个栈顶指针top来动 态地表 示栈顶元素在顺序栈中的位置。 0 1 2 3 4 5 6 7 8 9 MAXSIZE-1 top (栈空) data
顺序栈定义如下： #define MAXSIZE 1024 typedef struct stack { datatype data[MAXSIZE]; int top; }SeqStack;
顺序栈定义如下： #define MAXSIZE 1024 typedef struct stack { datatype data[MAXSIZE]; int top; }SeqStack;
top b top→ L L top→ 空栈 a入栈 b入栈 gf top e top→ e d d top→ d C C C b b b L a L Cl,e入栈 f入栈溢出 E出栈
top 空栈 a 入栈 b 入栈 a a b a b c d e c,d,e 入栈 a b c d e f 入栈溢出 a b d E出栈 c top top top top top f
top→ b top b L a top→ d出栈 C出栈 b出栈 top→a出栈 空栈←一top==0
c 出栈 b 出栈 a a 出栈 空栈 a b d 出栈 c a b top top top top top= =0