數據結構筆記（二）：棧、隊列

（一）棧

1、棧是一種後進先出，先進後出的數據結構。

2、棧是一種操作受限的線性表，只允許在一端插入和刪除數據。

3、棧主要包含2個操作，入棧和出棧

4、棧可以用數組實現，也可以用鏈表實現。用數組實現的棧叫做順序棧，用鏈表實現的棧叫做鏈式棧。

例如：

  現在有一個空瓶子。

1、我們依次放入多個蘋果

2、從瓶子中取蘋果的時候，最後放進去的蘋果會最先取出來，最先放進去的蘋果最後取出來。

3、只能從瓶口放入或取出蘋果。（只允許在一端插入和刪除數據）

用數組實現一個棧：（這裡用列表代替了）

 1 class ArrayStack():
 2 
 3     ITEMS = []  # 這裡用列表代替了
 4     COUNT = 0  # 棧中的元素個數
 5     N = 10  # 棧的大小
 6 
 7     def  push(self ,item):
 8         """
 9         入棧
10         :param item:
11         :return:
12         """
13         if len(self.ITEMS) >= self.N: return False   # 棧已經滿了
14         self.ITEMS.append(item)
15         self.COUNT += 1
16         return True
17 
18     def  pop(self):
19         """
20         出棧
21         :return:
22         """
23         if len(self.ITEMS) == 0: return False   # 棧為空
24         item = self.ITEMS.pop()
25         self.COUNT -= 1
26         return item

（二）隊列

1、隊列是一種先進先出的數據結構。例如：超市排隊付款，排在前面的先付完款，然後先出去。後來的只能排隊，不允許插隊。

2、棧只支持2個基本操作入棧（push）和出棧（pop）。隊列也只支持2個基本操作，入隊 enqueue()，放一個數據到隊列尾部；出隊 dequeue()，從隊列頭部取一個元素。

3、隊列和棧一樣。也是一種操作受限的線性表結構。

4、跟棧一樣，也可以用數組或鏈表實現。用數組實現的隊列叫順序隊列，用鏈表實現的隊列叫鏈式隊列。

用數組實現一個隊列（這裡用列表代替了）：

 1 class ArrayQueue():
 2 
 3     ITEMS = []  # 數組
 4     HEAD = 0    # 隊頭索引
 5     TAIL = 0    # 隊尾索引
 6 
 7     def __init__(self,n):
 8         self.n = n  # 數組大小
 9 
10     def enqueue(self,item):
11         """
12         入隊
13         :param item:
14         :return:
15         """
16         if self.TAIL == self.n: return False  # 隊尾索引等於數組大小，表示隊列滿了
17         self.ITEMS.append(item)
18         self.TAIL += 1
19         return True
20 
21     def dequeue(self):
22         """
23         出隊
24         :return:
25         """
26         if self.HEAD == self.TAIL: return False  # 隊頭索引==隊尾索引，表示隊列為空
27         item = self.ITEMS[self.HEAD]
28         self.ITEMS[self.HEAD] = "X" # 標識已經刪除
29         self.HEAD += 1
30         return item

（三）練習題

1、leetcode 20 

1 class Solution:
2     def isValid(self, s: str) -> bool:
3         the_dict = {"(":")","{":"}","[":"]","k":"k"}
4         stack = ["k"]
5         for i in s:
6             if i in the_dict: stack.append(i)  # 將左括弧壓入棧
7             elif the_dict[stack.pop()] != i: return False   # 如果字元串中的右括弧不等於預期的右括弧，返回false
8         return  len(stack) == 1