本系列文章

(1) 數據結構淺析(1)-什麼是數據結構？

(2) 數據結構淺析(2)-集合

(3) 數據結構淺析(3)-線性結構：數組

(4) 數據結構淺析(4)-線性結構：線性表

(5) 數據結構淺析(5)-線性結構：串

本文目標

試著理解什麼是線性數據結構中的棧 stack。

把錢堆起來，stack 的表現形式

什麼是棧 stack

以下內容引自維基百科Stack (abstract data type)

在計算機科學中，棧是作為元素集合的抽象數據類型，有兩個主要操作：

push 推進，它向集合添加元素

pop 取出，刪除最近添加的尚未刪除的元素

從棧中放入取出元素的順序有它的專屬名稱Last In First Out(最後進，最先出；LIFO)。此外，peek操作可以在不修改棧的情況下訪問棧的頂部。這種數據類型，棧的名字，來自於類比一組物理產品堆疊在彼此之上，這使得它很容易把一件東西從堆棧的頂部拿走，想從一個棧中比較底部的地方拿出一個元素需要拿走它上面的多個其他元素。

作為線性數據結構，或者更抽象地說，順序收集，push 和pop 操作只發生在結構的一端，也就是棧的頂部。這使得將堆棧實現為單鏈表和指向頂部元素的指針成為可能。棧的實現是有有限容量的。如果堆棧已滿，且不包含足夠的空間接受要推送的實體，則認為堆棧處於溢出狀態。pop 操作則是從堆棧頂部刪除一個項。

我自己的看法

簡單來說，棧是其中元素有先進後出順序的線性結構。像疊積木，你只能從頂部放新的積木或則取走舊的積木；要想取走底下第n 塊積木，你就得先把其上面（n-1）塊積木先取走。這就是最後進最先出。

內存分配中的棧

棧（操作系統）：由操作系統自動分配釋放存放函數的參數值，局部變數的值等。其操作方式類似於數據結構中的棧。

棧使用的是一級緩存， 他們通常都是被調用時處於存儲空間中，調用完畢則立即釋放。

圖片來源：cleey 的堆和棧的區別 之 數據結構和內存，侵權刪

棧的特徵

從棧中放入取出元素的順序有它的專屬名稱Last In First Out(最後進，最先出；LIFO)。像疊積木，你只能從頂部放新的積木或則取走舊的積木；要想取走底下第n 塊積木，你就得先把其上面（n-1）塊積木先取走。這就是最後進最後出。

棧的兩個基本操作，push 和 pop

棧的基本操作

除了前面提到的pop 和 push，還有top，empty 和 full操作。

  • STACK_FULL（）：判斷棧是否已滿
  • STACK_EMPTY（）：判斷棧是否為空
  • PUSH（X）：向棧頂部添加一個值，預先判斷棧是否已滿
  • POP（）：從棧頂部取出一個值，預先判斷棧是否為空
  • top（）：查看棧頂部的元素

push 操作往棧頂部放入新元素，pop 操作從棧頂部取出元素

棧的實現

棧可以通過數組或鏈表來實現。在這兩種情況下，將數據結構標識為堆棧的方式不用實現，直接用介面：用戶只允許在數組或鏈表上pop 或push 元素，而很少有其他輔助操作。下面的代碼將使用偽代碼演示這兩種實現。

引自維基百科

數組 Array

一個數組可以用來實現一個（有界的）堆棧，如下所示。第一個元素為底部，導致array[0]被推到堆棧中的第一個元素。我們的程序必須一直跟蹤棧的大小(長度)，使用一個變數top 來記錄元素的數量，因此在數組中指向下一個元素的位置會插入下一個元素(假設是一個從零開始的index)。因此，堆棧本身可以有效地實現為一個三元素結構：

structure stack:
maxsize : integer
top : integer
items : 元素的數組

# 初始化步驟
procedure initialize(stk : stack, size : integer):
stk.items ← 新的size 元素的數組, 初始狀態下是空的
stk.maxsize ← 大小
stk.top ← 0

在檢查棧是否溢出之後，push 操作將添加一個元素並增加至頂部索引。

procedure push(stk : stack, x : item):
if stk.top = stk.maxsize: # 如果頂部顯示已經滿了/溢出狀態
report overflow error # 彙報溢出
else: # 如果未滿
stk.items[stk.top] ← 在頂部加入元素
stk.top ← stk.top 加1

類似地，在檢查了是否underflow 空之後，pop 會逐漸取出頂部元素，並返回之前最上面的元素。

procedure pop(stk : stack):
if stk.top = 0: # 如果頂部顯示是空的
report underflow error
else: # 如果不是空的
stk.top ← stk.top 減1
r ← stk.items[stk.top] # 之前最上面的元素
return r

使用動態數組，我們可以實現一個根據需要增長或縮小的棧。棧的大小是動態數組的大小，這是一個非常有效的堆棧的實現方式，因為在動態數組的末尾添加條目或刪除條目只需要平均O(1) 的時間。

鏈表 Linked List

structure frame:
data : item
next : frame 或則沒有

structure stack:
head : frame 或則誒呦
size : integer

procedure initialize(stk : stack):
stk.head ← nil
stk.size ← 0

push 和pop 操作發生在列表的頂部；在下面的代碼中，溢出是不可能的（除非內存耗盡）。

procedure push(stk : stack, x : item):
newhead ← new frame
newhead.data ← x
newhead.next ← stk.head
stk.head ← newhead
stk.size ← stk.size + 1

procedure pop(stk : stack):
if stk.head = nil:
report underflow error
r ← stk.head.data
stk.head ← stk.head.next
stk.size ← stk.size - 1
return r

Java

Java 中的stack 類，java.util.stack，是一個經典的堆棧數據結構。

在導入包後直接用代碼即可創建。

相信內容大家可以點擊這裡或則Stack Class in Java。

Stack stack = new Stack();

Python

相信的代碼解釋可以看這裡或則Python - Stack。

class Stack:
def __init__(self):
self.items = []

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

def push(self, item):
self.items.append(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)

在下一篇文章中，將著重講的是線性結構(4) -隊列 queue

如果你覺得我的文章有用，順手點個贊，關注下我的專欄或則留下你的評論吧！


推薦閱讀：
相关文章