Mục lục bài họcĐang ở d05-b4
Applications of Stacks and Queues: Call Stacks, Undo, Buffers and Breadth-First Traversal
Choose by what must come out first. A stack returns the item added most recently (last in, first out); a queue returns the item added earliest (first in, first out). Every application question reduces to one question: which item must be dealt with first, the newest or the oldest? Answer that and the structure follows. Both are usually built on an array or a linked list, and both offer only a handful of operations — push and pop, or enqueue and dequeue, plus a test for empty — which is exactly what makes them safe: the caller cannot reach into the middle.
Stack applications. The call stack: when a sub-program calls another, the return address and local variables are pushed; when it finishes they are popped, so the most recently called sub-program always finishes first — this is what makes recursion possible, and what overflows when recursion is too deep. Undo: each action is pushed; undo pops the most recent; redo needs a second stack. Expression evaluation: postfix expressions are evaluated by pushing operands and popping two for each operator; compilers convert infix to postfix using a stack of operators. Browser back button, bracket matching and depth-first traversal of a tree or maze are the same pattern: the most recent choice is the first to revisit.
Queue applications. The print queue: documents are printed in the order submitted. Buffers: a keyboard buffer stores keystrokes until the program reads them; a router queues packets until the outgoing link is free; a video player buffers frames so that playback stays smooth when the network hiccups — in every case the producer and consumer run at different speeds and the queue absorbs the difference while preserving order. Process scheduling keeps ready processes in a queue. Breadth-first traversal of a tree uses a queue: enqueue the root; repeatedly dequeue a node, visit it, and enqueue its children; the result is level by level, left to right. Replace the queue with a stack in the same algorithm and the traversal becomes depth-first — the clearest demonstration that the structure, not the loop, decides the order.
Implementation details that get asked. A queue in a plain array creeps to the right as items are removed from the front, wasting space or forcing every element to shift; a circular queue lets the front and rear pointers wrap around, so both operations are constant time in a fixed array. A stack in an array needs only a top index. Linked-list versions grow without limit but cost a pointer per item. Both structures must handle empty (pop or dequeue on nothing) and, in array form, full — and an exam answer that omits these checks loses marks.
Chọn theo thứ gì phải ra trước. Ngăn xếp trả lại phần tử được thêm gần nhất (vào sau ra trước); hàng đợi trả lại phần tử được thêm sớm nhất (vào trước ra trước). Mọi câu hỏi ứng dụng quy về một câu: phần tử nào phải được xử lý trước, mới nhất hay cũ nhất? Trả lời được thì cấu trúc theo sau. Cả hai thường xây trên mảng hoặc danh sách liên kết, và cả hai chỉ cung cấp vài phép — push và pop, hoặc enqueue và dequeue, cộng kiểm rỗng — chính điều đó làm chúng an toàn: bên gọi không thò tay vào giữa được.
Ứng dụng của ngăn xếp. Ngăn xếp gọi: khi một chương trình con gọi chương trình con khác, địa chỉ trở về và biến cục bộ được đẩy vào; khi xong chúng được lấy ra, nên chương trình con được gọi gần nhất luôn xong trước — đây là điều làm đệ quy khả thi, và là thứ tràn khi đệ quy quá sâu. Hoàn tác: mỗi thao tác được đẩy vào; hoàn tác lấy ra thao tác gần nhất; làm lại cần ngăn xếp thứ hai. Tính biểu thức: biểu thức hậu tố được tính bằng cách đẩy toán hạng và lấy ra hai cho mỗi toán tử; trình biên dịch chuyển trung tố sang hậu tố bằng một ngăn xếp toán tử. Nút quay lại của trình duyệt, kiểm ngoặc và duyệt theo chiều sâu của cây hay mê cung là cùng một mẫu: lựa chọn gần nhất là thứ được quay lại trước.
Ứng dụng của hàng đợi. Hàng đợi in: tài liệu được in theo thứ tự gửi. Bộ đệm: bộ đệm bàn phím giữ phím gõ tới khi chương trình đọc; router xếp hàng gói tin tới khi đường ra rảnh; trình phát video đệm khung hình để phát mượt khi mạng giật — trong mọi trường hợp bên sản xuất và bên tiêu thụ chạy ở tốc độ khác nhau và hàng đợi hấp thụ chênh lệch trong khi giữ thứ tự. Lập lịch tiến trình giữ các tiến trình sẵn sàng trong một hàng đợi. Duyệt theo chiều rộng của cây dùng hàng đợi: đưa gốc vào; lặp lại lấy một nút ra, thăm nó, đưa các con vào; kết quả là từng tầng, trái sang phải. Thay hàng đợi bằng ngăn xếp trong cùng thuật toán và phép duyệt thành theo chiều sâu — minh chứng rõ nhất rằng cấu trúc, không phải vòng lặp, quyết định thứ tự.
Chi tiết cài đặt hay được hỏi. Hàng đợi trong mảng thường trườn dần sang phải khi phần tử bị lấy khỏi đầu, lãng phí chỗ hoặc buộc dịch mọi phần tử; hàng đợi vòng cho con trỏ đầu và cuối quay vòng, nên cả hai phép đều hằng thời gian trong mảng cố định. Ngăn xếp trong mảng chỉ cần một chỉ số đỉnh. Bản danh sách liên kết lớn không giới hạn nhưng tốn một con trỏ mỗi phần tử. Cả hai cấu trúc phải xử lý rỗng (pop hoặc dequeue khi không có gì) và, ở dạng mảng, đầy — bài thi bỏ các kiểm tra này sẽ mất điểm.
Một trình soạn thảo cần hoàn tác (Ctrl+Z) và làm lại (Ctrl+Y). Hãy chọn cấu trúc, mô tả thao tác cho mỗi sự kiện: người dùng gõ, người dùng hoàn tác, người dùng làm lại, người dùng gõ mới sau khi hoàn tác. Nêu cách xử lý khi bộ nhớ giới hạn 100 thao tác.
Cấu trúc. Hai ngăn xếp: UNDO và REDO. Hoàn tác phải huỷ thao tác gần nhất trước, nên UNDO là ngăn xếp; làm lại phải khôi phục thao tác vừa bị hoàn tác gần nhất trước, nên REDO cũng là ngăn xếp.
Người dùng gõ. Đẩy mô tả thao tác (vị trí, ký tự chèn) vào UNDO. Đồng thời xoá sạch REDO: sau khi làm một việc mới, chuỗi làm lại cũ không còn hợp lệ — bỏ bước này là lỗi kinh điển khiến làm lại chèn văn bản vào sai chỗ.
Hoàn tác. Nếu UNDO rỗng thì không làm gì (kiểm rỗng bắt buộc). Ngược lại pop một thao tác, đảo ngược nó trên văn bản (xoá ký tự đã chèn), rồi push nó vào REDO.
Làm lại. Nếu REDO rỗng thì không làm gì. Ngược lại pop từ REDO, áp dụng lại lên văn bản, push trở lại UNDO. Hai ngăn xếp chuyển thao tác qua lại, và văn bản luôn nhất quán với đỉnh của UNDO.
Gõ mới sau khi hoàn tác. Chính là trường hợp đầu: push vào UNDO và xoá REDO. Nếu không xoá, người dùng có thể làm lại một thao tác dựa trên trạng thái văn bản đã không còn tồn tại.
Giới hạn 100 thao tác. Ngăn xếp thuần chỉ bỏ được ở đỉnh, nhưng khi đầy ta cần bỏ thao tác cũ nhất ở đáy. Giải pháp là cài UNDO trên một mảng vòng có kích thước 100: khi push lúc đầy, đáy bị ghi đè và con trỏ đáy tiến lên. Tức là cấu trúc thực tế là ngăn xếp có giới hạn với hành vi bỏ đáy — một lai giữa ngăn xếp và hàng đợi vòng, và câu trả lời tốt gọi tên được điều đó thay vì nói ngăn xếp rồi dừng.
Chọn cấu trúc và giải thích: (a) router nhận gói tin nhanh hơn tốc độ đường ra; (b) trình duyệt web quản lý nút quay lại; (c) một robot tìm đường ngắn nhất ra khỏi mê cung lưới, mỗi bước đi một ô. Với (c), điều gì xảy ra nếu dùng cấu trúc kia?
(a) Router — hàng đợi. Gói tới trước phải đi trước để giữ thứ tự và để không gói nào bị bỏ đói; hàng đợi hấp thụ chênh lệch tốc độ giữa đường vào và đường ra. Khi hàng đợi đầy, router bỏ gói mới tới, và TCP ở hai đầu phát hiện mất gói rồi giảm tốc — hàng đợi đầy chính là tín hiệu tắc nghẽn. Cài bằng hàng đợi vòng trong bộ nhớ cố định vì router không được cấp phát động giữa lúc bận.
(b) Nút quay lại — ngăn xếp. Trang được rời gần nhất là trang cần quay lại trước. Mỗi lần đi tới trang mới, push trang hiện tại; quay lại là pop. Giống hoàn tác, cần ngăn xếp thứ hai cho nút tiến, và đi tới trang mới sau khi quay lại phải xoá ngăn xếp tiến.
(c) Mê cung, đường ngắn nhất — hàng đợi. Đưa ô xuất phát vào hàng đợi; lặp lại lấy một ô ra, đánh dấu đã thăm, đưa các ô kề chưa thăm vào. Vì hàng đợi xử lý theo thứ tự đưa vào, mọi ô cách xuất phát 1 bước được xử lý trước mọi ô cách 2 bước, và cứ thế — nên ô đích được gặp lần đầu chính là qua đường ngắn nhất. Đây là duyệt theo chiều rộng, và tính chất ngắn nhất đến từ việc mở rộng theo từng vòng đồng tâm.
Nếu dùng ngăn xếp cho (c). Thuật toán vẫn tìm được lối ra nếu có, nhưng đi sâu theo một nhánh tới cùng trước khi thử nhánh khác, nên đường tìm được có thể dài hơn nhiều so với ngắn nhất; nó dùng ít bộ nhớ hơn trên mê cung rộng vì chỉ giữ một nhánh, và là lựa chọn đúng khi chỉ cần một lối ra bất kỳ. Cùng vòng lặp, đổi cấu trúc là đổi lời hứa của thuật toán — từ ngắn nhất sang bất kỳ.
Bẫy 2 — không kiểm rỗng và đầy. Pop trên ngăn xếp rỗng và enqueue vào mảng đầy là lỗi bài thi hay mất điểm nhất.
Bẫy 3 — nói duyệt theo chiều rộng vì thuật toán khác. Cùng vòng lặp; chỉ hàng đợi hay ngăn xếp quyết định theo tầng hay theo chiều sâu.
Đọc xong rồi — làm thử ngay
Bài tập của chương Abstract Data Structures (HL) gồm 14 câu trắc nghiệm và 5 đề tự luận. Đáp án hiện ngay khi chọn, miễn phí.