1. 棧
棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
棧(Stack)是限制插入和刪除操作只能在一個位置進行的表，該位置是表的末端，稱為棧的頂(top)。棧的基本操作有PUSH(入棧)和POP(出棧)。棧又被稱為LIFO(后入先出)表。
1.1 棧的實現(xiàn)
class Stack(object): def __init__(self): self.stack=[] def isEmpty(self): return self.stack==[] def push(self,item): self.stack.append(item) def pop(self): if self.isEmpty(): raise IndexError,'pop from empty stack' return self.stack.pop() def peek(self): return self.stack[-1] def size(self): return len(self.stack)
1.2 棧應(yīng)用
1.2.1 檢查程序中成對的符號
程序的語法錯誤經(jīng)常是由缺少一個符號造成的。可用棧來檢查符號是否成對。做一個空棧，如果字符是開放符號('({[')則將其push棧中。如果符號是個閉合符號(')]}'),則當(dāng)棧空時報錯，對應(yīng)'()}'的錯誤。否則，將棧pop，如果彈出的符號不是對應(yīng)的開放符號，則報錯，對應(yīng)'(}'的錯誤。文件末尾，如果棧為空，則報錯，對應(yīng)'({}'的錯誤。
def match(i,j): opens='([{' closes=')]}' return opens.index(i)==closes.index(j)def syntaxChecker(string): stack=Stack() balanced=True for i in string: if i in '([{': stack.push(i) elif i in ')]}': if stack.isEmpty(): balanced=False break else: j=stack.pop() if not match(j,i): balanced=False break if not stack.isEmpty(): balanced=False return balanced1.2.2 進制轉(zhuǎn)換
十進制轉(zhuǎn)換二進制：把十進制轉(zhuǎn)成二進制一直分解至商數(shù)為0。從最底左邊數(shù)字開始讀，之后讀右邊的數(shù)字，從下讀到上。
來自《Problem Solving with Algorithms and Data Structures》的圖片：
代碼：
def decimal_to_bin(dec): stack=Stack() cur=dec while cur>0: a=cur%2 cur=cur/2 stack.push(a) binstr='' while not stack.isEmpty(): binstr+=str(stack.pop()) return binstr
1.2.3 后綴記法
后綴記法(postfix)，使用一個棧，見到一個數(shù)時入棧，遇到一個運算符時就作用于從棧彈出的兩個元素，將結(jié)果彈入棧中。
(7+8)/(3+2)可以寫作7 8 + 3 2 + /
來自《Problem Solving with Algorithms and Data Structures》的圖片：
def infixtoPostfix(infix): a={} a['*']=3 a['/']=3 a['+']=2 a['-']=2 a['(']=1 stack=Stack() post='' for i in infix: if i not in a and i!=')': post+=i elif i=='(': stack.push(i) elif i==')': top=stack.pop() while top!='(': post+=top top=stack.pop() else: while not stack.isEmpty() and a[i]<=a[stack.peek()]: post+=stack.pop() stack.push(i) while not stack.isEmpty(): post+=stack.pop() return post def postfixExp(postfix): stack=Stack() postlist=postfix.split() for i in postlist: if i not in '+-*/': stack.push(i) else: a=stack.pop() b=stack.pop() result=math(i,b,a) stack.push(result) return stack.pop()def math(x,y,z): if x=='+': return float(y)+float(z) if x=='-': return float(y)-float(z) if x=='*': return float(y)*float(z) if x=='/': return float(y)/float(z)2 隊列
隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。
隊列(queue)也是表，使用隊列時插入和刪除在不同的端進行。隊列的基本操作是Enqueue(入隊)，在表的末端(rear)插入一個元素，還有出列(Dequeue)，刪除表開頭的元素。
class Queue(object): def __init__(self): self.queue=[] def isEmpty(self): return self.queue==[] def enqueue(self,x): self.queue.append(x) def dequeue(self): if self.queue: a=self.queue[0] self.queue.remove(a) return a else: raise IndexError,'queue is empty' def size(self): return len(self.queue)
總結(jié)
以上就是本文關(guān)于Python數(shù)據(jù)結(jié)構(gòu)之棧、隊列的實現(xiàn)代碼分享的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
新聞熱點
疑難解答
圖片精選
