快捷導(dǎo)航

Python數(shù)據(jù)結(jié)構(gòu)與算法中的棧詳解(1)

更新時(shí)間：2022年03月09日 16:51:42 作者：姜學(xué)遷

這篇文章主要為大家詳細(xì)介紹了Python中的棧，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助

什么是棧

棧有時(shí)也被稱作“下推棧”。它是有序集合，添加操作和移除操作總發(fā)生在同一端，即棧的 “頂端”，棧的另一端則被稱為 “底端”。所以最新添加的元素將被最先移除，而且棧中的元素離底端越近，代表其在棧中的時(shí)間越長(zhǎng)。

這種排序原則被稱作LIFO（last-in first-out），即后進(jìn)先出。它提供了一種基于在集合中的時(shí)間來(lái)排序的方式。 最近添加的元素靠近頂端，舊元素則靠近底端。

棧的例子在日常生活中比比皆是。幾乎所有咖啡館都有一個(gè)由托盤或盤子構(gòu)成的棧，你可以從頂部取走一個(gè)，下一個(gè)顧客則會(huì)取走下面的托盤或盤子。

考慮到棧的反轉(zhuǎn)特性，我們可以想到在使用計(jì)算機(jī)時(shí)的一些例子。例如，每一個(gè)瀏覽器都有返回按鈕。當(dāng)我們從一個(gè)網(wǎng)頁(yè)跳轉(zhuǎn)到另一個(gè)網(wǎng)頁(yè)時(shí)，這些網(wǎng)頁(yè)——實(shí)際上是URL，都被存放在一個(gè)棧中。當(dāng)前正在瀏覽的網(wǎng)頁(yè)位于棧的頂端，最早瀏覽的網(wǎng)頁(yè)則位于底端。如果點(diǎn)擊返回按鈕，便開(kāi)始反向?yàn)g覽這些網(wǎng)頁(yè)。

構(gòu)建一個(gè)棧

如前所述，棧是元素的有序集合，添加操作與移除操作都發(fā)生在其頂端。棧的操作順序是LIFO，它支持以下操作：

將一個(gè)元素添加到棧的頂端
將棧頂端的元素移除
返回棧頂端的元素
返回棧中元素的數(shù)目

明確了棧的基本特性之后，我們開(kāi)始用代碼構(gòu)建它。在面向?qū)ο蟮木幊陶Z(yǔ)言中(以Python為例)，每當(dāng)需要在Python中實(shí)現(xiàn)像棧這樣的抽象數(shù)據(jù)類型時(shí) ，就可以通過(guò)創(chuàng)建一個(gè)類的途徑實(shí)現(xiàn)它，且數(shù)據(jù)類型的特性、操作方法等也可以通過(guò)在類中定義方法實(shí)現(xiàn)。

我們來(lái)明確一下這個(gè)類的具體方法：

創(chuàng)建一個(gè)空棧。它不需要參數(shù)，且會(huì)返回一個(gè)空棧。 Stack()
將一個(gè)元素添加到棧的頂端。它需要一個(gè)參數(shù)item ，且無(wú)返回值。 push(item)
將棧頂端的元素移除。它不需要參數(shù)，但會(huì)返回頂端的元素，并且修改棧的內(nèi)容。 pop()
返回棧頂端的元素，但是并不移除該元素。它不需要參數(shù)，也不會(huì)修改棧的內(nèi)容。 peek()
返回棧中元素的數(shù)目。它不需要參數(shù)，且會(huì)返回一個(gè)整數(shù)。 size()
檢查棧是否為空。它不需要參數(shù)，且會(huì)返回一個(gè)布爾值。 isEmpty()
打印這個(gè)棧/列表，它不需要參數(shù)，會(huì)輸出棧的內(nèi)容。 look()

?因?yàn)?strong>棧是元素的集合，所以完全可以利用Python提供的強(qiáng)大、簡(jiǎn)單的原生集合來(lái)實(shí)現(xiàn)。這里，我們將使用列表。 列表的最左端將用來(lái)表示棧底，最右邊將用來(lái)表示棧頂：

class Stack:
  # 定義一個(gè)列表/構(gòu)造一個(gè)棧
  def __init__(self):
  	self.items = []
  	print("你創(chuàng)造了一個(gè)棧！")
  def isEmpty(self):
    return self.items == []
  def look(self):
    print(self.items)
  def push(self, item):
    self.items.append(item)
    print("你給棧頂加了個(gè)%s" % item)
  def pop(self):
    return self.items.pop()
  def peek(self):
    return self.items[len(self.items) - 1]
  def size(self):
    return len(self.items)

以下展示了棧的操作及其返回結(jié)果：

在這里插入圖片描述

值得注意的是，也可以選擇將列表的頭部(左邊)作為棧的頂端。不過(guò)在這種情況下，便無(wú)法直接使用列表的pop方法和append方法，而必須要用列表的pop方法和insert方法顯式地訪問(wèn)下標(biāo)為0的元素，即列表中的第1個(gè)元素。以下代碼展現(xiàn)了這種方式：

class Stack:
  def __init__(self):
  	self.items = []
  def isEmpty(self):
    return self.items == []
  def look(self):
    print(self.items)
  def push(self, item):
    self.items.insert(0, item)
  def pop(self):
    return self.items.pop(0)
  def peek(self):
    return self.items[0]
  def size(self):
    return len(self.items)

盡管上述兩種實(shí)現(xiàn)都可行，但是二者在性能方面肯定有差異。append 方法和 pop 方法的時(shí)間復(fù)雜度都是 o ( 1 ) o(1) o(1)，這意味著不論棧中有多少個(gè)元素，第一種實(shí)現(xiàn)中的 push 操作和 pop 操作都會(huì)在恒定的時(shí)間內(nèi)完成。第二種實(shí)現(xiàn)的性能則受制于棧中的元素個(gè)數(shù)，這是因?yàn)?insert(0) 和 pop(0) 的時(shí)間復(fù)雜度都是 o ( n ) o(n) o(n)，元素越多就越慢。

顯而易見(jiàn)，盡管兩種實(shí)現(xiàn)在邏輯上是相等的，但是它們?cè)谶M(jìn)行基準(zhǔn)測(cè)試時(shí)耗費(fèi)的時(shí)間會(huì)有很大的差異。