- 算法设计与问题求解(第2版):计算思维培养
- 李清勇
- 2182字
- 2020-08-27 11:37:49
2.2.2 栈和队列
1.栈
栈是一种特殊的线性表,如图2-8所示。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。进行插入和删除的一端是浮动端,通常被称为栈顶,并用一个“栈顶指针”指示;另一端是固定端,通常被称为栈底。
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_40_1721_s.jpg?sign=1738821569-HKSnFi1LLtCF8TN3j4b9kbh1d1gMyWFz-0-33d929d0a352a09d2821fc59631c9449)
图2-8 顺序栈
栈具有后进先出(Last In First Out,LIFO)的特点,因此栈被称为LIFO线性表。
很多活动都具有LIFO的特点,比如:家里吃饭的碗,通常在洗干净后一个一个地摞在一起存放,在使用时,若一个一个地拿,一般先拿走最上面的那个碗,最后拿走最下面的那只碗。又如,在建筑工地上,使用的砖块从底往上一层一层地码放,在使用时,将从最上面一层一层地拿取。
栈结构的基本操作包括:
☢ 初始化栈,InitStack(S)。
☢ 入栈,Push(S,item)。
☢ 出栈,Pop(S,item)。
☢ 获取栈顶元素内容,GetTop(S, item)。
☢ 判断栈是否为空,StackEmpty(S)。
类似线性表,栈也有两种存储结构(或者说两种实现方式):顺序存储和链式存储。
(1)栈的顺序存储
栈的顺序存储是用一组连续的存储单元依次存放栈中的每个数据元素,并用起始端作为栈底。其类型定义如下:
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_40_37891_l.jpg?sign=1738821569-Akp8mMRskCg6OWjkO2swAjhBznAFuuhp-0-98652e727bbb91054250da0a8278a469)
其中,StackEntry是数据元素类型的抽象表示,其结构体的定义需要具体问题具体分析。顺序栈的基本操作伪代码描述如下。
① 初始化栈S
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_40_47718_l.jpg?sign=1738821569-4goh57RLixFpjH7biiObnhbpHownktPz-0-1e5c6800c608db5947d8b612dc987c62)
② 入栈
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_40_53799_l.jpg?sign=1738821569-g0c7F7nSfcyQLYOBcn0zakmePzPF70Zl-0-d2648f00aa45b9b6b55cf77ac8fe665f)
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_41_0169_l.jpg?sign=1738821569-KwwV7QG2z5curLe7AQBsDHCsZBdsPiSI-0-5c8c5f9144c2d62f8dc5d1e0d65b43bc)
③ 出栈
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_41_6393_l.jpg?sign=1738821569-h4p6Ftl5w7XeHtam5bAxIbep9FNSgcaK-0-15d4be83d0a7dd14289584f9dece8ef6)
④ 获取栈顶元素内容
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_41_13271_l.jpg?sign=1738821569-JJFp2YrM6vIDWj4TN9Cn11d4hNSqoXvn-0-f54d67e9ca4e0b3fe012e53800ad7a87)
⑤ 判断栈S是否为空
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_41_19984_l.jpg?sign=1738821569-PfApaKLLwsvzvAALKy8wAy04EI0ujQ4L-0-e3ac07d9daa57fdf793c4ce56d1f893b)
由于栈的插入和删除操作具有它的特殊性,因此用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题,但栈容量是固定的,无法动态扩充。若是栈中元素的数目变化范围较大或不清楚栈元素的数目,就应该考虑使用链式存储结构。
(2)栈的链式存储
人们将用链式存储结构表示的栈称为链栈。链栈通常用一个无头结点的单链表表示,如图2-9所示。
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_41_37997_s.jpg?sign=1738821569-IFxaJt8ODldLRs4gENKBnyE0LA6AxPdL-0-656986f2edb2226886ebb309f7b7c946)
图2-9 链栈
由于栈的插入删除操作只能在一端进行,而对于单链表来说,在首端插入删除结点要比尾端相对容易一些,因此我们将单链表的首端作为栈顶,即将单链表的头指针作为栈顶指针。
链栈的结点定义如下:
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_41_12209_l.jpg?sign=1738821569-2WkZ2PV2z3bLxP1LlisbPZTtf7MgJOMh-0-2bea62eee18077b3289051ed8bf99332)
其中,StackEntry是数据元素类型的抽象表示,其结构体的定义需要具体问题具体分析。然后,通过指定链表的头结点得到链栈的定义:
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_42_30881_l.jpg?sign=1738821569-ELw5x9RRpw6cTKdgHktoEKPObcnpUdLt-0-ceace9457bde2ac2ebab5d3a15559c7e)
链栈的基本操作伪代码描述如下。
① 初始化栈S
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_42_41961_l.jpg?sign=1738821569-RvJfOLzOQrrvBI81y8t4n85EDYNgztz1-0-548953198e05c003214fae149adb68c9)
② 入栈
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_42_4760_l.jpg?sign=1738821569-CpFW8z27wP50x66kZHvhLVmViJFNx4Fr-0-61e5ebc1d607798c864681e0790fac7a)
③ 出栈
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_42_52687_l.jpg?sign=1738821569-2PLKiYPXz7MNQNURBSFnVsdYyOcrFHfO-0-d060dfff764a70d42d3d618b789b2030)
④ 获取栈顶元素内容
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_42_58829_l.jpg?sign=1738821569-T5YdYklF57w1weWdXQFcBWUTFxTFN27j-0-301aeae543b874c796c71bac5f09972a)
⑤ 判断栈S是否空
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_42_4685_l.jpg?sign=1738821569-y3cXoW0ABTV6ZDnHXxeMgcZsNJThXQQF-0-3a9efc0dc746c4272b6727f01ec3fc6f)
2.队列
队列也是一种特殊的线性表,它限定插入操作在线性表的一端进行,删除操作在线性表的另一端进行,如图2-10所示。
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_43_16789_m.jpg?sign=1738821569-QDaQSl5jypxi529giAqVDTfxsutm94WT-0-7e756184ec8268b8ee1d2751d06ecf2d)
图2-10 队列
在队列中,插入端和删除端都是浮动的。通常,插入端被称为队尾,用“队尾指针”指示;删除端被称为队头,用“队头指针”指示。显然,在队列中先插入的元素将被先删除,即具有先进先出(First In First Out,FIFO)的特性,队列也被称为FIFO线性表。
很多活动都具有FIFO的特点,比如:到医院看病,先挂号的病人先就诊;乘坐公共汽车,排在前面的乘客先上车;又如,在Windows这类多任务的操作系统环境中,每个应用程序响应一系列的“消息”,如用户点击鼠标、拖动窗口这些操作都会导致向应用程序发送消息。为此,系统将为每个应用程序创建一个队列,用来存放发送给该应用程序的所有消息,应用程序的处理过程就是不断地从队列中读取消息,并依次给予响应。
队列结构的基本操作包括:
☢ 初始化队列,InitQueue(Q)。
☢ 入队,EnQueue(Q,item)。
☢ 出队,DeQueue(Q, item)。
☢ 获取队头元素内容,GetFront(Q, item)。
☢ 判断队列是否为空,QueueEmpty(Q)。
类似栈,队列也存在顺序存储和链式存储两种方式。
(1)顺序存储队列
顺序存储队列用一组连续的存储单元依次存放队列中的每个数据元素,并指定队头(Front)和队尾(Rear)指针,如图2-11所示。
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_43_5715_m.jpg?sign=1738821569-Gfoh8U5DYwtdSMwxPFIWvgKu7MGP9ilf-0-34af3a8becc02b7345d42583c7387172)
图2-11 顺序存储队列
具体实现时,顺序存储队列存在两个问题。
问题1:当队列为空时,队头和队尾指针都为-1,此时若进行入队操作,需要让队头和队尾指针都增1,再将新数据元素放入该位置。而当队列非空时,入队操作只需要队尾指针增1。如果在实现程序中对这两种情况加以区分,这将增加算法的复杂性。
解决方法:队头指针指向队列真正队头元素的前一个位置。
问题2:顺序存储结构的存储空间属于静态分配,在添加数据元素时,可能出现在队列末端没有剩余空间,但是队列前端存在可用空间的情况,即“假溢出”现象。
解决方法:将存储队列元素的一维数组首尾相接,形成一个环状,如图2-12所示,即循环队列。
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_44_23531_s.jpg?sign=1738821569-WNxuBT4HHIF1FS7f7YoKrVidNYjiUl9p-0-26a83cbc89f70de6df6bf53550193012)
图2-12 循环队列
假设为队列开辟的数组单元数目为MAX_QUEUE,在C语言中,它的下标为0~MAX_QUEUE-1,若增加队头或队尾指针,则可以利用取模运算(一个整数数值整除以另一个整数数值的余数)实现,其运算如下:
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_44_757_l.jpg?sign=1738821569-doNAmcj5ty0UzlHwc8KvtVPrnFVVVT1R-0-501463cd517643e074ca03b7b18f83e1)
当front或rear为MAX_QUEUE-1时,上述两个公式计算的结果就为0。这样使得指针自动由后面转到前面,形成循环的效果。
在上述循环队列中,当队列变为空时,队头和队尾指针相等。当队列变为满时,队头和队尾指针也相等。为了区分队列“空”和“满”两种情况,约定当数组只剩下一个空闲单元时就认为队满,此时队尾指针只差一步追上队头指针,即:
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_44_13471_l.jpg?sign=1738821569-1A2wKIuvuaZEbaCFirZAz1vcB7aWpXdK-0-69567fe3fcfdc40125a6f12fda8fbda3)
综上所述,循环队列结构可以定义为:
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_44_4267_l.jpg?sign=1738821569-WmMiDZI7p82CwMwLw9MJfurEB6Y4oGI1-0-014b92763087a0799dc148a541d1d86b)
其中,QueueEntry是数据元素类型的抽象表示,其结构体的定义需要具体问题具体分析。
循环队列的基本操作定义如下。
① 初始化队列Q
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_44_53889_l.jpg?sign=1738821569-Fd5uObZhGPrhpc2DpFqM6flNe9wj1vE9-0-2f8d6bb2342fe0f15946201280cdbce8)
② 入队
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_44_59725_l.jpg?sign=1738821569-mx7uKi50ocFdR008AYdrWcpjXxrO0k6y-0-cf992c7a743a173fcda014535fe0706f)
③ 出队
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_44_6526_l.jpg?sign=1738821569-NtlS49qYKhXOuwCqvSdo5ihVvPJnhIB5-0-ff6280d5dde08af04e59da189bc783af)
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_45_1678_l.jpg?sign=1738821569-ZTjltxca7zh6BXzoZJmIGYFjRgfXEmvC-0-5e555c4c73dfde17b78c28895fb2ee92)
④ 获取队头元素内容
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_45_21873_l.jpg?sign=1738821569-PgN5bYztzGd3dciBrv7TapFqnWA9TrPR-0-d41bdda067c5d452ffb5f8aff2e7c4bf)
⑤ 判断队列Q是否为空
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_45_28118_l.jpg?sign=1738821569-uWdF0gxpP5bG3CC8GdCiNXNM2LqqMpWA-0-938ed5ff833f4a4e8404cb8f4f312832)
(2)链式存储队列
在用链式存储结构表示队列时,需要设置队头指针和队尾指针,以便指示队头结点和队尾结点,如图2-13所示。
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_45_34866_m.jpg?sign=1738821569-H58GGJkQKPO8ydtqxcM6VCpNvwioUnFt-0-58861e65cb971500c5c0255a26b43b22)
图2-13 链式存储队列
链式存储队列的结点结构定义如下:
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_45_56459_l.jpg?sign=1738821569-nX346qkgVdNQTqXYLT6YrUvmCAr3suNo-0-fc2bc3b31dddad3399a28615af3321cc)
其中,QueueEntry是数据元素类型的抽象表示,其结构体的定义需要具体问题具体分析。然后,链式存储队列可通过队头指针和队尾指针定义:
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_45_12383_l.jpg?sign=1738821569-KZT2rcYBCDwvfZSQHmQbrGHLtOb67H0I-0-fe0fcb59fc1c769e20f1eb674368f818)
链式存储队列的基本操作可以定义如下。
① 初始化队列Q
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_45_19994_l.jpg?sign=1738821569-pS0mAyoOBpqGYBD2Wy5BU2IAILK4SLdD-0-7d8fef0fd2950365602480329cfa28fc)
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_46_25412_l.jpg?sign=1738821569-GVtPwixj4J2VOvHXY1piIw0lJuXodQ7a-0-3527d03a0a06c6316777a061f0d26216)
② 入队
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_46_30716_l.jpg?sign=1738821569-XSUwecxyU1heuQWL8eya2HQl4iMGP1JE-0-bc8eca6b55b677f04feeddd96b282537)
③ 出队
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_46_35495_l.jpg?sign=1738821569-4qMZYzyFspiJUSTqtMKQCYtGWXIhBSS8-0-9d913329c621b96f578c617af903ccbe)
④ 获取队头元素内容
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_46_41728_l.jpg?sign=1738821569-CNYn9V9Rb4mWrYSHLs7yFAR3cutsswsz-0-64801e78e9afce2fb5ded43d63d46368)
⑤ 判断队列Q是否为空
![](https://epubservercos.yuewen.com/9BC028/17545850807267206/epubprivate/OEBPS/Images/cutq_46_47761_l.jpg?sign=1738821569-F334MyCQeLgp5cZgUmuAjr4xNhEYk9ql-0-34c66ca815e80ea7c12725bdaae21556)
STL提供stack和queue类来实现栈和队列的功能,具体调用方法见附录B。