Stacks · สแต็ก (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 คืออะไร?
- Abstract Data Type (ADT) คือชุดรวมของข้อมูลพร้อมกับการดำเนินการต่างๆ บนข้อมูลนั้น
- คุณใช้การดำเนินการเหล่านี้โดยไม่สนใจวิธีการสร้างภายใน
- Stack, Queue และ Linked list ทั้งหมดนี้เป็น ADTs
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.
Stack เป็น LIFO
- Stack คือ Last In, First Out (LIFO)
- รายการสุดท้ายที่คุณเพิ่มเข้าไป จะเป็นรายการแรกที่ถูกดึงออกมา
- คิดถึงกองจาน: คุณหยิบจานด้านบนออกมาก่อน
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 และ pop ด้วย List
- เราสามารถสร้าง Stack จาก Python list ได้
- push =
stack.append(x)— เพิ่มไปที่ปลายสุด (ด้านบน) - pop =
stack.pop()— ลบออกและคืนค่าที่ปลายสุด (ด้านบน)
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 และ empty
- peek ดูที่ด้านบนโดยไม่ลบออก:
stack[-1] - Stack จะ empty เมื่อ
len(stack) == 0 - การ pop จาก Stack ที่ว่างเปล่าถือเป็นความผิดพลาด ดังนั้นควรตรวจสอบก่อน
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).
ใน伪代码 Cambridge
- การสอบสร้าง Stack จาก Array พร้อมตัวชี้
top(index)
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.
ข้อผิดพลาดที่พบบ่อย
- Stack เป็น Last-in, first-out: push ที่ด้านบน, pop จากด้านบน
- ตรวจสอบว่ามันไม่ว่างเปล่าก่อนที่คุณจะ pop
Now you try
- Use a list as your stack (
appendto push,popto remove). - Press Check answer to test your code.
ลองดูเลย
- ใช้ List เป็น Stack ของคุณ (
appendสำหรับ push,popสำหรับลบออก) - กด Check answer เพื่อทดสอบโค้ดของคุณ
A stack is LIFO · สแต็กเป็นแบบ LIFO
A stack pushes and pops at one end — last in, first out. · สแต็กทำ Push และ Pop ที่ ด้านเดียว — เข้าทีหลัง ออกทีแรก (last in, first out)
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].) · เริ่มจากส택ว่าง Push 1 แล้ว 2 แล้ว 3 จากนั้น pop หนึ่งครั้ง เก็บค่าที่ถูกลบออกไว้ใน top (top ควรจะเป็น 3 และส택ควรเป็น [1, 2])
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
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].) · ใช้สแต็กเพื่อ ** 역กลับ** list items. Push ทุกรายการลงสแต็ก แล้ว Pop ทั้งหมดเข้าไปใน result. (result ควรจะเป็น [3, 2, 1].)
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Write top(stack) that returns the top item (the last one) without removing it. If the stack is empty, return None. · เขียน top(stack) ที่ return รายการบนสุด (รายการสุดท้าย) โดยไม่ลบออก หากสักว่าง ให้ return None
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่