Bỏ qua đến nội dung chính
Mục lục

Stack là gì? Ngăn xếp (stack) trong Python bằng list

AIDev Team · duyệt: Nguyễn Việt Chung

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

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.

python
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'] 1

Ba 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 ô.

python
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 499500

Dò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.

python
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ỉu

Lầ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:

python
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

  1. Sau ds = [], ds.append("A"), ds.append("B") và ds.append("C"), lệnh print(ds.pop(), ds[-1]) in ra gì?

    • A C
    • C B
    • C C
  2. Với ds = [], ds.pop() cho kết quả gì?

    • None
    • Không in gì
    • Báo lỗi IndexError
  3. 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()
  4. 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ữa
    • xóa cà phê sữa
    • thêm trà đào
Đúng hết lần đầu +15 XP

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): đặt viec lên đỉnh da_lam, làm rỗng da_hoan_tac.

  • hoan_tac(): lấy thao tác ở đỉnh da_lam, đặt lên đỉnh da_hoan_tac, trả về thao tác đó.

  • lam_lai(): lấy ở đỉnh da_hoan_tac, đặt lại lên da_lam, trả về thao tác đó.

  • viec_cuoi(): thao tác ở đỉnh da_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.

python
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):
        pass

Tó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áo IndexError: pop from empty list, hãy hỏi if 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ủ đề

stack là gì

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

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.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập