1. Nguyên lý LIFO và FIFO

Ngăn xếp (Stack) và Hàng đợi (Queue) là hai cấu trúc dữ liệu tuyến tính có quy tắc thêm/xóa phần tử bị ràng buộc chặt chẽ nhằm phục vụ các luồng xử lý đặc thụ trong máy tính.

       STACK (LIFO)                      QUEUE (FIFO)
Last In, First Out              First In, First Out

      |  Data 3  |  <-- Top         In --> [3][2][1] --> Out
      |  Data 2  |                         Rear   Front
      |  Data 1  |
      +----------+

a) Ngăn xếp (Stack): LIFO (Last In, First Out - Vào sau, Ra trước)

• Nguyên lý: Phần tử nào được thêm vào cuối cùng sẽ là phần tử đầu tiên bị lấy ra.

• Mô hình thực tế: Chồng đĩa trong nhà ăn. Đĩa đặt lên trên cùng sau cùng sẽ là đĩa được lấy ra dùng trước.

• Các thao tác cốt lõi:

  • push(x): Đẩy phần tử x vào đỉnh (Top) $\rightarrow O(1)$.

  • pop(): Lấy phần tử ở đỉnh ra khỏi Stack $\rightarrow O(1)$.

  • peek() / top(): Xem giá trị phần tử ở đỉnh mà không xóa $\rightarrow O(1)$.

b) Hàng đợi (Queue): FIFO (First In, First Out - Vào trước, Ra trước)

• Nguyên lý: Phần tử nào vào hàng đợi trước sẽ được phục vụ và đi ra trước.

• Mô hình thực tế: Hàng người xếp hàng mua vé.

• Các thao tác cốt lõi:

  • enqueue(x): Thêm phần tử x vào đuôi hàng đợi (Rear) $\rightarrow O(1)$.

  • dequeue(): Lấy phần tử ở đầu hàng đợi (Front) ra xử lý $\rightarrow O(1)$.

2. Cài đặt Stack & Queue trong Python

Trong Python, ta có thể cài đặt Stack dễ dàng bằng list. Tuy nhiên, đối với Queue, việc sử dụng list.pop(0) có độ phức tạp thời gian lên tới $O(N)$ (vì phải dịch chuyển toàn bộ mảng sang trái).

Để đạt độ phức tạp $O(1)$ cho cả enqueue và dequeue, ta sử dụng collections.deque (Double-ended Queue - Hàng đợi 2 đầu cài đặt bằng Danh sách liên kết đôi).

from collections import deque


# --- 1. CÀI ĐẶT STACK (Dùng List) ---
class Stack:

    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)  # O(1) Amortized

    def pop(self):
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        return self._items.pop()  # O(1)

    def peek(self):
        return self._items[-1] if not self.is_empty() else None

    def is_empty(self):
        return len(self._items) == 0


# --- 2. CÀI ĐẶT QUEUE (Dùng collections.deque) ---
class Queue:

    def __init__(self):
        self._items = deque()

    def enqueue(self, item):
        self._items.append(item)  # Thêm vào đuôi - O(1)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Dequeue from empty queue")
        return self._items.popleft()  # Lấy từ đầu - O(1)

    def is_empty(self):
        return len(self._items) == 0