的 华中科技大学 计算机学院(4) 2001-3-19
2001-3-19 华中科技大学 数据结构 计算机学院(4)
第三章栈和队列 引言:对线性表L=(a1,a2,,an), 可在任意第i(i=1,2,,n,n+1)个位置插入新元素, 或删除任意第i(i=1,2,,n)个元素 受限数据结构-—插入和删除受限制的线性表。 1.栈( stack),2.队列( queue),3.双队列( deque) 3.1栈( stack) 3.1.1栈的定义和操作 1.定义和术语 ▲栈——-限定在表尾作插入、删除操作的线性表。 (a1,a2 ,an)←插入元素(进栈) 删除元素(出栈) 表头 表尾 (栈底) (栈顶)
第三章 栈和队列 引言：对线性表 L=(a1,a2,,...,an), 可在任意第i(i=1,2,,...n,n+1)个位置插入新元素， 或删除任意第i(i=1,2,,...n)个元素 受限数据结构---- 插入和删除受限制的线性表。 1.栈(stack), 2.队列(queue), 3.双队列(deque) 3.1栈(stack) 3.1.1栈的定义和操作 1.定义和术语 ▲ 栈----限定在表尾作插入、删除操作的线性表。 (a1,a2, ,...，an） ←插入元素(进栈) ↑ ↑ ↘删除元素(出栈） 表头 表尾 (栈底) (栈顶）
出栈(pop) 进栈(push) an栈顶(top) a1|栈底( (bottom 栈的示意图 ▲进栈—插入一个元素到栈中。或:入栈、推入、压入、push ▲出栈——从栈删除一个元素。或:退栈、上托、弹出、pop ▲栈顶-—表中允许插入、删除元素的一端(表尾)。 ▲栈顶元素一—处在栈顶位置的元素 栈底一表中不允许插入、删除元素的一端 ▲空栈-不含元素的栈
an a1 栈顶(top) 栈底(bottom) 出栈(pop) 进栈(push) ▲ 进栈----插入一个元素到栈中。或:入栈、推入、压入、push。 ▲ 出栈----从栈删除一个元素。或：退栈、上托、弹出、pop。 ▲ 栈顶----表中允许插入、删除元素的一端(表尾)。 ▲ 栈顶元素----处在栈顶位置的元素。 ▲ 栈底----表中不允许插入、删除元素的一端。 ▲ 空栈----不含元素的栈。 栈的示意图
▲栈的元素的进出原则:“后进先出”, Last in first out ▲栈的别名:《后进先出”表、“LIFO表、反转存储器、地窖、 堆栈 2.栈的基本操作 (1) Initstack(s)-置s为空栈。 (2)Push(s,e)--元素e进栈s。 若s已满,则发生溢出 若不能解决溢出,重新分配空间失败,则插入失败。 (3)Pop(s,e)-删除栈s的顶元素,并送入 若s为空栈,发生“下溢”( underflow) 为空栈时,表示某项任务已完成。 (4) Gettop(s,e)-栈s的顶元素拷贝到e。 若s为空栈,则结束拷贝 (5) Empty(s)-判断s是否为空栈。 若s为空栈,则 Empty(s)为true;否则为 false
▲ 栈的元素的进出原则: “后进先出” , “Last In First Out” 。 ▲ 栈的别名: “后进先出”表、“LIFO”表、反转存储器、地窖、 堆栈。 2.栈的基本操作 (1) Initstack(s)----置s为空栈。 (2) Push(s,e)----元素e进栈s。 若s已满，则发生溢出。 若不能解决溢出，重新分配空间失败，则插入失败。 (3) Pop(s,e)----删除栈s的顶元素，并送入e 。 若s为空栈,发生“下溢”(underflow)； 为空栈时，表示某项任务已完成。 (4) Gettop(s,e)----栈s的顶元素拷贝到e。 若s为空栈，则结束拷贝。 (5) Empty(s)----判断s是否为空栈。 若s为空栈,则Empty(s)为true；否则为false
3.模拟铁路调度站 输出端 输入端 A,B,C进栈 出 进栈 栈 调度站(栈) 讨论:⊙② 假设依次输入3个元素(车厢)A,B,C到栈(调度站)中, 可得当哪几种不同输出?
3.模拟铁路调度站 讨论： 假设依次输入3个元素(车厢)A,B,C到栈(调度站)中, 可得当哪几种不同输出？ 输入端 A,B,C 进栈 进 出 栈 栈 输出端 调度站(栈）