的 华中科技大学 计算机学院(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 进栈 进 出 栈 栈 输出端 调度站(栈）
(1)输入A,B,C,产生输出A,B,C的过程: B. C A B. C A C A B 1)A进栈 (2)A出栈 (3)B进栈 A B C A. B A,B C (4)B出栈 (5)C进栈 (6)C出栈
(1)输入A,B,C,产生输出A,B,C的过程： A B,C (1)A进栈 B,C (2)A出栈 B C (3)B进栈 (4)B出栈 C (5)C进栈 (6)C出栈 C A,B,C A A,B A,B A
(2)输入A,B,C,产生输出C,B,A的过程: B C C 1|于 C B B A A A (1)A进栈 (2)B进栈 (3)C进栈 C C. B B A C (4)C出栈 (5)B出栈 (6)A出栈
(2)输入A,B,C,产生输出C,B,A的过程： A B,C (1)A进栈 B A C (2)B进栈 C B A (3)C进栈 B A (4)C出栈 C (5)B出栈 (6)A出栈 C C,B C,B,A
(3)输入A,B,C,产生输出B,C,A的过程: B. C B A BA A (1)A进栈 (2)B进栈 (3)B出栈 B B. C B.C. A A A (4)C进栈 (5)C出栈 (6)A出栈
(3)输入A,B,C,产生输出B,C,A的过程: A B,C (1)A进栈 B A C (2)B进栈 A C (3)B出栈 C A (4)C进栈 A (5)C出栈 (6)A出栈 B B,C B,C,A B
(4)输入A,B,C,不能产生输出C,A,B: A.B. C C B B A A (1)初始状态(2)A,B,C进栈 (3)C出栈 当A,B,C依次进栈,C出栈后,由于栈顶元素是B,栈底 元素是A,而A不能先于B出栈,所以不能在输出序列中,使A 成为C的直接后继,即不可能由输入A,B,C产生输出C,A,B。 般地,输入序列(..,ai,,aj,,ak,,)到 栈中,不能得到输出序列(.,ak, al
当A,B,C依次进栈，C出栈后，由于栈顶元素是B,栈底 元素是A,而A不能先于B出栈,所以不能在输出序列中, 使A 成为C的直接后继, 即不可能由输入A,B,C产生输出C,A,B。 一般地，输入序列(...,ai,...,aj,...,ak,...)到 栈中,不能得到输出序列(...,ak,...,ai,...,aj,...)。 (1)初始状态 C B A (2)A,B,C进栈 B A (3)C出栈 A,B,C C (4)输入A,B,C,不能产生输出C,A,B:
设依次输入元素A,B,C到栈中,可得哪几种输出?⊙⊙⊙ A,B C (1)A,B,C (2)A,C,B (3)B,A,C (4)B,C,A (5)C,A,B (6)C,B,A 设依次输入元素C,B,A到栈中,可得哪几种输出?②⊙⊙ C.B. A (1)A,B,C (2)A,C,B (3)B,A,C (4)B,C,A (5)C,A,B (6)C,B,A
设依次输入元素A,B,C到栈中,可得哪几种输出? 设依次输入元素C,B,A到栈中,可得哪几种输出? A,B,C (1) A,B,C (2) A,C,B (3) B,A,C (4) B,C,A (5) C,A,B (6) C,B,A C,B,A (1) A,B,C (2) A,C,B (3) B,A,C (4) B,C,A (5) C,A,B (6) C,B,A