线性结构之栈
在说栈的前提下，我们先来说说什么是线性结构，线性结构是一种有序数据项的集合，其中每个数据项都有唯一的前驱和后继，除了第一个没有前驱，最后一个没有后继，新的数据项加入到数据集中时，只会加入到原有某个数据项之前或者之后，具有这种性质的数据集，就成为线性结构。
线性结构总有两端，在不同的情况下，两端的称呼也不同，有时候称为"左"、“右”端，有时候称为“前”、“后”端、有时候称为为“顶”、"底"端。
两端的称呼并不是关键，不同线性结构的关键区别在于数据项的增减方式。有的结构只允许数据从一端添加，而由的结构则允许数据项从两端移除。
栈Stack,队列Queue,双端队列Deque和列表List，这些数据集的共同点在于，数据项之间只存在先后的次序关系，都是线性结构。
栈Stack
什么是栈
一种有次序的数据项集合，在栈中，数据项的加入和移除都仅仅发生在同一端，这一端叫栈“顶top”，另一端叫栈“底base”。
日常生活中有很多栈的应用，比如盘子，书堆等等。
距离栈底最近的数据项，留在栈中的时间就越长，而最新加入栈的数据项会被最先移除。
这种次序通常称为“后进先出“，这是一种基于数据项保存时间的次序，时间越短的离栈顶越近，而时间越长的离栈底越近。
栈的特性：反转次序
我们观察一个由混合的Python原生数据对象形成的栈，如下图所示，进栈和出栈的次序正好相反。
这种访问次序反转的特性，我们在某些计算机操作上碰到过，浏览器的“后退”按钮，最先后退的是最近访问的网页。
抽象数据类型Stack
抽象数据类型“栈”是一个有次序的数据集，每个数据项仅从“栈顶”一端加入到数据集中，从数据集中移除，栈具有后进先出的特性。
-
抽象数据类型“栈”定义为如下的操作：
Stack()：创建一个空栈，不包含任何数据项
push(item):将item加入栈顶，无返回值
pop():将栈顶数据项移除，并返回，栈被修改
peek():"窥视"栈顶数据项，返回栈顶的数据项但不移除，栈不被修改
isEmpty():返回栈是否为空栈
size():返回栈中有多少个数据项
-
操作样例
Stack Operation Stack Contents Return Value s=Stack() [] Stack object s.isEmpty() [] True s.push(4) [4] s.push("dog") [4,"dog"] s.peek() [4,"dog"] "dog" s.push(True) [4,"dog",True] s.size() [4,"dog",True] 3 s.isEmpty() [4,"dog",True] False s.push(8.4) [4,"dog",True,8.4] s.pop [4,"dog",True] 8.4 s.pop [4,"dog"] True s.size() [4,"dog"] 2
用Python实现ADT Stack
在清楚地定义了抽象数据类型Stack之后，我们看看如何用Python来实现它，Python的面向对象机制，可以用来实现用户自定义类型。
将Stack实现为Python的一个Class
将Stack的操作实现为Class的方法
由于Stack是一个数据集，所以可以采用Python的原生数据集来实现，我们选用最常用的数据集List来实现
一个细节：Stack的两端对应List的设置。可以将List的任意一端（index=0或-1）设置为栈顶，我们选用List的末端（index=-1）作为栈顶，这样栈的操作就可以通过list的append和pop来实现。
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
return self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
s = Stack()
print(s.isEmpty()) # True
s.push(4)
s.push("dog")
print(s.peek()) # dog
s.push(True)
print(s.size()) # 3
print(s.isEmpty()) # False
s.push(8.4)
print(s.pop()) # 8.4
print(s.pop()) # True
print(s.size()) # 2
ADT Stack的另一种实现
如果我们把List的另一端(首端index=0)作为Stack的栈顶，同样也可以实现Stack。
不同的实现方案保持了ADT接口的稳定性，但性能有所不同，栈顶首端的版本其push/pop的复杂度为O(n),而栈顶尾端的实现，其push/pop的复杂度为O(1)。
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
return self.items.insert(0, item)
def pop(self):
return self.items.pop(0)
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
栈的应用
简单括号匹配
我们都写过这样的表达式：（5+6）*（7+8）/ (4+3)
当然，括号的使用必须遵循“平衡”规则，首先，每个开括号要恰好对应一个闭括号；其次，每对开括号要正确的嵌套。对括号是否正确匹配的识别，是很多语言编译器的基础语法。
下面我们看看如何构造括号匹配识别算法：
从左到右扫描括号串，最新打开的左括号，应该匹配最先遇到的右括号，第一个左括号（最早打开），就应该匹配一个右括号（最后遇到），次序反转的识别，正好符合栈的特性。
def parChecker(symbolString):
s = Stack()
balanced = True
index = 0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol == "(":
s.push(symbol)
else:
s.pop()
index += 1
if balanced and s.isEmpty():
return True
else:
return False
更多种括号匹配
在实际的应用中，我们会碰到更多的括号，如Python中列表所用的方括号“[]”,字典所用的花括号“{}”,元祖和表达式所用的圆括号"()"。
这些不同的括号可能会混合在一起使用，因此就要注意各自的开闭匹配情况。
那么我们可以把上面的代码改成通用匹配不？
我们依旧是碰到各种左括号仍然入栈，碰到各种右括号的时候需要判断栈顶的左括号是否跟它是同一类？
def parChecker(symbolString):
s = Stack()
balanced = True
index = 0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol in "([{":
s.push(symbol)
else:
top = s.pop()
if not matches(top, symbol):
balanced = False
index += 1
if balanced and s.isEmpty():
return True
else:
return False
def matches(open, close):
opens = "([{"
closers = ")]}"
return opens.index(open) == closers.index(close)
十进制转二进制
我们经常需要将整数在二进制和十进制之间转换，十进制转换为二进制，采用的是“除以2求余数”的算法，将整数不断除以2，每次得到的余数就是由低到高的二进制位。
“除以2”的过程，得到的余数是从低到高的次序，而输出则是从高到低，所以需要一个栈来反转次序。
def divideBy2(number):
s = Stack()
while number > 0:
rem = number % 2 # 求余
s.push(rem)
number //= 2 # 整除2
binString = ""
while not s.isEmpty():
binString += str(s.pop())
return binString
扩展到更多进制转换
十进制转换为二进制的算法，很容易可以扩展到转换为任意N进制，只需要将"除以2求余数"算法改为“除以N求余数”算法就可以了。
def baseConverter(number,base):
digits = "0123456789ABCDEF"
s = Stack()
while number > 0:
rem = number % base
s.push(rem)
number //= base
newString = ""
while not s.isEmpty():
newString += digits[s.pop()]
return newString