Bài 31. Ngăn xếp và hàng đợi
Cùng là một dãy dữ liệu đang chờ được xử lí, nhưng thứ tự lấy ra có thể theo hai luật hoàn toàn trái ngược nhau: lấy thứ vừa bỏ vào gần nhất, hoặc lấy thứ đã chờ lâu nhất. Bài này giới thiệu hai cấu trúc dữ liệu dựng trên hai luật đó - ngăn xếp và hàng đợi - cùng cách mô phỏng cả hai chỉ bằng danh sách có sẵn của Python, và một lỗi rất hay gặp khi lấy phần tử ra.
- Cánh DiềuTin học 11 (Khoa học máy tính) - Chủ đề F(CS) · Bài 15. Cấu trúc dữ liệu danh sách liên kết và ứng dụngtr. 146
Bắt đầu bằng một hình dung
Sau bữa tối, bạn rửa xong một chồng đĩa và úp chúng lên giá. Chiếc rửa xong sớm nhất nằm dưới cùng, chiếc rửa sau được đặt chồng lên trên. Sáng hôm sau cần lấy một cái đĩa, bạn làm gì? Không ai đi rút chiếc nằm dưới đáy cả - bạn nhấc chiếc trên cùng, tức là chiếc vừa được úp lên sau cùng tối qua. Muốn lấy chiếc ở đáy, bạn buộc phải dỡ hết những chiếc nằm đè lên nó. Chồng đĩa vì thế có một luật ngầm: thứ vào sau lại là thứ ra trước.
Chiều hôm đó, bạn ra siêu thị và đứng vào hàng chờ ở quầy thanh toán. Tại đây luật hoàn toàn ngược lại. Người tới quầy sớm nhất được tính tiền trước rồi rời đi; người vừa tới phải đứng vào cuối hàng và chờ tới lượt. Không ai chen ngang, cũng không ai được phục vụ sớm chỉ vì mới đến.
Hai cách sắp xếp rất đời thường đó - chồng đĩa trên giá và hàng người trước quầy - chính là hai cách máy tính tổ chức những dữ liệu đang xếp hàng chờ xử lí.
Nội dung bài học
- 1) Ngăn xếp - vào sau ra trước
- 2) Hàng đợi - vào trước ra trước
- 3)
pop()vàpop(0)- khác nhau đúng một con số - 4) Hai cấu trúc này nằm ở đâu trong đời sống
Tóm tắt lý thuyết cần nhớ
- Ngăn xếp (
stack) chạy theo luật vào sau ra trước (LIFO): mọi thao tác thêm (push) và lấy (pop) đều diễn ra ở đỉnh (top), không được rút phần tử ở giữa. - Hàng đợi (
queue) chạy theo luật vào trước ra trước (FIFO): thêm phần tử vào cuối hàng, lấy phần tử ra từ đầu hàng. - Danh sách Python mô phỏng được cả hai: ngăn xếp là
append()+pop(), hàng đợi làappend()+pop(0); nhớ kĩpop()lấy phần tử cuối, cònpop(0)lấy phần tử đầu. - Luôn kiểm tra rỗng bằng
len(ds) > 0trước khi lấy phần tử ra, nếu không Python báo lỗiIndexErrorvà dừng chương trình. - Ngăn xếp đứng sau nút Hoàn tác và nút Back của trình duyệt; hàng đợi đứng sau hàng chờ in ấn, việc xếp hàng mua vé và tin nhắn chờ gửi.
Thuật ngữ tiếng Anh trong bài
| Tiếng Anh | Đọc là | Nghĩa |
|---|---|---|
| stack | xờ-TẮC | ngăn xếp Cách chứa dữ liệu kiểu 'vào sau ra trước' - giống chồng đĩa: đĩa đặt lên sau cùng lại được lấy ra trước tiên. |
| queue | kiu | hàng đợi Dãy dữ liệu 'vào trước ra trước' - y như xếp hàng mua vé, ai đến trước được trước. |
| LIFO (Last In, First Out) | lai-phâu | vào sau ra trước Luật hoạt động của ngăn xếp: thứ được bỏ vào sau cùng lại là thứ được lấy ra đầu tiên. |
| FIFO (First In, First Out) | phai-phâu | vào trước ra trước Luật hoạt động của hàng đợi: thứ vào trước thì ra trước. |
| push | pút | đẩy vào đỉnh Thao tác thêm một phần tử lên đỉnh ngăn xếp. |
| pop | pốp | nhấc ra khỏi đỉnh Thao tác lấy phần tử ở đỉnh ngăn xếp ra và trả về giá trị của nó. |
Câu hỏi trắc nghiệm có đáp án
Mấy câu mẫu để bạn tự kiểm tra ngay. Trong ứng dụng, bài này có đủ 25 câu, chấm điểm tự động và giải thích từng câu sai.
stack) hoạt động theo nguyên tắc nào?- Vào trước ra trước - phần tử vào sớm nhất được lấy ra đầu tiên
- Vào sau ra trước - phần tử vào sau cùng được lấy ra đầu tiên
- Lấy ngẫu nhiên một phần tử bất kì trong ngăn xếp
- Luôn lấy phần tử có giá trị nhỏ nhất ra trước
LIFO), đúng như chồng đĩa: chiếc úp lên sau cùng nằm trên đỉnh và được nhấc ra đầu tiên. Phương án đầu là luật của hàng đợi (FIFO), không phải ngăn xếp. Hai phương án còn lại đều sai vì ngăn xếp chỉ cho phép thao tác ở đỉnh, không rút phần tử tuỳ ý ở giữa và cũng không quan tâm giá trị lớn hay nhỏ.queue), phần tử mới được thêm vào đâu và phần tử được lấy ra nằm ở đâu?- Thêm vào cuối hàng, lấy ra từ đầu hàng
- Thêm vào đầu hàng, lấy ra từ đầu hàng
- Thêm vào cuối hàng, lấy ra từ cuối hàng
- Thêm vào giữa hàng, lấy ra từ cuối hàng
s làm ngăn xếp. Máy in ra kết quả gì?s = []
s.append(1)
s.append(2)
s.append(3)
print(s.pop(), s.pop())- 1 2
- 3 2
- 1 3
- 3 1
append, danh sách là [1, 2, 3] với đỉnh là 3. Lệnh pop() thứ nhất nhấc đỉnh ra, trả về 3 và danh sách còn [1, 2]; lệnh pop() thứ hai nhấc đỉnh mới, trả về 2. Vậy máy in 3 2. Các phương án bắt đầu bằng 1 đều nhầm ngăn xếp thành hàng đợi (lấy từ đầu), còn 3 1 sai vì sau khi lấy 3 thì đỉnh là 2 chứ không phải 1.- a)Trong ngăn xếp, cả thao tác thêm vào lẫn thao tác lấy ra đều diễn ra ở đỉnh.Đúng
- b)Trong hàng đợi, phần tử vào sau cùng sẽ được lấy ra đầu tiên.Sai
- c)Gọi
pop()trên một danh sách đang rỗng sẽ khiến chương trình báo lỗiIndexError.Đúng - d)Có thể lấy một phần tử nằm giữa ngăn xếp mà không cần đụng tới các phần tử nằm trên nó.Sai
- (a) Đúng: ngăn xếp chỉ mở một đầu là đỉnh,
pushvàpopđều làm việc tại đó. - (b) Sai: “vào sau ra trước” là luật của ngăn xếp; hàng đợi theo luật vào trước ra trước, phần tử vào sau cùng phải đứng cuối và chờ lâu nhất.
- (c) Đúng: danh sách rỗng không còn gì để lấy nên Python báo
IndexError: pop from empty list, vì vậy phải kiểm tra rỗng trước. - (d) Sai: muốn lấy phần tử ở giữa, bạn buộc phải
pophết những phần tử nằm trên nó, đúng như phải dỡ đĩa từ trên xuống.
Thử ngay: minh hoạ từng bước
Bấm từng bước để tự xem cơ chế hoạt động, hoặc bấm “Tự chạy” cho nó tiến mỗi giây một lần. Đổi được dữ liệu đầu vào - không cần đăng nhập.
Học trọn bài này trong ứng dụng
Bài giảng đầy đủ, 25 câu luyện tập chấm tự động, thi thử đúng cấu trúc đề tốt nghiệp (24 trắc nghiệm + 4 Đúng/Sai), bài thực hành máy tự chấm và gia sư AI giải thích chỗ sai.
Phần học miễn phí, không cần tạo tài khoản.
Bài liên quan - Lập trình, Thuật toán & CTDL (KHMT)
Cùng mạch kiến thức với bài này, học nối tiếp cho chắc phần lí thuyết.