电子斜技大学 软件技术基础 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表示出栈操作