Mục lục bài họcĐang ở d06-b1
Abstract data types: stacks, queues and linked lists
What an abstract data type is
An ADT is defined by the operations it supports, not by how it is stored. A stack is a stack because of push and pop, whether it is built from an array or a linked list. Separating the two is the idea being examined.
Stack — last in, first out
Operations: push adds to the top, pop removes from the top, peek looks without removing. One pointer, the top, is enough. Stack overflow happens on push when full; stack underflow on pop when empty — both must be checked. Stacks are used for the return addresses of subroutine calls, for undo functions, and for evaluating expressions.
Queue — first in, first out
Operations: enqueue at the rear, dequeue at the front. Two pointers are needed. A linear queue wastes space as the front pointer moves up the array, so a circular queue wraps the pointers round using modulo arithmetic. Queues are used for print spooling, keyboard buffers and process scheduling.
Linked list
Each node holds data and a pointer to the next node; a start pointer gives the head and the last node points to null. Inserting or deleting means changing pointers, not shifting elements — which is why a linked list beats an array for frequent insertion in the middle. The cost is that you cannot jump straight to element $n$; you must follow the chain from the start.
Array or linked list?
Array: fast direct access by index, fixed size, expensive insertion. Linked list: cheap insertion and deletion, dynamic size, slow access, and extra memory for the pointers. State the trade-off, do not just say one is 'better'.
Kiểu dữ liệu trừu tượng là gì
Một kiểu dữ liệu trừu tượng được định nghĩa bằng các phép toán nó hỗ trợ, không phải bằng cách nó được lưu trữ. Ngăn xếp là ngăn xếp nhờ hai phép push và pop, dù bên trong nó được dựng bằng mảng hay bằng danh sách liên kết. Tách bạch hai điều đó chính là ý đang được kiểm tra.
Ngăn xếp — vào sau ra trước
Phép toán: push thêm vào đỉnh, pop lấy ra từ đỉnh, peek xem mà không lấy. Chỉ cần một con trỏ top là đủ. Tràn ngăn xếp xảy ra khi push lúc đã đầy; rỗng ngăn xếp khi pop lúc đã cạn — bắt buộc phải kiểm cả hai. Ngăn xếp dùng để lưu địa chỉ quay về của lời gọi chương trình con, cho chức năng hoàn tác, và để tính biểu thức.
Hàng đợi — vào trước ra trước
Phép toán: enqueue ở cuối, dequeue ở đầu. Cần hai con trỏ. Hàng đợi tuyến tính lãng phí chỗ vì con trỏ đầu cứ tiến lên trong mảng, nên hàng đợi vòng cho con trỏ quay vòng lại bằng phép chia lấy dư. Hàng đợi dùng cho hàng chờ in, bộ đệm bàn phím và điều độ tiến trình.
Danh sách liên kết
Mỗi nút chứa dữ liệu và một con trỏ tới nút kế tiếp; một con trỏ đầu chỉ vào nút đầu tiên và nút cuối trỏ tới null. Chèn hay xoá chỉ là đổi con trỏ chứ không phải dịch chuyển phần tử — và đó là lý do danh sách liên kết thắng mảng khi phải chèn giữa thường xuyên. Cái giá là không nhảy thẳng tới phần tử thứ $n$ được; phải đi lần theo chuỗi từ đầu.
Mảng hay danh sách liên kết?
Mảng: truy cập trực tiếp theo chỉ số rất nhanh, kích thước cố định, chèn tốn kém. Danh sách liên kết: chèn và xoá rẻ, kích thước động, truy cập chậm, và tốn thêm bộ nhớ cho con trỏ. Hãy nêu sự đánh đổi, đừng chỉ nói cái nào ‘tốt hơn’.
Thực hiện dãy thao tác sau, lần đầu trên một NGĂN XẾP và lần hai trên một HÀNG ĐỢI:
thêm A, thêm B, thêm C, lấy ra, thêm D, lấy ra, thêm E, lấy ra
Cho biết thứ tự các phần tử được lấy ra và nội dung còn lại.
Ngăn xếp (vào sau ra trước).
push A ⇒ [A]
push B ⇒ [A, B]
push C ⇒ [A, B, C]
pop ⇒ lấy ra C, còn [A, B]
push D ⇒ [A, B, D]
pop ⇒ lấy ra D, còn [A, B]
push E ⇒ [A, B, E]
pop ⇒ lấy ra E, còn [A, B]
Thứ tự lấy ra: C, D, E. Còn lại: A, B.
Hàng đợi (vào trước ra trước).
enqueue A ⇒ [A]
enqueue B ⇒ [A, B]
enqueue C ⇒ [A, B, C]
dequeue ⇒ lấy ra A, còn [B, C]
enqueue D ⇒ [B, C, D]
dequeue ⇒ lấy ra B, còn [C, D]
enqueue E ⇒ [C, D, E]
dequeue ⇒ lấy ra C, còn [D, E]
Thứ tự lấy ra: A, B, C. Còn lại: D, E.
Điều đáng rút ra. Cùng một dãy thao tác nhưng kết quả ngược hẳn: ngăn xếp trả về đúng ba phần tử mới nhất, hàng đợi trả về đúng ba phần tử cũ nhất. Đó là lý do phải chọn đúng cấu trúc theo bài toán — chức năng hoàn tác cần ngăn xếp (hoàn tác thao tác vừa làm), còn hàng chờ in cần hàng đợi (in theo thứ tự gửi lệnh).
Mẹo trình bày trong phòng thi: vẽ nội dung cấu trúc sau MỖI thao tác thay vì tính nhẩm — biểu điểm thường cho điểm cho các bước trung gian.
pop không kiểm ngăn xếp rỗng sẽ trả về rác hoặc làm chương trình dừng, và biểu điểm thường có một điểm riêng cho câu lệnh IF top = 0 THEN OUTPUT "stack empty".Đọc xong rồi — làm thử ngay
Bài tập của chương Algorithms and Data Structures gồm 14 câu trắc nghiệm và 3 đề tự luận. Đáp án hiện ngay khi chọn, miễn phí.