数 3-栈队列2.pdf

数据结构华中科技大学 计算机学院 第三章 栈和队列 对线性表 L=(a ,a ,,...,a ), 1 2 n 可在任意第i(i=1,2,,...n,n+1)个位置插入新元素， 或删除任意第i(i=1,2,,...n)个元素。 受限数据结构 插入和删除受限制的线性表： 1.栈(stack) 2.队列(queue) 3.双队列(deque) 2 栈和队列是限定插入和删除只能在表的“端点” 进行的线性表。 线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1≤i≤n+1 Delete(L, i,e) Delete(S, n,e) Delete(Q, 1,e) 1≤i≤n 栈和队列是两种常用的数据类型 3 3.1栈(stack) 3.1.1栈的定义和操作 1.定义和术语 栈：限定在表尾作插入、删除操作的线性表。 (a ,a , ,...，a ） ←插入元素(进栈) 1 2 n ↑ ↑ ↘删除元素(出栈） 表头 表尾 (栈底) (栈顶） 4 进栈：插入一个元素到栈中。 或称:入栈、推入、压入、push。 出栈(pop) 进栈(push) 出栈：从栈删除一个元素。 或称：退栈、上托、弹出、pop。 an 栈顶(top) 栈顶：允许插入、删除元素的一端(表尾)。 栈顶元素：处在栈顶位置的元素。 a1 栈底(bottom) 栈底：表中不允许插入、删除元素的一端。 栈的示意图 空栈：不含元素的栈。 栈的元素的进出原则: 后进先出 , Last In First Out 。 “ ” “ ” 栈的别名: 后进先出 表、 LIFO 表、反转 “ ” “ ” 存储器、地窖、堆栈。 5 栈的类型定义 ADT Stack { 数据对象： D ＝{ ai | ai ∈ElemSet, i=1,2,...,n, n ≥0 } 数据关系： R1 ＝{ a , a | a , a ∈D, i=2,...,n }