Ngăn xếp (Stacks)
ADT là gì?
- Một Abstract Data Type (ADT - Kiểu Dữ Liệu Trừu Tượng) là một tập hợp dữ liệu kèm theo một bộ các thao tác trên nó.
- Bạn sử dụng các thao tác và bỏ qua cách nó được xây dựng bên trong.
- Một stack (ngăn xếp), một queue (hàng đợi), và một linked list (danh sách liên kết) đều là các ADT.
Một ngăn xếp tuân theo nguyên tắc LIFO
- Ngăn xếp là Last In, First Out (Vào sau, Ra trước - LIFO).
- Mục cuối cùng bạn thêm vào là mục đầu tiên bạn lấy ra.
- Hãy tưởng tượng chồng đĩa: bạn lấy chiếc đĩa ở trên cùng trước.
push và pop với danh sách
- Chúng ta có thể xây dựng ngăn xếp từ một danh sách Python.
- push =
stack.append(x)— thêm vào cuối (phía trên). - pop =
stack.pop()— xóa và trả về cuối (phía trên).
stack = []
stack.append("a")
stack.append("b")
print(stack.pop())
print(stack)
peek và empty
- peek (nhìn trộm) vào phía trên mà không xóa nó:
stack[-1]. - Ngăn xếp empty (trống) khi
len(stack) == 0. - Pop một ngăn xếp trống là một lỗi, vì vậy hãy kiểm tra trước.
stack = [10, 20, 30]
print(stack[-1]) # peek the top
print(len(stack) == 0) # is it empty?
Trong pseudocode Cambridge
- Bài thi xây dựng ngăn xếp từ mảng cộng với một con trỏ
top(một chỉ số).
DECLARE stack : ARRAY[1:10] OF INTEGER
DECLARE top : INTEGER
top ← 0 // 0 means empty
// push value
top ← top + 1
stack[top] ← value
// pop into value
value ← stack[top]
top ← top - 1
Lỗi thường gặp
- Ngăn xếp là vào sau, ra trước: push lên trên, pop từ trên.
- Kiểm tra nó không rỗng trước khi pop.
Bây giờ bạn thử
- Dùng danh sách làm ngăn xếp của bạn (
appendđể push,popđể xóa). - Nhấn Check answer (Kiểm tra câu trả lời) để thử mã của bạn.
Ngăn xếp hoạt động theo LIFO
Ngăn xếp đẩy và lấy ở một đầu — cuối vào, đầu ra.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Bắt đầu với ngăn xếp rỗng. Đẩy 1, sau đó 2, rồi 3. Sau đó lấy một lần, lưu giá trị bị loại bỏ vào top. (top nên bằng 3 và ngăn xếp nên là [1, 2].)
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Dùng ngăn xếp để đảo ngược danh sách items. Đẩy từng phần tử lên ngăn xếp, sau đó lấy tất cả vào result. (result nên là [3, 2, 1].)
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Viết top(stack) trả về phần tử trên cùng (phần tử cuối cùng) mà không loại bỏ nó. Nếu ngăn xếp rỗng, trả về None.
Nhấn Chạy để xem kết quả ở đây.