Stacks · Ngăn xếp (Stacks)
What is an ADT?
- An Abstract Data Type (ADT) is a collection of data plus a set of operations on it.
- You use the operations and ignore how it is built inside.
- A stack, a queue, and a linked list are all ADTs.
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.
A stack is LIFO
- A stack is Last In, First Out (LIFO).
- The last item you add is the first one you take off.
- Think of a stack of plates: you take the top plate first.
Ngăn xếp遵循 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 and pop with a list
- We can build a stack from a Python list.
- push =
stack.append(x)— add to the end (the top). - pop =
stack.pop()— remove and return the end (the top).
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 and empty
- peek at the top without removing it:
stack[-1]. - A stack is empty when
len(stack) == 0. - Popping an empty stack is an error, so check first.
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?
In Cambridge pseudocode
- The exam builds a stack from an array plus a
toppointer (an index).
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
Common mistakes
- A stack is last-in, first-out: push to the top, pop from the top.
- Check it is not empty before you pop.
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.
Now you try
- Use a list as your stack (
appendto push,popto remove). - Press Check answer to test your code.
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.
A stack is LIFO · Ngăn xếp hoạt động theo LIFO
A stack pushes and pops at one end — last in, first out. · Ngăn xếp đẩy và lấy ở một đầu — cuối vào, đầu ra.
Start with an empty stack. Push 1, then 2, then 3. Then pop once, storing the removed value in top. (top should be 3 and the stack should be [1, 2].) · 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].)
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Use a stack to reverse the list items. Push every item onto a stack, then pop them all into result. (result should be [3, 2, 1].) · 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].)
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Write top(stack) that returns the top item (the last one) without removing it. If the stack is empty, return None. · 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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.