数据结构3-栈与队列.pdfVIP

第三章 栈和队列 对线性表 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) 1 和队列是限定插入和删除只能在表的“端点” 进行的线性表。 性表 栈 队列 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 和队列是两种常用数据类型，是典型的串行数据结构。 2 1 3.1栈(stack) 3.1.1栈的定义和操作 1.定义和术语 栈：限定在表尾作插入、删除操作的线性表。 (a ,a , ,...，a ） ←插入元素(进栈) 1 2 n ↑ ↑ ↘删除元素(出栈） 表头 表尾 (栈底) (栈顶） 3 进栈：插入一个元素到栈中。 或称:入栈、推入、压入、push。 出栈(pop) 进栈(push) 出栈：从栈删除一个元素。 或称：退栈、上托、弹出、pop。 an 栈顶(top) 栈顶：允许插入、删除元素的一端(表尾)。 栈顶元素：处在栈顶位置的元素。 a1 栈底(bottom) 栈底：表中不允许插入、删除元素的一端。 栈的示意图 空栈：不含元素的栈。 栈的元素的进出原则: 后进先出”, Last In First Out 。 “ “ ” 栈的别名: 后进先出”表、“LIFO 表、 “ ” 反转存储器、地窖、堆栈。 4 2 栈的类型定义 ADT Stack { 数据对象： D ＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1 ＝{ a , a | a , a ∈D, i=2,...,n } i-1 i i-1 i 约定a 端为 顶，a 端为栈底。 n 1 基本操作： } ADT Stack