第3章

栈 和 队 列



3．1栈结构
栈(Stack)是一种线性的存储结构，它具有如下特点： 
(1) 栈中的数据元素遵守先进后出(First In Last Out,FILO结构)的原则。
(2) 限定只能在栈顶进行插入和删除操作。


图31栈结构

如图31所示。
打个比方，栈就像一摞盘子，一个个的盘子摞成一叠，只能从最上面添加或拿走。最先放下的盘子在最底下，最后才能拿出，最后放下的盘子在最上面，最先被拿出。栈的常用操作如下(用一摞盘子比喻)： 
(1) 入栈： 就是向栈中添加元素，只能从最上面添加，通常命名为push。
(2) 出栈： 也可称为弹栈，就是从栈中取出元素，只能从最上面取出，通常命名为pop。
(3) 求栈的大小，返回栈中有多少个元素。
(4) 判断栈是否为空，如果栈中无元素，返回True； 如果栈中有元素，返回False。


视频讲解


下面看例31的代码结构。
【例31】栈结构包括栈的节点类、主结构类和测试代码。
(1) 节点类(node．py)包括： 栈节点的值value和指向前一个节点的指针pre。

class Node:

def __init__(self,value):

self.value=value#栈节点的值

self.pre=None#指向前一个节点的指针

(2) 主结构类(stack．py)包括如下内容： 
成员变量： 栈顶指针point，栈长度length。
成员方法： 入栈方法push，出栈方法pop，判断栈是否为空方法isNone。

from node import Node

class Stack:

def __init__(self):#栈初始化

self.point=None#定义栈顶指针

self.length=0#栈中节点总数

def push(self,value):#向栈中压入数据方法

node = Node(value)#把压入栈中的数据包装成栈节点

if self.point!=None:#假如栈顶指针不为空

node.pre = self.point#后压入栈的节点指向前一个节点

self.point = node#栈顶指针指向新压入栈的新节点

else:#假如栈顶指针为空

self.point = node#栈顶指针指向栈中唯一的节点

self.length += 1#栈中总数加1

def pop(self):#从栈中弹出数据方法

if self.point!=None:#假如栈顶指针不为空

node = self.point#获得栈顶指针指向的节点

self.point = node.pre #栈顶指针向前一个节点移动

node.pre = None#把栈顶节点的向前指针置为空

self.length -= 1#栈中节点总数减1

return node.value#返回弹出节点的值

else:#如果栈内没有节点

return None#返回空



def isNone(self):#栈的判空方法

if self.length>0:#假如栈内节点总数大于0

return False#返回False

else:#假如栈内节点总数等于0

return True#返回True

(3) 测试代码(test．py)。

from stack import Stack

stack = Stack()

for ii in range(5):#向栈中压入5个数字

print(ii)

stack.push(ii)

print(stack.isNone())#判断栈是否为空

print('--------------------')

for ii in range(stack.length):#从栈中依次弹出压入的元素

print(stack.pop())

print(stack.isNone())#判断栈是否为空

以上代码运行结果如图32所示。


图32栈结构压入和弹出5个数字并判空


3．2用栈做十进制与二进制的转换
十进制转换成二进制的对应表如表31所示。


表31十进制转换成二进制的对应表



十进制二进制十进制二进制
006110
117111
21081000
31191001
4100…………
5101

思路： 十进制整数转换为二进制整数采用“除2取余，逆序排列”法。具体做法： 除数始终是2，用2整除十进制整数，可以得到一个商和余数； 再用2去除商，又会得到一个商和余数，如此进行，直到商为0时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。


图336转换为二进制

的结果为110


假设将十进制6转换成二进制，方法如下： 
6/2=3余0余数为二进制第3位
3/2=1余1余数为二进制第2位
1/2=0余1余数为二进制第1位
以上余数倒序排列为110，就是十进制6转换为二进制的换算数，如图33所示。
下面看例32的代码。


视频讲解


【例32】用栈做十进制转换成二进制(test．py)。

from stack import Stack#引用3.1节中的栈

import math

def tenToTwo(n):

if n>1:#如果传入的自然数大于1

stack = Stack()

temp = n

while(temp>0):#如果除后的结果大于0

mod = temp%2#对2取余

stack.push(mod)#余数压入栈中

temp = math.floor(temp/2)#除2后向下取整

v = stack.pop()

while(stack.isNone()==False):#循环弹出栈中结果

v = v*10+stack.pop()

return v

else:#如果传入的自然数小于或等于1

return n#直接把0或1返回

print(tenToTwo(6))#把6转换成二进制

print(tenToTwo(9))#把9转换成二进制

以上代码运行结果如图34所示。


图346和9十进制转换为二进制的执行结果


3．3最小栈
所谓最小栈，就是当前栈顶元素的值始终是栈中元素的最小值。其实现方式： 
每次入栈时进行判断，如果小于或等于栈顶元素，直接入栈； 如果大于栈顶元素，栈先执行弹栈操作，然后把新值压入，最后把弹出的节点重新压回栈内，如图35所示。


图35最小栈入栈操作步骤

接着看例33的代码。


视频讲解


【例33】最小栈包括最小栈代码和测试代码。
(1) 最小栈(minstack．py)。

from node import Node

class MinStack:

def __init__(self):

self.point=None

self.length=0

def push(self,value):#压栈方法

node = Node(value)

if self.point!=None:

#和栈顶元素的值进行比较,如果大于栈
#顶元素,先弹栈,再压栈新元素,再把弹
#出的元素重新入栈

#如果小于栈顶元素,直接压入

if node.value>self.point.value:#入栈的新元素大于当前的栈顶元素

minV = self.pop()#先弹出栈顶元素

self.add(node)#新节点先入栈

self.length +=1#补充POP时的减1动作

self.add(Node(minV))#再把刚才弹出的栈压入

else:

self.add(node)#直接压入

else:

self.point = node

self.length += 1

def add(self,node):#节点入栈方法

node.pre = self.point#入栈节点前向指针指向原栈顶节点

self.point = node#栈顶指针指向新入栈节点

def pop(self):#弹栈方法

if self.point!=None:

node = self.point#获得栈顶节点

self.point = node.pre#栈顶指针指向栈顶节点的前1节点

node.pre = None#原栈顶节点前向指针置空

self.length -= 1#栈中节点总数减1

return node.value

else:

return None



def isNone(self):#判断栈是否为空

if self.length>0:

return False

else:

return True

(2) 测试代码(test.py)。

from minstack import MinStack

mstack = MinStack()#实例化最小栈

lst = ［9,6,15,4,21,7,3,34,5,18,21,17］

slen = len(lst)#取列表长度

for ii in range(slen):#循环压入最小栈

mstack.push(lst［ii］)

print(mstack.pop())#弹出栈顶元素

执行test．py，代码运行结果如图36所示。


图36向最小栈中压入一些数据，弹出栈顶元素，确定是其中最小值


3．4队列
队列(Quence)和栈一样，是一种操作受限制的线性表。它只允许在表的后端(rear)进行插入操作，称为入队； 
在表的前端(front)进行删除操作，称为出队。所以最早进入队列的元素会最先从队列中删除，故队列又称为先进先出(First In First Out，FIFO)的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
其结构描述： 建立顺序队列结构，必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素； 另一个是队尾指针rear，指向下一个入队元素的存储位置。
队列的实现方式有如下两种： 
(1) 数组方式： 根据数据量定义一个数组，以front指向队首元素，值始终为数组首元素a［0］。入队时，根据队列大小将元素存储到相应位置。出队时，front保持不变，删除队首元素，其余元素依次向前移动，队尾指针rear向前移动，时间复杂度为O(N)。上述实现因为不断移动元素，效率太低。


图37链表方式实现队列结构

(2) 链表方式： 队列中每个元素为一个节点，节点包含值和指向后一个节点的指针。头指针front指向队首节点，尾指针rear指向队尾节点。入队时，队尾节点的节点指针指向新入队节点，队尾指针再指向新入队节点。出队时，队首节点弹出，front节点指向后一个节点。此实现方式效率较高，且可自由伸展队列长度，但所占空间略大于数组方式，如图37所示。

队列的基本操作包括入队操作、出队操作、取长度、判断队列是否为空。下面看例34的代码。


视频讲解


【例34】队列。
(1) 队列节点类 (node．py)。

class Node:

def __init__(self,value):

self.value=value#数据映射

self.next=None#指向后一个节点的指针

(2) 队列类 (quence．py)。

from node import Node

class Quence:

def __init__(self):

self.head=None#队列头指针

self.rear=None#队列尾指针

self.length=0#队列中元素长度

def inQue(self,value):#入队

node = Node(value)

if self.head!=None:#如果队列头指针不为空

self.rear.next = node#尾指针所在节点的next指向新节点

self.rear = node#尾指针指向新节点

else:

self.head=node#如果队列为空，头尾指针都指向新进的节点

self.rear=node

self.length += 1



def outQue(self):#出队

node = self.head

if node.next!=None:#如果不是最后一个节点

self.head = node.next#队列头指针指向队列中的第2个节点

node.next = None

else:#如果是最后一个节点

self.head = None#头指针置空

self.rear = None#尾指针置空

self.length -= 1

return node.value

def isNone(self):#判断队列是否为空

if self.head!=None:

return False

else:

return True

(3) test.py(测试代码)。

from quence import Quence

quence = Quence()

for ii in range(10):#队列中入队10个数字

quence.inQue(ii)

for ii in range(quence.length):#顺序出队

print(quence.outQue())

执行test．py，运行结果如图38所示。


图38向队列中压入10个数字，再顺序出队


3．5两个栈实现一个队列

解题思路： 栈是先进后出，队列是先进先出，a、b两个栈中以a栈为入栈，b栈为出栈，通过两个栈之间的数据互导实现队列的先进先出。程序步骤如下： 
(1) 声明a、b两个栈。
(2) 入队操作： 首先判断b栈是否为空，如果为空，直接向a栈压入数据； 如果不为空，将b栈中所有元素依次弹回a栈，然后向a栈压入新元素。
(3) 出队操作： 首先判断b栈是否为空，如果不为空，直接从b栈中弹出元素； 如果为空，则先将a栈中的数据全部依次弹出，随即顺序压入b栈，然后再从b栈弹出元素。
(4) 再入队操作： 首先判断b栈是否为空，如果不为空，先将b栈中的元素依次弹出，顺序压入a栈，直到b栈为空，然后再将新数据压入a栈。
(5) 再出队操作： 首先判断b栈是否为空，如果不为空，直接从b栈中弹出元素； 如果为空，则先将a栈中的数据全部依次弹出，随即顺序压入b栈，然后再从b栈弹出元素。
两个栈实现一个队列的算法图解分析如图39所示。


图39两个栈实现一个队列的算法图解分析



图39（续）


代码实现方式见例35。


视频讲解


【例35】用两个栈实现一个队列。
(1) 栈代码(stackque．py)。

from stack import Stack

class StackQue:

def __init__(self):

self.a = Stack()

self.b = Stack()

def appendTail(self,value):#向队列中加入数据

if self.b.isNone()==False:#假如b栈不为空

blen = self.b.length

for i in range(blen):

self.a.push(self.b.pop())

self.a.push(value)

def deleteHead(self):#从队列中删除数据

if self.b.isNone():#假如a栈不为空

alen = self.a.length

for i in range(alen):

self.b.push(self.a.pop())

return self.b.pop()

(2) 测试代码(test.py)。

from stackque import StackQue

stackque = StackQue()

for i in range(5):#向队列中添加5个数

stackque.appendTail(i)

for i in range(2):#从队列中删除2个

print(stackque.deleteHead())

for i in range(7,10):#再向队列中加入3个

stackque.appendTail(i)

for i in range(10):#全部从队列中出队

print(stackque.deleteHead())

测试代码运行结果如图310所示。


图310执行test．py后的效果


3．6以递归方式反转一个栈


以递归方式反转一个栈，要求不得重新申请一个同样的栈。


图311以递归方式反转栈步骤分解

思路： 栈中的节点原本是从栈顶节点依次指向下一个节点直到栈底，反转后栈顶指针指向栈底，栈底节点的下一个指针指向原先的上一个节点直到栈顶。因为栈的起始位置是从栈顶指针开始的，这样就达到了栈中节点序列相反的目的。实现方式其实有很多种，这里使用递归调用的方式让每一个节点后一个节点的pre指针反指向本节点，步骤如图311所示。
代码实现见例36。
【例36】以递归方式反转一个栈结构。



视频讲解



from stack import Stack#引入3.1节中的栈

from node import Node#引入3.1节中的节点

stack = Stack()

def rev(node):#反转方法

global stack

preNode = node.pre

if preNode!=None:#假如没到最后一个节点

rev(preNode)#节点反转前，先递归调用下一个节点的反转方法

preNode.pre = node#让下一个节点指针反指向自己

else:

stack.point = node#到最后一个节点，栈顶指针指向最后一个节点

for i in range(1,6):#向栈中压入6个数字

stack.push(i)

node = stack.point#拿到栈顶节点

rev(node)#调用反转方法

node.pre = None#原栈顶节点(变尾节点)的next指针必须置为None

for i in range(stack.length):

print(stack.pop())

代码运行结果如图312所示。


图312栈应先进后出，即5，4，3…反转后呈1，2，3…


3．7递归加栈实现汉诺塔

汉诺塔(又称河内塔)问题是源于印度的一个古老传说。大梵天创造世界时做了三根金刚石柱子，在一根柱子上从上往下按照由小到大的顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘重新摆放在另一根柱子上，顺序同样是从上往下由小到大摞列。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
把要求简述如下： a、b、c三根柱子，a上有从上到下按从小到大顺序摞着一列圆盘，现要求把a柱子上所有的圆盘移动到c柱子上。移动规则如下： 
(1) 三根柱子之间一次只能移动一个圆盘。
(2) 任何情况下，大圆盘不能放在小圆盘上面。
解题思路： 把柱子按用途定义为源柱子(初始是a柱)、中间柱子(初始是b柱)和目标柱子(初始是c柱)。三个用途在三根柱子中是来回切换的。
算法分析： 递归过程就是把步骤分解成下面的三个子步骤。

(1) 假设源柱子上落有n个盘子，将前n-1个盘子从源柱子移动到中间柱子上。
(2) 将最底下的最后一个盘子从源柱子移动到目标柱子上。
(3) 将中间柱子上的n-1个盘子移动到目标柱子上。
然后每个子步骤又是一次独立的汉诺塔游戏，也就可以继续分解目标直到n为1。
注意： 源柱子、中间柱子和目标柱子在每一个子步骤中是不同的，每次操作的步骤都是为了把底座盘子移动到目标柱子上，因此必须先把底座上面的盘子全移动到中间柱子上。而底座上面的盘子又可视为一个独立的汉诺塔游戏，需要用上述逻辑再次拆解，直到拆解到只剩一个盘子为止。
(1) 当a柱上只有一个盘子时，直接将盘子移动到c柱上，如图313所示。


图313a柱上的盘子直接移动到c柱上


(2) 当a柱上有2个盘子时，操作步骤如图314所示。


图314汉诺塔上有2个盘子时的操作步骤


(3) 当a柱上有3个盘子时，操作步骤如图315所示。


图315汉诺塔上有3个盘子时的操作步骤













图315（续）



下面看例37的代码。


视频讲解


【例37】以递归加栈的方式实现汉诺塔算法。
(1) 栈(stack．py)代码中添加一个元素name。

from node import Node

class Stack:

def __init__(self):

self.point=None

self.length=0

self.name = None#为了给柱子加个名字

(2) 测试代码(test.py)中实现汉诺塔。

from stack import Stack

a = Stack()#声明1个栈

a.name = 'A'#第1根柱子起名叫A

b = Stack()#声明b柱子

b.name = 'B'

c = Stack()#声明c柱子

c.name = 'C'

def move(n,s1,s2,s3):#递归，层层分解

if n!=1:

move(n-1,s1,s3,s2)#把底座上面所有盘子移动到中间柱子上

move(1,s1,s2,s3)#移动底座盘子到目标柱子上

move(n-1,s2,s1,s3)#把中间柱子上的盘子移动到目标柱子上

else:#当只剩一个盘子时

#s1->s3

s3.push(s1.pop())#把盘子移动到目标柱子上

print(s1.name,'=>',s3.name)

#测试

for ii in range(4,0,-1):#向a柱上压上4,3,2,1共4个盘子

a.push(ii)

n = a.length

move(n,a,b,c)

for ii in range(n):#打印c柱上的盘子编号

print(c.pop())

上述代码运行结果如图316所示。


图316汉诺塔上有4个盘子情况下的移动步骤和c柱上最后的盘子罗列情形