快捷導(dǎo)航

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

更新時間：2017年12月04日 10:13:09 作者：再見紫羅蘭

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

1. 棧

棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進(jìn)棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

棧(Stack)是限制插入和刪除操作只能在一個位置進(jìn)行的表，該位置是表的末端，稱為棧的頂(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)?？諘r報錯，對應(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 balanced

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

十進(jìn)制轉(zhuǎn)換二進(jìn)制：把十進(jìn)制轉(zhuǎn)成二進(jì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）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊尾，進(jìn)行刪除操作的端稱為隊頭。

隊列(queue)也是表，使用隊列時插入和刪除在不同的端進(jìn)行。隊列的基本操作是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)專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！

您可能感興趣的文章: