第3章栈和队列 3.1栈 3.2栈的应用举例 3.3队列
第3章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 队列
第3章栈和队列 栈和队列是两种应用非常广泛的数据结构，它们 都来自线性表数据结构，都是“操作受限”的线性 表。与线性表相比，它们的插入和删除操作受更多 的约束和限定，故又称为限定性的线性表结构。 ◆线性表允许在表内任一位置进行插入和删除； ◆栈只允许在表尾一端进行插入和删除； ◆队列只允许在表尾一端进行插入，在表头一端进行删除
第3章 栈和队列 栈和队列是两种应用非常广泛的数据结构，它们 都来自线性表数据结构，都是“操作受限”的线性 表。与线性表相比，它们的插入和删除操作受更多 的约束和限定，故又称为限定性的线性表结构。 ◆线性表允许在表内任一位置进行插入和删除； ◆栈只允许在表尾一端进行插入和删除； ◆队列只允许在表尾一端进行插入，在表头一端进行删除
3.1栈 3.1.1栈的基本概念 1栈的概念 ◆栈(Stack):是限制在表的一端进行插入和删除 操作的线性表。 ◆也称为后进先出LIFO(Last In First Out)或先进 后出FILO(First In Last Out)线性表
3.1 栈 3.1.1 栈的基本概念 1 栈的概念 ◆栈(Stack)：是限制在表的一端进行插入和删除 操作的线性表。 ◆也称为后进先出LIFO (Last In First Out)或先进 后出FILO (First In Last Out)线性表
◆栈顶(Top):允许进行插入、删除操作的一端，又 称为表尾。用栈顶指针(top)来指示栈顶元素。 ◆栈底Base):是固定端，又称为表头。 ◆空栈：当表中没有元素时称为空栈 设栈S=(a,a2,.an), 进栈(push) 出栈pop) 则a称为栈底元素，an为栈 顶元素。 top 8 栈中元素按a1,a2, ·。。●。 .an的次序进栈，出栈的第 a ●900● 一个元素应为栈顶元素。即 a 栈的修改是按后进先出的原 base aL 则进行的
设栈S=(a1，a2，…an )， 则a1称为栈底元素，an为栈 顶元素。 栈中元素按a1，a2， …an的次序进栈，出栈的第 一个元素应为栈顶元素。即 栈的修改是按后进先出的原 则进行的。 a1 a2 ai an ⋯⋯ ⋯⋯ base top 进栈（push） 出栈(pop) ◆栈顶(Top)：允许进行插入、删除操作的一端，又 称为表尾。用栈顶指针(top)来指示栈顶元素。 ◆栈底(Base)：是固定端，又称为表头。 ◆空栈：当表中没有元素时称为空栈
例1：家里吃饭的碗，通常在洗干净后一个一个 地落在一起存放，在使用时，若一个一个地拿， 一定最先拿走最上面的那只碗，而最后拿出最下 面的那只碗。 例2：在建筑工地上，使用的砖块从底往上一层 一层地码放，在使用时，将从最上面一层一层地 拿取。 Top Stack of Coins Stack of Books Computer Stack
例1：家里吃饭的碗，通常在洗干净后一个一个 地落在一起存放，在使用时，若一个一个地拿， 一定最先拿走最上面的那只碗，而最后拿出最下 面的那只碗。 例2：在建筑工地上，使用的砖块从底往上一层 一层地码放，在使用时，将从最上面一层一层地 拿取