隊(duì)、棧和鏈表一樣，在數(shù)據(jù)結(jié)構(gòu)中非常基礎(chǔ)一種數(shù)據(jù)結(jié)構(gòu)，同樣他們也有各種各樣、五花八門的變形和實(shí)現(xiàn)方式。但不管他們形式上怎么變，隊(duì)和棧都有其不變的最基本的特征，我們今天就從最基本，最簡單的實(shí)現(xiàn)來看看隊(duì)列和堆棧。

不管什么形式的隊(duì)列，它總有的一個(gè)共同的特點(diǎn)就是“先進(jìn)先出”。怎么理解呢?就像是超市排隊(duì)結(jié)賬，先排隊(duì)的人排在隊(duì)的前面，先結(jié)賬出隊(duì)。這是隊(duì)列的特征。

而堆棧則和隊(duì)列相反，它是“先進(jìn)后出”，怎么理解呢?基本所有的編輯器都有一個(gè)撤銷功能，就是按Ctrl+Z。當(dāng)你寫了一段文字，第一次按Ctrl+Z，消失的是你最后寫的文字，第二次按Ctrl+Z，同樣消失的是當(dāng)前編輯器內(nèi)最后寫的文字。這就是一個(gè)堆棧結(jié)構(gòu)的應(yīng)用例子。

好，介紹完概念我們來看一下代碼如何實(shí)現(xiàn)這兩種數(shù)據(jù)結(jié)構(gòu)，這篇文章我們采用最簡單方式——通過Python原生的數(shù)據(jù)類型列表來實(shí)現(xiàn)。上篇文章，我們介紹了鏈表，通過鏈表我們同樣可以實(shí)現(xiàn)堆棧和隊(duì)列，感興趣的朋友不妨嘗試一下。

隊(duì)列

首先，我們來定義一個(gè)隊(duì)列類：

class Queue():
 def __init__(self):
 self.__list = list()

接下來，我們給隊(duì)列類添加一些方法：

•判斷隊(duì)列是否為空

 def isEmpty(self):
 return self.__list == []

•入隊(duì) 

def push(self, data):
 self.__list.append(data)

•出隊(duì)

 def pop(self):
 if self.isEmpty():
  return False
 return self.__list.pop(0)

•定義len()函數(shù)和print()操作類方法 

 def __len__(self):
 return len(self.__list)
 def __str__(self):
 if self.isEmpty():
  return ''
 return ' '.join([str(x) for x in self.__list])

OK，到這里，一個(gè)最簡單的隊(duì)列就實(shí)現(xiàn)啦，自己實(shí)例化一個(gè)隊(duì)列測試一下吧

下面我們來看堆棧

堆棧

堆棧的實(shí)現(xiàn)和隊(duì)列類似，同樣有入棧和出棧操作，我們直接上代碼：

class Stack():
 def __init__(self):
 self.__list = list()

 def isEmpty(self):
 return self.__list == []

 def push(self, data):
 self.__list.append(data)
 
 def pop(self):
 if self.isEmpty():
  return False
 return self.__list.pop()

 def __len__(self):
 return len(self.__list)

 def __str__(self):
 if self.isEmpty():
  return ''
 return ' '.join([str(x) for x in self.__list])

可以看到，堆棧和隊(duì)列的類實(shí)現(xiàn)基本相同，差別僅在出隊(duì)和出棧的時(shí)候，隊(duì)列是彈出第一個(gè)元素，而堆棧則是彈出最后一個(gè)元素。這也是隊(duì)列和堆棧最本質(zhì)的區(qū)別。

總結(jié)

以上所述是小編給大家介紹的Python 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)-堆棧和隊(duì)列的操作方法,希望對(duì)大家有所幫助，如果大家有任何疑問請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
如果你覺得本文對(duì)你有幫助，歡迎轉(zhuǎn)載，煩請(qǐng)注明出處，謝謝！

最新評(píng)論