一、棧(Stack)
棧(stack)，也可以叫做堆棧，是一種容器類型的數(shù)據(jù)結(jié)構(gòu)，可以存入數(shù)據(jù)元素、訪問元素以及刪除元素。
特點：只允許在一端進(jìn)行操作，采用了后進(jìn)先出（Last in Fist out）的原理。
下面采用順序表的形式來實現(xiàn)棧：
| 操作 | 解釋 |
|---|---|
| Stack() | 創(chuàng)建一個新的棧 |
| push() | 在棧中添加一個元素 |
| pop() | 彈出棧頂?shù)脑?/td> |
| peek() | 返回棧頂?shù)脑?/td> |
| is_empty() | 判斷這個棧是不是空 |
| size() | 棧的大小 |
class Stack(object):
"""棧"""
def __init__(self):
self.__list = []
def push(self, item):
"""添加一個新元素到棧頂，就是將這個item放到append到最后面"""
self.__list.append(item)
def pop(self):
"""彈出棧頂?shù)脑?，采用list中的pop方法"""
return self.__list.pop()
def peek(self):
"""返回棧頂?shù)脑?，就是彈出來最后的一個元素"""
if self.__list:
return self.__list[-1]
else:
return None
def is_empty(self):
"""判斷棧是不是為空的"""
return self.__list == []
def size(self):
"""返回棧的元素個數(shù)"""
return len(self.__list)
if __name__ == '__main__':
s = Stack()
print(s.is_empty()) # True
print(s.size()) # 0
s.push(1)
s.push(2)
s.push(3)
print(s.is_empty()) # False
print(s.peek()) # 3
print(s.size()) # 3
s.pop()
s.pop()
print(s.is_empty()) # False
print(s.size()) # 1
二、隊列(Queue)
隊列是一種只允許在一端進(jìn)行插入操作，另外一端進(jìn)行刪除操作的線性表
特點是：先進(jìn)先出（First in First out）。舉個例子，就是排隊買票去動物園，先排隊買到票的小伙伴就先進(jìn)去。其效果如下圖所示：
| 操作 | 解釋 |
|---|---|
| Queue() | 創(chuàng)建一個新的隊列 |
| enqueue() | 在隊列中添加一個元素 |
| dequeue() | 從隊列的頭部刪除一個元素 |
| is_empty() | 判斷這個隊列是不是空 |
| size() | 隊列的大小 |
class Queue(object):
"""隊列"""
def __init__(self):
self.__list = []
def enqueue(self, item):
"""往隊列中添加一個元素"""
self.__list.append(item)
def dequeue(self):
"""將隊列頭部的一個元素刪除"""
self.__list.pop(0)
def is_empty(self):
"""判斷一個隊列是不是空的"""
return self.__list==[]
def size(self):
"""返回隊列的大小"""
return len(self.__list)
if __name__ == '__main__':
q = Queue()
print(q.is_empty()) # True
print(q.size()) # 0
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
print(q.is_empty()) # False
print(q.size()) # 4
q.dequeue()
q.dequeue()
print(q.is_empty()) # False
print(q.size()) # 2
三、雙端隊列(Deque)
雙端隊列具有隊列和棧的數(shù)據(jù)結(jié)構(gòu)。
| 操作 | 解釋 |
|---|---|
| Deque() | 創(chuàng)建一個空的雙端隊列 |
| add_front(item) | 從隊頭加入一個item元素 |
| add_rear(item) | 從隊尾加入一個item元素 |
| remove_front() | 從隊頭刪除一個item元素 |
| remove_rear() | 從隊尾刪除一個item元素 |
| is_empty() | 判斷雙端隊列是否為空 |
| size() | 返回隊列的大小 |
class Deque(object):
"雙端隊列"
def __init__(self):
self.items = []
def is_empty(self):
"""判斷雙端隊列是不是空"""
return self.items ==[]
def add_front(self, item):
"""從隊頭添加元素"""
self.items.insert(0, item)
def add_rear(self, item):
"""從隊尾添加元素"""
self.items.append(item)
def remove_front(self):
"""從隊頭刪除元素"""
return self.items.pop(0)
def remove_rear(self):
"""從隊尾刪除元素"""
return self.items.pop()
def size(self):
"""返回隊列大小"""
return len(self.items)
if __name__ == '__main__':
deque = Deque()
deque.add_front(1)
deque.add_front(2)
deque.add_rear(3)
deque.add_rear(4)
print(deque.size()) # 4
print(deque.remove_front()) # 2
print(deque.remove_front()) # 1
print(deque.remove_rear()) # 4
print(deque.remove_rear()) # 3
持續(xù)更新中...
數(shù)據(jù)結(jié)構(gòu)與算法系列博客：
一、數(shù)據(jù)結(jié)構(gòu)與算法概述
二、數(shù)組及LeetCode典型題目分析
三、鏈表（Linked list）以及LeetCode題
四、棧與隊列（Stack and Queue
五、樹（Trees）
六、遞歸與回溯算法
七、動態(tài)規(guī)劃
八、排序與搜索
九、哈希表
參考資料：
1、Data Structures and Algorithms in Python [Goodrich, Tamassia & Goldwasser 2013-03-18]
2、https://www.cs.auckland.ac.nz/compsci105s1c/resources/ProblemSolvingwithAlgorithmsandDataStructures.pdf
3、http://interactivepython.org/runestone/static/pythonds/index.html
