电子斜技大学 软件技术基础 3.3谁栈和队列 主讲教师：刘民岷 航空航天学院 a口2 软件技术基础课程组
软件技术基础 主讲教师：刘民岷 航空航天学院 软件技术基础课程组
1、谁栈 栈与队列是两种特列的线性表，它们的逻辑结构与线性表 相同，只是其插入、删除运算只允许在表的端点进行，栈与 队列是程序设计中常用的两种数据结构。 栈是仅允许在同一端进行插入和 进栈 个出栈 删除操作的特殊线性表。 栈顶 >允许进行插入和删除操作的一端称为栈 顶top),另一端为栈底(bottom)；栈底固 an-1 定，而栈顶浮动； >栈中元素个数为零时称为空栈。 >栈结构也称为后进先出表(LIFO)。 a2 a 栈底 栈示意图 电子科技大学刘民岷 堆栈和队列 2
电子科技大学 刘民岷 堆栈和队列 2 栈与队列是两种特列的线性表，它们的逻辑结构与线性表 相同，只是其插入、删除运算只允许在表的端点进行，栈与 队列是程序设计中常用的两种数据结构。 an an-1 a2 a1 ... 进栈 出栈 栈顶 栈底 栈示意图 栈是仅允许在同一端进行插入和 删除操作的特殊线性表。 ➢允许进行插入和删除操作的一端称为栈 顶(top)，另一端为栈底(bottom)；栈底固 定，而栈顶浮动； ➢栈中元素个数为零时称为空栈。 ➢栈结构也称为后进先出表(LIFO)
1.1堆栈基本操作 ▣堆栈的五种基本操作： (1)SETNULL(S)(置空栈)：将栈S置成空栈。 (2)EMPTY(S){判空栈)：这是一个布尔函。若栈S为空栈，则 返回值“真”，否则返回值“假”。 (3)PUSH(s,x){进栈}：在栈S的顶部插入（亦称压入）元素x。 (4)POP(S){出栈}：若栈S不空，则删除（亦称弹出）顶部元素。 (5)POP(S){取栈顶}：取栈顶元素，并不改变栈中内容。 电子科技大学刘民岷 堆栈和队列 3
电子科技大学 刘民岷 堆栈和队列 3 堆栈的五种基本操作： （1）SETNULL(s)｛置空栈｝:将栈S置成空栈。 （2）EMPTY(s)｛判空栈｝:这是一个布尔函。若栈S为空栈,则 返回值“真”，否则返回值“假”。 （3）PUSH(s,x)｛进栈｝:在栈S的顶部插入(亦称压入)元素x。 （4）POP(s)｛出栈｝:若栈S不空,则删除(亦称弹出)顶部元素。 （5）POP(s)｛取栈顶｝:取栈顶元素，并不改变栈中内容
1.1谁栈基本操作（续） ▣堆栈的操作示例： TOP al a a MAXSIZE 栈底 栈顶 1 2. ABC top=0 (空栈) top=3 (A、B、C进栈) 3. 4. EF top-2 top=MAXSIZE (C出栈) (栈满) 电子科技大学刘民岷 堆栈和队列 4
电子科技大学 刘民岷 堆栈和队列 4 堆栈的操作示例： a1 a2 …… an 栈底 栈顶 MAXSIZE TOP 1. top=0 2. A B C (空栈) top=3 (A、B、C进栈） 3. A B top=2 (C出栈） 4. A B C D E F top=MAXSIZE (栈满）
1.1谁栈-基本操作（续） 例：有三个元素的进栈序列是1,2,3。写出可能的 出栈序列。 出栈序列 操作序列 123 i o i o i 0 13.2 0 0 213 ii 0 0 0 231 ii 0 i 0 321 iii 0 0 0 注：上表中i表示进栈操作，o表示出栈操作。 电子科技大学刘民岷 堆栈和队列 5
电子科技大学 刘民岷 堆栈和队列 5 例：有三个元素的进栈序列是1，2，3。写出可能的 出栈序列。 出栈序列 操作序列 1 2 3 i o i o i o 1 3 2 i o i i o o 2 1 3 i i o o i o 2 3 1 i i o i o o 3 2 1 i i i o o o 注：上表中i表示进栈操作，o表示出栈操作
1.2谁栈物理存储结构 1.2.1顺序存储结构一顺序栈 ·栈的顺序存储结构实际上是一维数组。 ·栈的顺序存储结构称为顺序栈。 栈的操作只能在一端进行；即栈顶位置随进栈和出栈而变化。 顺序栈的C语言描述为： define struct eletype stack[MAXMUM] int top; }stacktype; 顺序栈结构定义 stacktype s; /定义一个堆栈 电子科技大学刘民岷 堆栈和队列 6
电子科技大学 刘民岷 堆栈和队列 6 1.2.1 顺序存储结构－顺序栈 • 栈的顺序存储结构实际上是一维数组。 • 栈的顺序存储结构称为顺序栈。 • 栈的操作只能在一端进行；即栈顶位置随进栈和出栈而变化。 • 顺序栈的C语言描述为： define struct {eletype stack[MAXMUM]; int top; }stacktype; //顺序栈结构定义 stacktype s; //定义一个堆栈
1.2谁栈-物理存储结构（续） ▣[算法]顺序栈元素的进栈 算法步骤： stepl 判别栈满否，若满，「 则显示栈溢出信息，停止执行；否 则，执行step2; Step2 栈顶指针top上移（加1）： Step3 在top所指的位置插入元素x。 电子科技大学刘民岷 堆栈和队列 7
电子科技大学 刘民岷 堆栈和队列 7 [算法] 顺序栈元素的进栈 • 算法步骤: – step1 判别栈满否，若满，则显示栈溢出信息，停止执行；否 则，执行step 2； – Step2 栈顶指针top上移(加1)； – Step3 在top所指的位置插入元素x
1.2谁栈-物理存储结构（续） ▣[算法]顺序栈元素的进栈 00001: /顺序栈的进栈算法 00002: 00003://========== 00004: define true 1 0000s:define false o 00006: int pushs (stacktype *s,elemtype x) 00007: if(s->top>=MAXNUM-1) /1诺误湾 况之- "MAXNUM-1"? 00008: return(false); 1/按赏，不能芦进按 00009: else 00010: f 00011: s->top++; 00012: s->stack[s->top]=x;/ 00013: return(true); 00014: 00015: 电子科技大学刘民岷 堆栈和队列 8
电子科技大学 刘民岷 堆栈和队列 8 [算法] 顺序栈元素的进栈
1.2谁栈-物理存储结构（续） ▣[算法]顺序栈元素的出栈 。算法步骤： stepl判别栈是否为空；若空，则输出栈下溢信息，并 停止执行；否则，执行step2; step2弹出（删除)栈顶元素； step3栈顶指针top下移（减l)。 电子科技大学刘民岷 堆栈和队列 9
电子科技大学 刘民岷 堆栈和队列 9 [算法] 顺序栈元素的出栈 • 算法步骤: – step1 判别栈是否为空；若空，则输出栈下溢信息，并 停止执行；否则，执行step2； – step2 弹出（删除）栈顶元素； – step3 栈顶指针top下移(减1)
1.2谁栈-物理存储结构（续） ▣[算法]顺序栈元素的出栈 00001: !顺序栈的出栈算法 00002: 00003: //================ 00004: int pops(stacktype *s) 00005: if(s->toptop--i 00010: return(s->stack[s->top+1]);/按政元蒸出按 00011 00012: 电子科技大学刘民岷 堆栈和队列 10
电子科技大学 刘民岷 堆栈和队列 10 [算法] 顺序栈元素的出栈