Chương 16. Ngăn xếp, hàng đợi và thư viện collections
Ngăn xếp (stack)
Phần tiêu đề “Ngăn xếp (stack)”Ngăn xếp giống một chồng đĩa: đĩa đặt vào sau cùng được lấy ra đầu tiên. Nguyên tắc này gọi là vào sau, ra trước (LIFO: last in, first out). Ngăn xếp có ba thao tác chính:
| Thao tác | Ý nghĩa | Với list Python |
|---|---|---|
| push | đặt phần tử lên đỉnh | stack.append(x) |
| pop | lấy phần tử ở đỉnh ra | stack.pop() |
| top | xem phần tử ở đỉnh | stack[-1] |
stack = []for page in ["trang1", "trang2", "trang3"]: stack.append(page)print(stack[-1], len(stack))print(stack.pop(), stack.pop())print(stack, len(stack) == 0)trang3 3trang3 trang2['trang1'] Falseappend và pop() (ở cuối) của list đều rất nhanh, nên list là ngăn xếp tốt. Gọi pop() khi ngăn
xếp rỗng báo IndexError, phải kiểm tra trước (if stack:).
Ứng dụng: nút “Quay lại” của trình duyệt, nút “Hoàn tác” (Ctrl + Z), kiểm tra dấu ngoặc, máy tính lưu các lời gọi hàm (ngăn xếp lời gọi ở chương 13).
Kiểm tra dãy ngoặc
Phần tiêu đề “Kiểm tra dãy ngoặc”Dãy ngoặc {[()]} đúng vì mỗi ngoặc đóng khớp với ngoặc mở gần nhất chưa được đóng. Ngoặc mở gần
nhất chính là đỉnh ngăn xếp:
def is_balanced(text): matching = {")": "(", "]": "[", "}": "{"} stack = [] for ch in text: if ch in "([{": stack.append(ch) # ngoặc mở: chờ ngoặc đóng elif not stack or stack.pop() != matching[ch]: return False # không có ngoặc mở, hoặc khác loại return len(stack) == 0 # còn ngoặc mở chưa đóng thì sai
for text in ["{[()]}", "([)]", "((", ")("]: print(text, is_balanced(text)){[()]} True([)] False(( False)( FalseHàng đợi (queue)
Phần tiêu đề “Hàng đợi (queue)”Hàng đợi giống hàng người xếp mua vé: ai đến trước được phục vụ trước. Nguyên tắc vào trước, ra trước (FIFO: first in, first out): thêm ở cuối, lấy ra ở đầu.
Dùng list làm hàng đợi thì pop(0) (lấy phần tử đầu) chậm: mọi phần tử phía sau phải dịch lên một
chỗ. Python có deque (đọc là “đéc”, double-ended queue: hàng đợi hai đầu) trong module collections,
thêm và lấy ở cả hai đầu đều nhanh:
from collections import deque
queue = deque()queue.append("An") # vào cuối hàngqueue.append("Binh")queue.append("Chi")print(queue[0], len(queue)) # người đầu hàngprint(queue.popleft()) # phục vụ người đầu hàngprint(list(queue))An 3An['Binh', 'Chi']| Thao tác | deque | Tốc độ |
|---|---|---|
| thêm vào cuối, đầu | append(x), appendleft(x) | nhanh |
| lấy ra ở cuối, đầu | pop(), popleft() | nhanh |
| xem đầu, cuối | q[0], q[-1] | nhanh |
| xoay vòng | rotate(k): đưa k phần tử cuối lên đầu (k âm thì ngược lại) | nhanh |
| truy cập giữa | q[i] | chậm với i ở giữa hàng đợi dài |
So sánh tốc độ: lấy lần lượt 105 phần tử ở đầu bằng list.pop(0) cần khoảng 5 × 109 lần dịch chuyển
phần tử, còn deque.popleft() chỉ cần 105 thao tác.
Xoay vòng với rotate
Phần tiêu đề “Xoay vòng với rotate”Ví dụ: n bạn đứng thành vòng tròn, đếm từ bạn đầu tiên, cứ đến bạn thứ k thì bạn đó ra khỏi vòng; tiếp
tục đếm từ bạn kế tiếp. rotate(-(k - 1)) đưa k − 1 bạn đầu xuống cuối hàng, khi đó bạn thứ k đứng
đầu hàng:
from collections import deque
circle = deque(range(1, 8)) # 7 bạn, đếm đến 3 thì raorder = []while circle: circle.rotate(-(3 - 1)) order.append(circle.popleft())print(*order)3 6 2 7 5 1 4Counter và defaultdict
Phần tiêu đề “Counter và defaultdict”Module collections còn hai công cụ giúp viết gọn các mẫu đếm và gom nhóm của chương 12.
Counter là từ điển đếm: tạo từ một dãy là có ngay số lần xuất hiện của từng phần tử; phần tử chưa
có thì đếm là 0 (không báo KeyError).
from collections import Counter
words = "meo cho ga meo ca cho meo ga".split()count = Counter(words)print(count["meo"], count["voi"])print(count.most_common(2))3 0[('meo', 3), ('cho', 2)]most_common(k) trả về k phần tử xuất hiện nhiều nhất kèm số lần. Lưu ý: khi nhiều phần tử cùng số
lần, most_common giữ thứ tự xuất hiện đầu tiên, không sắp theo thứ tự từ điển; đề bài yêu cầu
thứ tự từ điển thì phải tự sắp xếp với khóa (-số_lần, tên).
defaultdict là từ điển tự tạo giá trị mặc định khi gặp khóa mới, rất tiện để gom nhóm:
from collections import defaultdict
groups = defaultdict(list) # khóa mới tự có giá trị []for word in ["an", "binh", "anh", "bao", "chi"]: groups[word[0]].append(word)print(dict(groups)){'a': ['an', 'anh'], 'b': ['binh', 'bao'], 'c': ['chi']}So với chương 12, không cần viết if first not in groups: groups[first] = [] nữa.
Hàng đợi ưu tiên: heapq
Phần tiêu đề “Hàng đợi ưu tiên: heapq”Nhiều bài toán cần liên tục lấy phần tử nhỏ nhất trong một tập đang thay đổi (thêm phần tử mới, lấy phần tử nhỏ nhất ra). Sắp xếp lại sau mỗi lần thêm thì quá chậm. Hàng đợi ưu tiên (priority queue) làm việc này nhanh: mỗi lần thêm hoặc lấy chỉ mất khoảng log2n bước.
Python cài hàng đợi ưu tiên bằng module heapq, làm việc trên một list bình thường:
import heapq
heap = []for x in [5, 1, 8, 3, 9, 2]: heapq.heappush(heap, x) # thêmprint(heap[0]) # phần tử nhỏ nhất luôn ở heap[0]print(heapq.heappop(heap), heapq.heappop(heap)) # lấy ra nhỏ nhất, rồi nhỏ nhìnumbers = [7, 4, 6]heapq.heapify(numbers) # biến list có sẵn thành heapprint(heapq.heappop(numbers))print(heapq.nlargest(2, [5, 1, 8, 3]), heapq.nsmallest(2, [5, 1, 8, 3]))11 24[8, 5] [1, 3]heapqluôn lấy ra phần tử nhỏ nhất. Muốn lấy lớn nhất, đẩy vào số đối-xrồi đổi dấu khi lấy ra.- Phần tử có thể là tuple, so sánh theo phần tử đầu trước:
(độ_ưu_tiên, tên). heapkhông được sắp xếp hoàn toàn; chỉ chắc chắnheap[0]là nhỏ nhất.
Ví dụ: có các sợi dây, mỗi lần nối hai sợi tốn chi phí bằng tổng độ dài. Muốn tổng chi phí nhỏ nhất, mỗi lần nối hai sợi ngắn nhất (sợi được nối sớm bị cộng vào chi phí nhiều lần, nên để sợi ngắn nối trước):
import heapq
ropes = [2, 3, 4, 5]heapq.heapify(ropes)cost = 0while len(ropes) > 1: joined = heapq.heappop(ropes) + heapq.heappop(ropes) cost += joined heapq.heappush(ropes, joined)print(cost)28Chọn cấu trúc nào?
Phần tiêu đề “Chọn cấu trúc nào?”| Bài toán cần | Dùng | Thao tác chính |
|---|---|---|
| Lấy phần tử thêm vào gần nhất | ngăn xếp: list | append, pop() |
| Lấy phần tử thêm vào sớm nhất | hàng đợi: deque | append, popleft() |
| Lấy phần tử nhỏ nhất (lớn nhất) | hàng đợi ưu tiên: heapq | heappush, heappop |
| Đếm số lần xuất hiện | Counter | Counter(a), most_common |
| Gom nhóm theo khóa | defaultdict(list) | d[k].append(x) |
Lỗi thường gặp
Phần tiêu đề “Lỗi thường gặp”| Lỗi | Nguyên nhân |
|---|---|
IndexError: pop from empty list | lấy ra khi ngăn xếp, hàng đợi rỗng; kiểm tra if stack: trước |
| Chương trình chậm với hàng đợi | dùng list.pop(0) hoặc list.insert(0, x); đổi sang deque |
Nghĩ heap đã sắp xếp | chỉ heap[0] chắc chắn nhỏ nhất; in cả heap không theo thứ tự |
| Lấy lớn nhất bằng heapq | heapq chỉ cho nhỏ nhất; đẩy -x vào |
most_common sai thứ tự khi bằng nhau | tự sắp xếp với khóa (-số_lần, tên) |
Tóm tắt
Phần tiêu đề “Tóm tắt”- Ngăn xếp (vào sau ra trước): list với
append,pop(),stack[-1]. - Hàng đợi (vào trước ra trước):
dequevớiappend,popleft(),q[0];rotateđể xoay vòng. Counter(a)đếm,most_common(k);defaultdict(list)gom nhóm.heapq:heappush,heappop,heapify,heap[0]nhỏ nhất; lớn nhất thì dùng-x.- Chọn cấu trúc theo câu hỏi: lấy phần tử nào ra tiếp theo?
Bài tập thực hành
Phần tiêu đề “Bài tập thực hành”Chương này có 6 bài tập thực hành:
- Bài 16.1. Dãy ngoặc đúng
- Bài 16.2. Hàng đợi
- Bài 16.3. Trình duyệt web
- Bài 16.4. Vòng tròn loại trừ
- Bài 16.5. Nối dây
- Bài 16.6. Các từ phổ biến
Mua bộ tài liệu đầy đủ
Phần tiêu đề “Mua bộ tài liệu đầy đủ”Đề bài chi tiết (có ví dụ), lời giải từng bài (ý tưởng, các bước, lỗi hay gặp) kèm code Python, bộ test chấm tự động bằng Themis và bài giảng PowerPoint của chương này có trong bộ giáo trình Python đầy đủ.
Thầy cô và các em muốn mua bộ tài liệu đầy đủ vui lòng liên hệ tác giả Th.S Trần Huy Phúc:
- Zalo: 0972465159
- Facebook: facebook.com/tran.huyphuc.3