一、棧 （後進先出）
棧（stack），有些地方稱為堆棧，是一種容器，可存入資料元素、通路元素、删除元素，它的特點在于隻能允許在容器的一端（稱為棧頂端名額，英語：top）進行加入資料（英語：push）和輸出資料（英語：pop）的運算。沒有了位置概念，保證任何時候可以通路、删除的元素都是此前最後存入的那個元素，确定了一種預設的通路順序。
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __str__(self):
return str(self.data)
class Stack:
def __init__(self):
self._head = None
# 壓棧
def push(self, item):
node = Node(item)
node.next = self._head
self._head = node
return node.data
# 彈棧
def pop(self):
if self._head == None:
return None
else:
data = self._head.data
self._head = self._head.next
return data
# peek 取出棧頂元素
def peek(self):
if self._head != None:
return self._head.data
else:
raise ValueError('stack is empty')
def print_all(self):
cur = self._head
while cur != None:
print(cur)
cur = cur.next
if __name__ == '__main__':
s = Stack()
s.push(6)
s.push(1)
s.push(8)
s.push(10)
s.print_all()
print('--------pop-------------')
s.pop()
s.print_all() View Code
二、隊列
隊列（queue）是隻允許在一端進行插入操作，而在另一端進行删除操作的線性表。
隊列是一種先進先出的（First In First Out）的線性表，簡稱FIFO。允許插入的一端為隊尾，允許删除的一端為隊頭。隊列不允許在中間部位進行操作！
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __str__(self):
return str(self.data)
class Queue:
def __init__(self, maxsize=-1):
self.maxsize = maxsize
self._head = None
self._tail = None
# 入隊
def enter(self, data): # put
size = self.qsize()
if self.maxsize != -1 and self.maxsize > size or self.maxsize == -1:
node = Node(data)
if self._head == None and self._tail == None:
self._head = node
self._tail = node
else:
self._tail.next = node
self._tail = node
else:
raise Exception('queue full ')
# 出隊
def exit(self): # get()
if self._head == None and self._tail == None:
# return None
raise ValueError('queue is empty')
data = self._head.data
if self._head == self._tail:
self._head = None
self._tail = None
else:
self._head = self._head.next
return data
def print_all(self):
cur = self._head
while cur != None:
print(cur)
cur = cur.next
def qsize(self):
count = 0
cur = self._head
while cur != None:
count += 1
cur = cur.next
return count
def full(self):
pass
def empty(self):
pass
if __name__ == '__main__':
q = Queue(4)
q.enter(6)
q.enter(4)
q.enter(2)
q.print_all()
print('---------取出-------------')
q.exit()
q.print_all()
print('-----------大小-------')
q.enter(7)
q.enter(1)
# q.enter(9)
print(q.qsize()) View Code
雙端隊列：是一種具有隊列和棧的性質的資料結構。
雙端隊列中的元素可以從兩端彈出，其限定插入和删除操作在表的兩端進行。雙端隊列可以在隊列任意一端入隊和出隊。
from collections import deque
class Deque:
def __init__(self):
self.items = []
def isEmpty(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)
def print_all(self):
for item in self.items:
print(item)
if __name__ == '__main__':
dq = Deque()
dq.add_front(8)
dq.add_front(9)
dq.add_front(0)
dq.print_all()
dq.add_rear(6)
dq.print_all()
print('-----------remove---------')
dq.remove_front()
dq.print_all() View Code
三、排序算法