重學數據結構之棧

2020 年 5 月 6 日
筆記
數據結構

一、前言簡介

　　數據結構課程是一門重要的電腦基礎課程，而我本人在上學期間真是沒學好這門課，聽課總是聽得雲里霧裡的，寫起程式碼來也不知道如何編寫和運用這些數據結構，以致於後來考試也只能是低分飄過，所以現在就需要花時間重新學習一下數據結構了！

　　為了能夠更好地學習和掌握數據結構，除了學習和理解相應的概念，我還會找幾個題目並用所學的數據結構來解決問題，相應的問題和程式碼也會一併記錄在部落格中。

二、棧的概念

1.基本概念

　　棧（stack）又被稱為堆棧，是一種保存數據元素的容器。棧作為一種數據結構，是一種只能在一端進行插入和刪除操作的特殊線性表，允許進行插入和刪除操作的一端叫做棧頂（top），另一端則叫做棧底（bottom），插入元素一般稱為進棧（PUSH），刪除元素一般稱為出棧（POP）。

　　棧按照後進先出的原則（LIFO， Last In First Out）存儲數據，後存入的元素會先被取出來使用。存入棧中的元素相互之間並沒有任何具體的關係，只有存入的時間先後順序，而沒有元素的前後順序或者元素的位置等概念。

2.抽象數據類型

　　棧的基本操作一個封閉的數據集合，在一個棧里需要實現將元素壓入棧中即進棧、從棧中彈出元素即出棧、返回最後一個插入棧中的元素、獲取棧中元素的數量等方法，下面就是一個棧的抽象數據類型描述：

ADT Stack：

　　Stack(self) # 創建一個空棧

　　empty(self) # 判斷棧是否為空

　　push(self, x) # 將元素壓入棧中

　　pop(self) # 從棧中彈出元素

　　peek(self) # 返回最後一個插入的元素

　　size(sellf) # 獲取棧中元素的數量

3.用 Python 實現

　　在 Python 中沒有棧這種數據結構，但我們可以藉助 list 來實現，用 list 來存放數據，並實現一個棧所需要的各種方法，具體程式碼如下：

 1 # 自定義棧
 2 class MyStack:
 3     def __init__(self):
 4         self.data = []
 5 
 6     def push(self, x):
 7         """
 8         將數據壓入棧中
 9         :param x: 需要插入的元素
10         :return: 
11         """
12         self.data.append(x)
13 
14     def pop(self):
15         """
16         從棧中彈出元素
17         :return: 彈出的元素
18         """
19         if not self.empty():
20             ret, self.data = self.data[-1], self.data[:-1]
21             return ret
22         return None
23 
24     def empty(self):
25         """
26         判斷棧是否為空
27         :return: 棧空--True，非空--False
28         """
29         return len(self.data) == 0
30 
31     def size(self):
32         """
33         獲取棧中元素的數量
34         :return: 
35         """
36         return len(self.data)
37 
38     def peek(self):
39         """
40         返回最後一個插入的元素
41         :return: 最後一個插入的元素
42         """
43         if not self.empty():
44             return self.data[-1]
45         return None

三、棧的應用

1.進位轉換

1）問題描述

　　輸入一個任意的十進位正整數，將其轉化成相應的二進位、八進位和十六進位的數。

2）解決思路

　　這裡首先需要介紹一個公式：

N = (N div d) * d + N mod d

　　其中 div 表示整除，mod 表示求余。例如當輸入的正整數 N 為777，輸出的進位是八進位時，計算過程如下：

N 　　 N div 8 　　 N mod 8

777　　　97　　　　 1

97　　　 12　　　　 1

12　　　　1　　　　　4

1　　　　 0　　　　　1　　

　　在進行進位轉換的時候，我們就可以將每次求余的結果保存在棧中，最後將棧中的數依次取出，就是轉換後的結果了，例如十進位的777轉換成八進位就是1411。

3）程式碼實現

　　如何用程式碼來解決這個問題？一個思路就是將每次求余的結果保存在棧中，而整除的結果則用來進行下一步的計算，直到這個整除的結果為0，表明計算結束，再出棧中依次取出元素，得到的結果就是轉換成相應進位後的數。具體程式碼如下：

 1 def solution(n: int, scale: int):
 2     """
 3     進位轉換
 4     :param n: 正整數
 5     :param scale: 進位
 6     :return:
 7     """
 8     stack = MyStack()
 9     # 循環計算
10     while n // scale >= 0 and n > 0:
11         stack.push(n % scale)
12         n = n // scale
13     # 輸出
14     while not stack.empty():
15         print(stack.pop(), end="")

2.括弧匹配

1）問題描述

　　輸入一個字元串，裡面可能有「()」、「[]」和「{}」三種括弧，編寫程式檢查該字元串中的括弧是否成對出現。

2）解決思路

　　遍歷這個字元串，用棧來存放每次遍歷的元素，如果遍歷的元素和棧頂的括弧是配對的，則進行出棧操作將棧頂元素彈出，反之若不配對，則進行入棧操作將該元素插入到棧中。等遍歷結束後，若棧為空，則表明該字元串中的括弧都是成對出現的，若棧不為空，則表明有括弧不匹配。

3）程式碼實現

 1 def solution(input_string: str):
 2     """
 3     判斷輸入的字元中的括弧是否成對出現
 4     :param input_string: 輸入字元串
 5     :return:
 6     """
 7     def match(c1: str, c2: str):
 8         """
 9         判斷兩個括弧是否匹配
10         :param c1: 
11         :param c2: 
12         :return: 
13         """
14         if c1 == "(" and c2 == ")":
15             return True
16         elif c1 == "[" and c2 == "]":
17             return True
18         elif c1 == "{" and c2 == "}":
19             return True
20         else:
21             return False
22 
23     stack = MyStack()
24     for i in range(len(input_string)):
25         if stack.empty():
26             # 棧空直接入棧
27             stack.push(input_string[i])
28         else:
29             # 棧非空時進行比較
30             if match(stack.peek(), input_string[i]):
31                 stack.pop()
32             else:
33                 stack.push(input_string[i])
34     print("匹配！") if stack.empty() else print("不匹配！")

Tags: 數據結構