栈
下压栈(或简称栈)是一种基于后进后出的(LIFO)策咯的集合类型.
其中添加移除新项总发生在同一端。这一端通常称为“顶部”。与顶部对应的端称为“底部”。栈的例子很常见,想象桌上有一堆书., 只有顶部的那本书封面可见，要看到其他书的封面，只有先移除他们上面的书.
image
下图反应了栈中数据加入和移走的顺序：
image
栈的抽象数据类型
一个栈一般会实现以下方法：
-
Stack()构造方法，创建一个空栈，无参数，返回值是空栈 -
push(value)向栈顶压入一个新数据项，需要一个数据项参数，无返回值 -
pop()抛出栈顶数据项，无参数，返回被抛出的数据项，栈本身发生变化 -
is_empty()测试栈是否空栈。不需要参数，返回布尔值 -
size()返回栈内数据项的数目，不需要参数，返回值是整数 -
peak()返回栈顶数据项，但不删除。不需要参数，栈不变
栈的python实现(一)
利用.append与.pop方法,我们可以把python内置的列表当作栈来使用(栈是一种特殊的列表),这是一种较为方便的实现方式
class Stack:
def __init__(self):
self.values = []
def push(self, value):
self.values.append(value)
def pop(self):
return self.values.pop()
def is_empty(self):
return self.size() == 0
def size(self):
return len(self.values)
def peak(self):
return self.values[self.size()-1]
栈的python实现(二)
或者自由定义类似列表的Stack类
class Node: ➊
def __init__(self, value):
self.value = value
self.next = None
class Stack: ➋
def __init__(self):
self.top = None
def push(self, value):
node = Node(value)
node.next = self.top
self.top = node
def pop(self):
node = self.top
if node is None:
raise Exception('This is an empty stack')
self.top = node.next
return node.value
def peek(self):
node = self.top
if node is None:
raise Exception('This is an empty stack')
return node.value
def is_empty(self):
return not self.top
def size(self):
node = self.top
count = 0
if node is None:
raise Exception('This is an empty stack')
while node is not None:
count += 1
node = node.next
return count
if __name__ == '__main__':
stack = Stack()
stack.push(2)
stack.push(3)
# print(stack.pop())
# print(stack.top.value)
print(stack.peek())
print(stack.is_empty())
print(stack.size())
➊ 定义一个结点
image
➋ 定义一个栈
image
top指向栈顶的Node,next之想下一个Node,若没有下一个Node,则指向一个None
栈的应用
十进制转二进制 是一个应用堆栈的典型案例。十进制转二进制 采用“除2取余，逆序排列”的方法，如图所示：
image
借助Stack类，可以很方便地实现上述转换算法：
def divideBy2(decNumber):
remstack = Stack()
while decNumber > 0:
rem = decNumber % 2
# 将余数逐个加入
remstack.push(rem)
decNumber = decNumber // 2
binString = ""
while not remstack.is_empty():
binString = binString + str(remstack.pop())
return binString
if __name__ == '__main__':
print(divideBy2(42))
运行结果:
$ python dec2bin.py
101010
相关链接
http://zhaochj.github.io/2016/05/14/2016-05-14-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%A0%88/
http://www.cnblogs.com/russellluo/p/3282563.html
https://facert.gitbooks.io/python-data-structure-cn/3.%E5%9F%BA%E6%9C%AC%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/3.3.%E4%BB%80%E4%B9%88%E6%98%AF%E6%A0%88/
