外观
3.1 栈
铁路调度站
火车站里有一种调度站,用来给车厢重新排顺序。它是一段尽头线:一头接着主线,另一头是死的。
车厢从右边的主线开进尽头线。要出来,只能倒回同一个口,开到左边的主线上去。
学完这一节,你能一眼看出一个出站顺序调不调得出来。
现在右边开来三节车厢,按1号、2号、3号的顺序进站。进出可以交替:开进几节之后,可以先开出几节,再接着开进。
调度员要把它们排成新的顺序开出去。他得先知道:按2、1、3开出去,能做到吗?按3、1、2呢?
本节问题哪些出站顺序做得到,哪些永远做不到?
调一调
先试2、1、3。
第一个要开出的是2号。2号还没进站,先让1号、2号开进去。这时2号在最外面,开出去。接着1号在最外面,开出去。最后3号开进来,再开出去。
2、1、3做得到。
再试3、1、2。
第一个要开出的是3号。先让1号、2号、3号都开进去,3号在最外面,开出去。下一个要开出1号,可是1号在最里面,2号挡在它外面。
尽头线只有一个口。1号要出去,得先让2号出去,那样开出的顺序就成了3、2、1。所以3、1、2做不到。
两次试下来,规律是:每次只能开出最外面那一节。
回到本节问题。按要开出的顺序,一节一节看。轮到的车厢还没进站,就让它和排在它前面的车厢依次开进来;它已经在站里,就必须在最外面。每一节都做得到,这个顺序就调得出来。只要有一节轮到时被挡在里面,这个顺序就永远做不到。
什么是栈
这样的调度站可以看成一个栈。
栈是只能在一端插入和删除的线性表。把调度站和栈的示意图放在一起,对照着看:
线性表。站里的车厢一节挨一节,排成一列:(1, 2, 3)。除了最里面和最外面的两节,每节车厢里面恰好挨着一节,外面恰好挨着一节,一个接一个。所以站里的车厢可以看成一个线性表。
线性表在2.1节讲过。
只能在一端插入和删除。能进出的那一端叫栈顶,另一端叫栈底。尽头线的开口是栈顶,尽头是栈底。现在3号在栈顶,1号在栈底。
插入叫入栈,删除叫出栈。车厢开进来是入栈,开出去是出栈。一节车厢都没有的时候,叫空栈。
普通的线性表可以在任意位置插入和删除。比如编辑器可以在一行字的中间插入一个字符。栈不行,只能动栈顶。所以栈是操作受限的线性表。
后进先出。上一页的规律是:每次只能开出最外面那一节。换成栈的说法,就是每次只能出栈栈顶。栈顶总是最后入栈的那一个,所以最后入栈的,最先出栈。这叫后进先出,也说成先进后出。
3号最后开进来,停在最外面,最先开出去。1号最先开进来,被2号、3号挡着,要等它们都出去。
练习1:哪个开出顺序做不到?
单选
1号、2号、3号、4号车厢按这个顺序开到调度站,进出可以交替。下面哪个开出顺序做不到?
A
4、3、2、1
四节全部开进去,再全部开出来,顺序正好倒过来。
B
1、2、3、4
每开进一节就马上开出这一节,每次出栈的都是刚入栈的那节。
C
3、4、2、1
1、2、3入栈,3出栈;4入栈,4出栈;这时2在栈顶,2出栈,最后1出栈。
D
4、2、3、1
4号开出时,1、2、3都在站里,3号在栈顶。下一个要开出2号,可2号被3号挡着,开不出来。
判断的办法:轮到一节车厢开出时,它要么还没进站,要么必须在栈顶。
练习2:出栈的顺序是什么?
填空
栈里放的不一定是车厢,可以是任何元素。从空栈开始,依次做下面七步:
a入栈,b入栈,出栈,c入栈,d入栈,出栈,出栈。
- 出栈的元素依次是 、、
- 七步做完,栈顶是
第一次出栈时,栈里是(a, b),栈顶是b。接着c、d入栈,栈里是(a, c, d),连续两次出栈,先出d,再出c。最后只剩a,它就是栈顶。
练习3:哪些可以看成栈?
多选
下面哪些东西可以看成一个栈?
A
浏览器的后退:每打开一个网页就记下来,按后退时回到最近记下的那一页
新网页记在最近的一头,后退也从最近的一头取,后进先出。
B
编辑器的撤销:每做一步就记下来,撤销时撤的是最近做的那一步
新的一步记在最近的一头,撤销也从最近的一头取,后进先出。
C
一摞盘子:洗好的放在最上面,用的时候从最上面拿
放和拿都在最上面这一端,最上面就是栈顶。
D
食堂排队打饭:新来的人排在队尾,打饭的是队头
进在一头、出在另一头,先来的先打,不是后进先出。
E
书架上的一排书:可以从中间抽出任意一本
能在任意位置删除,是普通的线性表,不是只能动一端的栈。
判断的办法:是不是只在一端放进去,也从同一端取出来。
到这里你有了栈的定义:只能在一端插入和删除的线性表。栈顶、栈底、入栈、出栈、空栈这几个名词,以及由此推出的后进先出。下一步栈要提供哪些操作?