Stack: animation và bài tập CSD201

Animation Stack: push, pop, peek, linked list và kiểm tra dấu ngoặc. Video 3 phút 12 giây, chú thích tiếng Việt, kèm bài tập Java.

Stack lưu phần tử theo nguyên tắc vào sau, ra trước (LIFO). Xem các khối chuyển động, dừng lại để đoán kết quả, rồi tự cài đặt bằng Java.

Push, pop, peek, con trỏ head và kiểm tra dấu ngoặc.

Mở / tải video đầy đủ

Xem từng phần

1. Push, pop, peek và Stack rỗng (60 giây)

push(x) thêm x lên đỉnh; peek() đọc đỉnh nhưng giữ nguyên Stack; pop() lấy phần tử ở đỉnh ra.

Mở clip riêng

Dừng và đoán: Sau push(10), push(20), pop(), push(30), peek() trả về gì? Stack còn bao nhiêu phần tử?

Xem đáp án

peek() trả về 30. Stack còn 2 phần tử: 10 ở đáy, 30 ở đỉnh. Gọi peek không làm giảm số phần tử.

2. Linked Stack và con trỏ head (36 giây)

Đặt đỉnh Stack ở đầu singly linked list. Khi push, nối node mới với head cũ trước khi thay head. Khi pop, lưu giá trị rồi chuyển head sang node kế tiếp.

Mở clip riêng

Dừng và giải thích: Vì sao thứ tự node.next = head; head = node; quan trọng?

Xem đáp án

Phải giữ liên kết đến danh sách cũ. Nếu đổi head trước rồi gán node.next = head, node mới sẽ trỏ vào chính nó thay vì head cũ.

3. Kiểm tra dấu ngoặc đúng và sai (96 giây)

Quét từ trái sang phải: push dấu mở; gặp dấu đóng thì kiểm tra dấu ở đỉnh. Đủ số dấu mở và đóng chưa đảm bảo đúng thứ tự.

Mở clip riêng

  • {[()]}: hợp lệ.
  • ([)]: gặp ) nhưng đỉnh là [, đang cần ].
  • ((: hết chuỗi mà Stack vẫn còn dấu mở.
  • ): gặp dấu đóng khi Stack rỗng.

Bài tập sau khi xem

  1. Tự cài LinkedStack. Viết push, pop, peek, isEmpty. Test trường hợp rỗng, một phần tử, nhiều phần tử và push lại sau khi pop hết.
  2. Viết hàm kiểm tra dấu ngoặc. Hỗ trợ (), [], {}; bỏ qua ký tự khác. Test thêm (a+b)*c, a+b), ((a+b). Muốn nâng mức khó, trả về vị trí lỗi và dấu đóng đang mong đợi.
  3. Thử Undo. Mỗi lần thay nội dung, push bản cũ vào Stack. Khi Undo, pop để khôi phục. Xử lý trường hợp không còn lịch sử.

Ba điều cần nhớ

  • Chỉ thêm và lấy ở đỉnh. Với singly linked list, push/pop tại head đều O(1).
  • Kiểm tra rỗng trước khi truy cập đỉnh. Video chọn cách báo EmptyStackException.
  • Chuỗi ngoặc chỉ hợp lệ khi không có lỗi ghép cặp và Stack rỗng lúc kết thúc.

Trong video, peek() tương ứng thao tác top() của slide môn học. Ví dụ dùng Stack tự cài với push không trả giá trị; chữ ký của thư viện khác có thể khác. Phần dấu ngoặc là bài luyện thuật toán, không phải parser Java/HTML đầy đủ. Đây là bài tập bổ sung, không thay thế đề Assignment chính thức.