棧
下壓棧(或簡稱棧)是一種基于后進后出的(LIFO)策咯的集合類型.
其中添加移除新項總發(fā)生在同一端织阳。這一端通常稱為“頂部”官脓。與頂部對應(yīng)的端稱為“底部”川队。棧的例子很常見,想象桌上有一堆書., 只有頂部的那本書封面可見呼奢，要看到其他書的封面酷勺，只有先移除他們上面的書.
image
下圖反應(yīng)了棧中數(shù)據(jù)加入和移走的順序：
image
棧的抽象數(shù)據(jù)類型
一個棧一般會實現(xiàn)以下方法：
-
Stack()構(gòu)造方法戴已，創(chuàng)建一個空棧固该，無參數(shù)，返回值是空棧 -
push(value)向棧頂壓入一個新數(shù)據(jù)項糖儡，需要一個數(shù)據(jù)項參數(shù)伐坏，無返回值 -
pop()拋出棧頂數(shù)據(jù)項，無參數(shù)握联，返回被拋出的數(shù)據(jù)項桦沉，棧本身發(fā)生變化 -
is_empty()測試棧是否空棧。不需要參數(shù)金闽，返回布爾值 -
size()返回棧內(nèi)數(shù)據(jù)項的數(shù)目纯露，不需要參數(shù)，返回值是整數(shù) -
peak()返回棧頂數(shù)據(jù)項代芜，但不刪除埠褪。不需要參數(shù)，棧不變
棧的python實現(xiàn)(一)
利用.append與.pop方法,我們可以把python內(nèi)置的列表當(dāng)作棧來使用(棧是一種特殊的列表),這是一種較為方便的實現(xiàn)方式
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實現(xiàn)(二)
或者自由定義類似列表的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())
? 定義一個結(jié)點
image
? 定義一個棧
image
top指向棧頂?shù)腘ode,next之想下一個Node,若沒有下一個Node,則指向一個None
棧的應(yīng)用
十進制轉(zhuǎn)二進制 是一個應(yīng)用堆棧的典型案例挤庇。十進制轉(zhuǎn)二進制 采用“除2取余钞速，逆序排列”的方法，如圖所示：
image
借助Stack類嫡秕，可以很方便地實現(xiàn)上述轉(zhuǎn)換算法：
def divideBy2(decNumber):
remstack = Stack()
while decNumber > 0:
rem = decNumber % 2
# 將余數(shù)逐個加入
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))
運行結(jié)果:
$ python dec2bin.py
101010
相關(guān)鏈接
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/
