Stack là gì? Ngăn xếp (stack) trong Python bằng list
Bài 3/20 · Chương 23
Cấu trúc dữ liệu và giải thuật
- 7 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 11
Stack là gì? Stack, hay ngăn xếp, là một dãy chỉ thêm và lấy ở một đầu gọi là đỉnh: thứ vào sau cùng được lấy ra trước tiên. Bạn gặp nó mỗi lần bấm hoàn tác (Ctrl+Z) trong một ô nhập đơn: thao tác làm gần nhất bị gỡ trước, rồi mới tới thao tác trước đó.
Cần biết trước: append() và pop() của list, __init__ và self và độ phức tạp Big O.
Vào sau ra trước với append() và pop()
Hình dung xấp hóa đơn cắm trên que ở quầy: tờ cắm sau cùng nằm trên cùng và được rút ra trước. Quy tắc đó gọi là vào sau ra trước, tiếng Anh viết tắt là LIFO (last in, first out). List làm ngăn xếp được ngay khi bạn coi cuối list là đỉnh.
lich_su = []
lich_su.append("thêm cà phê sữa")
lich_su.append("thêm trà đào")
lich_su.append("xóa cà phê sữa")
print(lich_su[-1])
print(lich_su.pop())
print(lich_su.pop())
print(lich_su, len(lich_su))KẾT QUẢ
xóa cà phê sữa
xóa cà phê sữa
thêm trà đào
['thêm cà phê sữa'] 1Ba thao tác của ngăn xếp: append(x) đặt x lên đỉnh, pop() không đối số lấy phần tử ở đỉnh ra và xóa nó khỏi list, lich_su[-1] xem đỉnh mà không lấy ra. len(lich_su) cho biết còn bao nhiêu thao tác để hoàn tác. Đổi print(lich_su[-1]) thành print(lich_su[0]) rồi chạy lại: dòng đầu in thêm cà phê sữa, phần tử ở đáy chứ không phải ở đỉnh.
Vì sao đỉnh nằm ở cuối list
Bạn cũng có thể lấy đầu list làm đỉnh, thêm bằng insert(0, x) và lấy bằng pop(0). Kết quả vẫn đúng quy tắc vào sau ra trước, nhưng chậm. Theo trang "Time complexity of operations on built-in types" của tài liệu Python (xem ngày 15/11/2026), append() (tính bình quân qua nhiều lần thêm) và pop() ở cuối là O(1), còn insert(0, x) và pop(0) là O(n) vì mọi phần tử còn lại phải dời sang một ô.
lich_su = []
so_lan_doi = 0
for i in range(1000):
so_lan_doi += len(lich_su)
lich_su.insert(0, f"thao tác {i}")
print(lich_su[0], so_lan_doi)KẾT QUẢ
thao tác 999 499500Dòng so_lan_doi += len(lich_su) cộng số phần tử mà mỗi insert(0, x) phải dời. Một nghìn lần đặt lên đỉnh ở đầu list tốn gần nửa triệu lần dời, trong khi append() không dời phần tử nào.
Gói ngăn xếp vào một class
List có cả insert(), sort(), lấy theo chỉ số, nên code khác dễ vô tình phá quy tắc vào sau ra trước. Một class chỉ mở ra các thao tác của ngăn xếp và giữ list ở bên trong.
class NganXep:
def __init__(self):
self.ds = []
def day(self, x):
self.ds.append(x)
def lay(self):
if not self.ds:
return None
return self.ds.pop()
def xem_dinh(self):
return self.ds[-1] if self.ds else None
ngan_xep = NganXep()
ngan_xep.day("thêm bạc xỉu")
ngan_xep.day("đổi bạc xỉu thành trà đào")
print(ngan_xep.lay(), "|", ngan_xep.xem_dinh())KẾT QUẢ
đổi bạc xỉu thành trà đào | thêm bạc xỉuLần lay() đầu lấy thao tác vừa đẩy, còn xem_dinh() cho thấy thao tác nằm ngay dưới nó. lay() trên ngăn xếp rỗng trả về None thay cho lỗi, nên nơi gọi chỉ cần hỏi kết quả có phải None không. Cả ba phương thức đều O(1).
Đảo thứ tự và những chỗ ngăn xếp xuất hiện
Đẩy hết một dãy vào ngăn xếp rồi lấy ra hết, bạn được dãy đó theo thứ tự ngược. Tuyến xe lượt về đi qua các trạm của lượt đi theo chiều ngược lại:
luot_di = ["Bến xe phía Bắc", "Ga Huế", "Đại Nội", "Chợ Đông Ba"]
ngan_xep = []
for tram in luot_di:
ngan_xep.append(tram)
luot_ve = []
for _ in range(len(ngan_xep)):
luot_ve.append(ngan_xep.pop())
print(luot_ve)KẾT QUẢ
['Chợ Đông Ba', 'Đại Nội', 'Ga Huế', 'Bến xe phía Bắc']Để đảo một list có sẵn, luot_di[::-1] của bài cắt list gọn hơn. Ngăn xếp có ích khi các phần tử tới dần và bạn cần xử lý cái mới nhất trước. Kiểm tra dấu ngoặc mở và đóng có khớp nhau không là một bài như vậy, nằm ở bài kiểm tra dấu ngoặc cân bằng. Python cũng giữ các lời gọi hàm đang chờ trong một ngăn xếp, chuyện mà bài đệ quy kể kỹ.
Kiểm tra nhanh
Sau
ds = [],ds.append("A"),ds.append("B")vàds.append("C"), lệnhprint(ds.pop(), ds[-1])in ra gì?A CC BC C
Với
ds = [],ds.pop()cho kết quả gì?None- Không in gì
- Báo lỗi
IndexError
Những thao tác nào giữ đúng quy tắc vào sau ra trước khi đỉnh là cuối list
ds?- Thêm bằng
ds.append(x) - Lấy bằng
ds.pop(0) - Xem đỉnh bằng
ds[-1] - Lấy bằng
ds.pop()
- Thêm bằng
Trong khung bẫy lấy ra bằng
pop(0), lần hoàn tác gỡ thao tác nào?thêm cà phê sữaxóa cà phê sữathêm trà đào
Bài tập
Viết hoàn tác và làm lại bằng hai ngăn xếp
Ô nhập đơn giữ hai ngăn xếp là list, đỉnh ở cuối: da_lam (đã làm) và da_hoan_tac (vừa hoàn tác). Viết thân bốn phương thức của LichSu:
lam(viec): đặtvieclên đỉnhda_lam, làm rỗngda_hoan_tac.hoan_tac(): lấy thao tác ở đỉnhda_lam, đặt lên đỉnhda_hoan_tac, trả về thao tác đó.lam_lai(): lấy ở đỉnhda_hoan_tac, đặt lại lênda_lam, trả về thao tác đó.viec_cuoi(): thao tác ở đỉnhda_lam, không lấy ra.
Ngăn xếp cần lấy hay xem mà rỗng thì phương thức trả về None.
Trả về: hoan_tac(), lam_lai() và viec_cuoi() trả về tên thao tác, một str, hoặc None.
class LichSu:
def __init__(self):
self.da_lam = []
self.da_hoan_tac = []
def lam(self, viec):
pass # Viết thân các phương thức thay cho các dòng pass
def hoan_tac(self):
pass
def lam_lai(self):
pass
def viec_cuoi(self):
passTóm tắt
Ngăn xếp chỉ thêm và lấy ở đỉnh, theo quy tắc vào sau ra trước (LIFO).
Lấy cuối list làm đỉnh:
append(x)đặt lên,pop()lấy ra,ds[-1]xem đỉnh, cả ba là O(1) (append()tính bình quân).insert(0, x)vàpop(0)phải dời mọi phần tử còn lại nên là O(n).pop()trên list rỗng báoIndexError: pop from empty list, hãy hỏiif ds:trước.pop(0)trên ngăn xếp có đỉnh ở cuối lấy nhầm phần tử cũ nhất mà không báo lỗi.Hoàn tác và làm lại dùng hai ngăn xếp chuyền thao tác cho nhau.
Câu hỏi thường gặp
Ngăn xếp là gì, khác hàng đợi chỗ nào?
Ngăn xếp lấy ra phần tử vào sau cùng, còn hàng đợi lấy ra phần tử vào đầu tiên, như hàng chờ ở quầy. Trong Python, hàng đợi dùng deque thay cho list vì list lấy ở đầu chậm. Bài hàng đợi ngay sau bài này dựng nó.
Python có module riêng cho stack không?
Không cần: list là ngăn xếp đủ tốt cho phần lớn chương trình. collections.deque cũng có append() và pop() ở cuối nên làm ngăn xếp được, bài deque dạy kiểu này. Khi nhiều luồng cùng đẩy và lấy, thư viện chuẩn có queue.LifoQueue.
Ngăn xếp trong Python có giới hạn số phần tử không?
List làm ngăn xếp chỉ bị giới hạn bởi bộ nhớ của máy. Giới hạn bạn hay gặp là của ngăn xếp lời gọi hàm: hàm gọi lồng nhau quá sâu thì Python báo RecursionError, chuyện của bài đệ quy.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.