快捷導(dǎo)航

Python數(shù)據(jù)結(jié)構(gòu)之棧、隊(duì)列的實(shí)現(xiàn)代碼分享

更新時(shí)間：2017年12月04日 10:13:09 作者：再見(jiàn)紫羅蘭

這篇文章主要介紹了Python數(shù)據(jù)結(jié)構(gòu)之棧、隊(duì)列的實(shí)現(xiàn)代碼分享，具有一定參考價(jià)值，需要的朋友可以了解下。

1. 棧

棧（stack）又名堆棧，它是一種運(yùn)算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。這一端被稱為棧頂，相對(duì)地，把另一端稱為棧底。向一個(gè)棧插入新元素又稱作進(jìn)棧、入?；驂簵＃前研略胤诺綏ｍ斣氐纳厦?，使之成為新的棧頂元素；從一個(gè)棧刪除元素又稱作出?；蛲藯＃前褩ｍ斣貏h除掉，使其相鄰的元素成為新的棧頂元素。

棧(Stack)是限制插入和刪除操作只能在一個(gè)位置進(jìn)行的表，該位置是表的末端，稱為棧的頂(top)。棧的基本操作有PUSH(入棧)和POP(出棧)。棧又被稱為L(zhǎng)IFO(后入先出)表。

1.1 棧的實(shí)現(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 檢查程序中成對(duì)的符號(hào)

程序的語(yǔ)法錯(cuò)誤經(jīng)常是由缺少一個(gè)符號(hào)造成的。可用棧來(lái)檢查符號(hào)是否成對(duì)。做一個(gè)空棧，如果字符是開(kāi)放符號(hào)('({[')則將其push棧中。如果符號(hào)是個(gè)閉合符號(hào)(')]}'),則當(dāng)棧空時(shí)報(bào)錯(cuò)，對(duì)應(yīng)'()}'的錯(cuò)誤。否則，將棧pop，如果彈出的符號(hào)不是對(duì)應(yīng)的開(kāi)放符號(hào)，則報(bào)錯(cuò)，對(duì)應(yīng)'(}'的錯(cuò)誤。文件末尾，如果棧為空，則報(bào)錯(cuò)，對(duì)應(yīng)'({}'的錯(cuò)誤。

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 balanced

1.2.2 進(jìn)制轉(zhuǎn)換

十進(jìn)制轉(zhuǎn)換二進(jìn)制：把十進(jìn)制轉(zhuǎn)成二進(jìn)制一直分解至商數(shù)為0。從最底左邊數(shù)字開(kāi)始讀，之后讀右邊的數(shù)字，從下讀到上。

來(lái)自《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)，使用一個(gè)棧，見(jiàn)到一個(gè)數(shù)時(shí)入棧，遇到一個(gè)運(yùn)算符時(shí)就作用于從棧彈出的兩個(gè)元素，將結(jié)果彈入棧中。

(7+8)/(3+2)可以寫(xiě)作7 8 + 3 2 + /

來(lái)自《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 隊(duì)列

隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。

隊(duì)列(queue)也是表，使用隊(duì)列時(shí)插入和刪除在不同的端進(jìn)行。隊(duì)列的基本操作是Enqueue(入隊(duì))，在表的末端(rear)插入一個(gè)元素，還有出列(Dequeue)，刪除表開(kāi)頭的元素。

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)之棧、隊(duì)列的實(shí)現(xiàn)代碼分享的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對(duì)本站的支持！

您可能感興趣的文章: