快捷導(dǎo)航

Python實(shí)現(xiàn)棧和隊(duì)列的簡(jiǎn)單操作方法示例

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

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

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

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

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

stack:后進(jìn)先出

queue:先進(jìn)先出

stack和queue是不能通過(guò)查詢(xún)具體某一個(gè)位置的元素而進(jìn)行操作的。但是他們的排列是按順序的

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

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

class Stack(object):
  def __init__(self):
    self.stack = []
  def push(self, value):  # 進(jìn)棧
    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]

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

定義一個(gè)頭結(jié)點(diǎn)，左邊指向隊(duì)列的開(kāi)頭，右邊指向隊(duì)列的末尾，這樣就可以保證我們插入一個(gè)元素和取出一個(gè)元素都是O(1)的操作，使用這種鏈表實(shí)現(xiàn)stack也是非常的方便。實(shí)現(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é)點(diǎn)
    self.head = Head()
  def enqueue(self, value):
    #插入一個(gè)元素
    newnode = Node(value)
    p = self.head
    if p.right:
      #如果head節(jié)點(diǎn)的右邊不為None
      #說(shuō)明隊(duì)列中已經(jīng)有元素了
      #就執(zhí)行下列的操作
      temp = p.right
      p.right = newnode
      temp.next = newnode
    else:
      #這說(shuō)明隊(duì)列為空，插入第一個(gè)元素
      p.right = newnode
      p.left = newnode
  def dequeue(self):
    #取出一個(gè)元素
    p = self.head
    if p.left and (p.left == p.right):
      #說(shuō)明隊(duì)列中已經(jīng)有元素
      #但是這是最后一個(gè)元素
      temp = p.left
      p.left = p.right = None
      return temp.value
    elif p.left and (p.left != p.right):
      #說(shuō)明隊(duì)列中有元素，而且不止一個(gè)
      temp = p.left
      p.left = temp.next
      return temp.value
    else:
      #說(shuō)明隊(duì)列為空
      #拋出查詢(xún)錯(cuò)誤
      raise LookupError('queue is empty!')
  def is_empty(self):
    if self.head.left:
      return False
    else:
      return True
  def top(self):
    #查詢(xún)目前隊(duì)列中最早入隊(duì)的元素
    if self.head.left:
      return self.head.left.value
    else:
      raise LookupError('queue is empty!')

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

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

您可能感興趣的文章: