Python實現(xiàn)棧和隊列的簡單操作方法示例

更新時間：2019年11月29日 11:14:18 作者：LuckyQueen0928

這篇文章主要介紹了Python實現(xiàn)棧和隊列的簡單操作方法,結(jié)合實例形式詳細分析了Python棧和隊列的原理與簡單實現(xiàn)技巧,需要的朋友可以參考下

本文實例講述了Python實現(xiàn)棧和隊列的簡單操作方法。分享給大家供大家參考，具體如下：

先簡單的了解一下數(shù)據(jù)結(jié)構(gòu)里面的棧和堆：

棧和隊列是兩種基本的數(shù)據(jù)結(jié)構(gòu)，同為容器類型。兩者根本的區(qū)別在于：

stack:后進先出

queue:先進先出

stack和queue是不能通過查詢具體某一個位置的元素而進行操作的。但是他們的排列是按順序的

對于stack我們可以使用python內(nèi)置的list實現(xiàn)，因為list是屬于線性數(shù)組，在末尾插入和刪除一個元素所使用的時間都是O(1),這非常符合stack的要求。當(dāng)然，我們也可以使用鏈表來實現(xiàn)。

stack的實現(xiàn)代碼（使用python內(nèi)置的list），實現(xiàn)起來是非常的簡單，就是list的一些常用操作

class Stack(object):
  def __init__(self):
    self.stack = []
  def push(self, value):  # 進棧
    self.stack.append(value)
  def pop(self): #出棧
    if self.stack:
      self.stack.pop()
    else:
      raise LookupError('stack is empty!')
  def is_empty(self): # 如果棧為空
    return bool(self.stack)
  def top(self): 
    #取出目前stack中最新的元素
    return self.stack[-1]

我們定義如下的鏈表來實現(xiàn)隊列數(shù)據(jù)結(jié)構(gòu)：

定義一個頭結(jié)點，左邊指向隊列的開頭，右邊指向隊列的末尾，這樣就可以保證我們插入一個元素和取出一個元素都是O(1)的操作，使用這種鏈表實現(xiàn)stack也是非常的方便。實現(xiàn)代碼如下：

class Head(object):
  def __init__(self):
    self.left = None
    self.right = None
class Node(object):
  def __init__(self, value):
    self.value = value
    self.next = None
class Queue(object):
  def __init__(self):
    #初始化節(jié)點
    self.head = Head()
  def enqueue(self, value):
    #插入一個元素
    newnode = Node(value)
    p = self.head
    if p.right:
      #如果head節(jié)點的右邊不為None
      #說明隊列中已經(jīng)有元素了
      #就執(zhí)行下列的操作
      temp = p.right
      p.right = newnode
      temp.next = newnode
    else:
      #這說明隊列為空，插入第一個元素
      p.right = newnode
      p.left = newnode
  def dequeue(self):
    #取出一個元素
    p = self.head
    if p.left and (p.left == p.right):
      #說明隊列中已經(jīng)有元素
      #但是這是最后一個元素
      temp = p.left
      p.left = p.right = None
      return temp.value
    elif p.left and (p.left != p.right):
      #說明隊列中有元素，而且不止一個
      temp = p.left
      p.left = temp.next
      return temp.value
    else:
      #說明隊列為空
      #拋出查詢錯誤
      raise LookupError('queue is empty!')
  def is_empty(self):
    if self.head.left:
      return False
    else:
      return True
  def top(self):
    #查詢目前隊列中最早入隊的元素
    if self.head.left:
      return self.head.left.value
    else:
      raise LookupError('queue is empty!')

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進階經(jīng)典教程》

希望本文所述對大家Python程序設(shè)計有所幫助。

您可能感興趣的文章: