Bỏ qua để đến nội dung

Chương 16. Ngăn xếp, hàng đợi và thư viện collections

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ĩaVới list Python
pushđặt phần tử lên đỉnhstack.append(x)
poplấy phần tử ở đỉnh rastack.pop()
topxem phần tử ở đỉnhstack[-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 3
trang3 trang2
['trang1'] False

append 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).

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
)( False

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àng
queue.append("Binh")
queue.append("Chi")
print(queue[0], len(queue)) # người đầu hàng
print(queue.popleft()) # phục vụ người đầu hàng
print(list(queue))
An 3
An
['Binh', 'Chi']
Thao tácdequeTốc độ
thêm vào cuối, đầuappend(x), appendleft(x)nhanh
lấy ra ở cuối, đầupop(), popleft()nhanh
xem đầu, cuốiq[0], q[-1]nhanh
xoay vòngrotate(k): đưa k phần tử cuối lên đầu (k âm thì ngược lại)nhanh
truy cập giữaq[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.

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ì ra
order = []
while circle:
circle.rotate(-(3 - 1))
order.append(circle.popleft())
print(*order)
3 6 2 7 5 1 4

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.

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êm
print(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 heap
print(heapq.heappop(numbers))
print(heapq.nlargest(2, [5, 1, 8, 3]), heapq.nsmallest(2, [5, 1, 8, 3]))
1
1 2
4
[8, 5] [1, 3]
  • heapq luôn lấy ra phần tử nhỏ nhất. Muốn lấy lớn nhất, đẩy vào số đối -x rồ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).
  • heap không được sắp xếp hoàn toàn; chỉ chắc chắn heap[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 = 0
while len(ropes) > 1:
joined = heapq.heappop(ropes) + heapq.heappop(ropes)
cost += joined
heapq.heappush(ropes, joined)
print(cost)
28
Bài toán cầnDùngThao tác chính
Lấy phần tử thêm vào gần nhấtngăn xếp: listappend, pop()
Lấy phần tử thêm vào sớm nhấthàng đợi: dequeappend, popleft()
Lấy phần tử nhỏ nhất (lớn nhất)hàng đợi ưu tiên: heapqheappush, heappop
Đếm số lần xuất hiệnCounterCounter(a), most_common
Gom nhóm theo khóadefaultdict(list)d[k].append(x)
LỗiNguyên nhân
IndexError: pop from empty listlấ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 đợidùng list.pop(0) hoặc list.insert(0, x); đổi sang deque
Nghĩ heap đã sắp xếpchỉ 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 heapqheapq chỉ cho nhỏ nhất; đẩy -x vào
most_common sai thứ tự khi bằng nhautự sắp xếp với khóa (-số_lần, tên)
  • 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): deque với append, 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?

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

Đề 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:

Th.S Trần Huy Phúc

Th.S Trần Huy Phúc

Principal Software Engineer @Adnovum & Bumbii Academy