<big>編譯環(huán)境：python v3.5.0, mac osx 10.11.4</big>
什么是堆棧
- 具有一定約束的線性表，只在一段（棧頂）進(jìn)行操作
-
后入先出（LIFO），如同疊碗：先疊上的，最后才會(huì)被取出來
- 插入數(shù)據(jù)（Push，入棧）站超，刪除數(shù)據(jù)（Pop，出棧）
堆棧的抽象數(shù)據(jù)類型描述
-
圖解堆棧
堆棧的順序存儲(chǔ)（數(shù)組）實(shí)現(xiàn)
基本結(jié)構(gòu)實(shí)現(xiàn)(下載地址：stack.py）
# -- coding: utf-8 --
class Stack():
def init(self, maxSize): # 初始化堆棧,設(shè)定最大值
self._stack = []
self._maxSize = maxSize
self._p = -1 # 指針指向棧頂
def push(self, value): # 插入數(shù)據(jù)
if self._p >= self._maxSize-1: # 通過判斷指針位置是否超過初始容量,確定堆棧是否滿了
print('stack is full')
else:
self._stack.append(value)
self._p += 1 # 指針向棧頂移動(dòng)
print('push %d in stack ' % value)
def pop(self): # 刪除數(shù)據(jù)
if self._p == -1: # 通過判斷指針位置來確定堆棧是否為空
print("it's an empty stack")
else:
iterms = self._stack[self._p] # 將最后一位元素的值取出
del self._stack[self._p] # s刪除元素
self._p -= 1 # 指針指向棧頂
print('pop %d out' % items)
return iterms # 返回最后一位元素的值-
堆棧的改良應(yīng)用（下載地址：stack_apply.py）
怎樣利用數(shù)組存儲(chǔ)兩個(gè)堆棧乖酬，要求最大化的利用數(shù)組空間死相，即只要任何一個(gè)堆棧不空，就能儲(chǔ)存元素
解決方案：<big>兩個(gè)堆棧從數(shù)組兩端往中間生長(zhǎng)</big>剑刑，即一個(gè)初始指針指向-1，另一個(gè)堆棧初始指針指向maxSize,當(dāng)兩指針相鄰時(shí)双肤，則兩堆棧都滿了施掏。
# -- coding: utf-8 --class newStack(): def __init__(self, maxSize): self._maxSize = maxSize self._p1 = -1 # 堆棧1 的指針 self._p2 = maxSize # 堆棧2 的指針 self._stack = [None] * maxSize # 儲(chǔ)存元素的數(shù)組 def push(self, value, tag): # 插入數(shù)據(jù), tag表示插入哪一個(gè)堆棧堆棧 if self._p2 - self._p1 == 1: # 通過判斷兩個(gè)指針位置是否相鄰,確定堆棧是否滿了 print('all stack are full') else: if tag == 1: self._p1 += 1 # 指針向中間移動(dòng) self._stack[self._p1] = value print('push %d in stack1 ' % value) elif tag == 2: self._p2 -= 1 # 指針向中間移動(dòng) self._stack[self._p2] = value print('push %d in stack2 ' % value) else: print("stack %d doesn't exist" % tag) def pop(self, tag): # 刪除數(shù)據(jù) if tag == 1: if self._p1 == -1: # 通過判斷指針位置來確定堆棧是否為空 print("it's an empty stack1") else: iterm1 = self._stack[self._p1] # 將最后一位元素的值取出 self._stack[self._p1] = None # 刪除元素 self._p1 -= 1 # 指針指向棧頂 print('pop %d out from stack 1' % iterm1) return iterm1 # 返回最后一位元素的值 elif tag == 2: if self._p2 == self._maxSize: # 通過判斷指針位置來確定堆棧是否為空 print("it's an empty stack2") else: iterm2 = self._stack[self._p2] # 將最后一位元素的值取出 self._stack[self._p2] = None # 刪除元素 self._p2 += 1 # 指針指向棧頂 print('pop %d out from stack 2' % iterm2) return iterm2 # 返回最后一位元素的值 else: print("stack %d doesn't exist" % tag)
堆棧的鏈?zhǔn)酱鎯?chǔ)（鏈表）實(shí)現(xiàn)
由于堆棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)際上是一個(gè)單向鏈表，所以棧頂指針應(yīng)該指向鏈表的表頭茅糜，若是指向表尾的話七芭，當(dāng)pop出一個(gè)元素后，我們無法得知這個(gè)元素的前一個(gè)元素是什么蔑赘。
-
基本結(jié)構(gòu)實(shí)現(xiàn)(下載地址：stack_chain.py）
class stackChain():
def init(self, value=None, next=None): # 創(chuàng)建一個(gè)空鏈表
self.value = value
self.next = nextdef isEmpty(stack_chain): # 判斷堆棧是否為空 return stack_chain.next is None def push(stack_chain, element): # 向堆棧stack_chain中插入元素element,并返回頭指針 newChain = stackChain(element) # 生成新的鏈表元素 newChain.next = stack_chain.next # 將原表頭棧頂元素接到新元素的下面 stack_chain.next = newChain # 將頭指針指向新元素 print('push '+str(element)+' in stack') return stack_chain def pop(stack_chain): # 堆棧stack_chain的頭元素,并返回頭指針 if isEmpty(stack_chain): print('it is an empty stack') else: p = stack_chain.next # 指針指向頭一個(gè)元素 print('pop '+str(p.value)+' out from stack') stack_chain.next = p.next # 將指針指向棧頂元素 element = p.value del p # 釋放空間 return element -
鏈?zhǔn)蕉褩５膽?yīng)用（下載地址：stack_expression.py）
表達(dá)式求值狸驳，應(yīng)用堆棧實(shí)現(xiàn)后綴表達(dá)式的求值過程，即將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式
解決方案：用列表存儲(chǔ)輸出狀態(tài)缩赛，用堆棧儲(chǔ)存表達(dá)符號(hào)耙箍。
# -- coding: utf-8 --import stack_chain def expression(expressionStrings): # 輸入表達(dá)式字符串,如:'1 + 1 * 2'以空格空開 allexpress = ['+', '-', '*', '/', '(', ')'] orderEX = { # 構(gòu)建運(yùn)算符優(yōu)先級(jí) '(': [1,0], # 第一位為優(yōu)先級(jí),第二位為標(biāo)簽 ')': [1], '+': [3], '-': [3], '*': [2], '/': [2], } output = [] # 建立存放輸出的列表 p_expression = stack_chain.stackChain() # 建立存放表達(dá)式的堆棧 normalExpression = expressionStrings.split() for element in normalExpression if not(element in allexpress): output.append(element) else: while not stack_chain.isEmpty(p_expression): # 如果堆棧不為空,則開始判斷 topElement = stack_chain.pop(p_expression) # 彈出棧頂元素并賦值給topElement if orderEX[topElement][0] <= orderEX[element][0]: # 棧頂優(yōu)先級(jí)低,則輸出棧頂元素 if topElement == '(' and orderEX['('][1] == 0: # 未彈出'(',將'('不斷輸入 stack_chain.push(p_expression, topElement) stack_chain.push(p_expression, element) break elif topElement == ')': # 遇到 ')'則改變'('的標(biāo)簽 orderEX['('][1] = 1 elif topElement == '(': orderEX['('][1] = 0 # 當(dāng)'('被pop出來后,初始化'('的標(biāo)簽 else: output.append(topElement) else: # 如果新掃到的運(yùn)算符優(yōu)先級(jí)低,則插入堆棧,并跳出循環(huán) stack_chain.push(p_expression, topElement) # 將棧頂元素重新插入 stack_chain.push(p_expression, element) # 將新運(yùn)算符也插入 break if stack_chain.isEmpty(p_expression): # 如果堆棧為空,則說明元素沒有push進(jìn)去 stack_chain.push(p_expression, element) while not(stack_chain.isEmpty(p_expression)): topElement = stack_chain.pop(p_expression) if not topElement in ['(', ')']: output.append(topElement) return output
堆棧的其他應(yīng)用：
- 函數(shù)的調(diào)用及遞歸實(shí)現(xiàn)
- 深度優(yōu)先搜索
- 回溯算法
