Nâng Cấp Stack/Queue: Bí Kíp Tìm Min Siêu Tốc

Nếu anh em thấy hay thì ủng hộ mình 1 follow + 1 upvote + 1 bookmark + 1 comment cho bài viết này tại Mayfest 2025 nhé, cảm ơn anh em!

Xin chào anh em, những chiến binh thuật toán và các tín đồ code!

Đã bao giờ anh em thấy cái stack (ngăn xếp) hay queue (hàng đợi) của mình nó hơi... "ngáo ngơ" chưa? Nó nhớ vanh vách thằng mới nhất (top/front), nhưng hỏi nó "Ê ku, trong đám mày đang giữ, thằng nào 'nhẹ ký' nhất?" thì mặt nó nghệt ra ngay. Ừ thì stack là LIFO (Vào Sau Ra Trước), queue là FIFO (Vào Trước Ra Trước), bản chất nó thế.

Nhưng trong giang hồ competitive programming và tối ưu thuật toán đầy khắc nghiệt, đôi khi chúng ta cần đám "ngáo ngơ" này thông minh hơn một chút!

Hôm nay, tôi sẽ vén màn bí mật về hai "siêu anh hùng" thầm lặng trong thế giới cấu trúc dữ liệu: Minimum Stack và Minimum Queue. Tưởng tượng chúng như phiên bản nâng cấp, có thêm "giác quan thứ sáu" để luôn biết phần tử nhỏ nhất đang trốn ở xó nào, mà lại còn nhanh như điện giật - lý tưởng là $O(1)$.

Tại sao lại cần chúng? Vì trong vô số bài toán, việc theo dõi giá trị nhỏ nhất một cách hiệu quả song song với các thao tác stack/queue thông thường chính là chìa khóa vàng mở ra cánh cửa tối ưu.

Nào, thắt dây an toàn! Chúng ta chuẩn bị làm một chuyến "tàu lượn siêu tốc" vào thế giới của MinStack và MinQueue. Tôi sẽ mổ xẻ định nghĩa, khám phá cách cài đặt "khôn như rận" (không cần bùa phép gì đâu, yên tâm!), phân tích hiệu năng như nhà khoa học khó tính, xem chúng "múa võ" ở đâu, và tất nhiên, không thể thiếu màn "vọc code" thực tế!

1. MinStack: Mò Kim Đáy Bể (Trong Nháy Mắt!)

1.1 "Anh Là Ai?" - Định Nghĩa & Mục Đích

Minimum Stack (Ngăn xếp tối thiểu), hay gọi thân mật là MinStack, là một cấu trúc dữ liệu ngăn xếp hỗ trợ đủ bộ các võ công cơ bản:

• push(val): Đẩy val lên đỉnh.
• pop(): Đá đít thằng trên đỉnh.
• top(): Nhòm trộm thằng trên đỉnh (không đá).

Và chiêu cuối của chúng ta:

• getMin(): Trả về phần tử có giá trị nhỏ nhất đang có mặt trong ngăn xếp.

Mục tiêu tối thượng là tất cả các chiêu này, đặc biệt là getMin(), phải thực hiện trong thời gian không đổi $O(1)$.

Tại sao cần MinStack? Nó cực hữu ích khi anh em cần biết min tức thì mà vẫn muốn giữ kiểu LIFO của stack. Ví dụ như theo dõi giá cổ phiếu thấp nhất, hay trong vài thuật toán xử lý biểu thức.

Ví von vui: Tưởng tượng anh em đang xếp chồng đĩa. Mỗi lần đặt đĩa mới lên, có một chú lùn siêu trí nhớ đứng cạnh, thì thầm vào tai cân nặng cái đĩa nhẹ nhất trong cả chồng hiện tại. Thao tác getMin() chỉ đơn giản là hỏi chú lùn đó thôi!

1.2 Các Chiêu Thức Cài Đặt ($O(1)$ Cho getMin)

Làm sao chú lùn biết min mà không cần lật tung cả chồng đĩa mỗi lần hỏi? Đây là lúc sự "lươn lẹo" thông minh của cấu trúc dữ liệu tỏa sáng!

Chiêu 1: Người Bạn Đồng Hành (Ngăn Xếp Phụ)

Cách phổ biến và dễ nuốt nhất. Chúng ta xài tới hai stack:

• mainStack: Chứa tất cả phần tử như stack bình thường.
• minStack: Chứa giá trị nhỏ nhất tương ứng tại mỗi "tầng" của mainStack.

Logic hoạt động:

• push(val):
  • Đẩy val vào mainStack.
  • Lấy current_min là thằng trên đỉnh minStack (nếu minStack không rỗng) hoặc giá trị vô cùng lớn.
  • Đẩy min(val, current_min) vào minStack. Điều này đảm bảo minStack luôn có cùng size với mainStack và giữ đúng giá trị min khi pop. (Cách này an toàn và dễ hơn việc chỉ push khi val <= minStack.top()).
• pop():
  • Pop khỏi mainStack.
  • Pop khỏi minStack (để giữ đồng bộ).
• top():
  • Trả về mainStack.top().
• getMin():
  • Trả về minStack.top().

Phân tích độ phức tạp:

• Thời gian: Mỗi thao tác chỉ gồm các lệnh cơ bản $O(1)$ của stack và phép so sánh. Vậy tất cả đều là $O(1)$.
• Không gian: Cần thêm một stack phụ, tối đa bằng stack chính. Vậy là $O(N)$, với $N$ là số phần tử tối đa.

Cách này tốn gấp đôi bộ nhớ (trường hợp xấu nhất), nhưng dễ code và đảm bảo $O(1)$ ngon lành. Thường là lựa chọn số 1 khi phỏng vấn hoặc thi đấu nếu bộ nhớ không quá eo hẹp.

Chiêu 2: Cặp Đôi Hoàn Hảo (Lưu Cặp {Giá Trị, Min Hiện Tại})

Thay vì hai stack, ta nhét luôn thông tin min vào cùng một stack. Mỗi phần tử là một cặp (value, current_minimum), với current_minimum là giá trị nhỏ nhất từ đáy lên đến nó.

Logic hoạt động:

• push(val):
  • Tính new_min: Nếu stack rỗng, new_min = val. Ngược lại, new_min = min(val, stack.top().second).
  • Đẩy cặp {val, new_min} vào stack.
• pop():
  • Pop cặp trên cùng.
• top():
  • Trả về stack.top().first (giá trị thực).
• getMin():
  • Trả về stack.top().second (min đã lưu).

Phân tích độ phức tạp:

• Thời gian: Vẫn là $O(1)$ cho tất cả.
• Không gian: Mỗi phần tử lưu thêm một giá trị min, nên vẫn là $O(N)$.

Phương pháp này gắn min trực tiếp vào từng phần tử. Khi push, nó "thừa kế" min từ dưới hoặc tự làm min mới. Giá trị min của cả stack luôn nằm ở second của cặp trên cùng. Hiệu năng và không gian tiệm cận tương đương stack phụ, nhưng code có vẻ "gọn" hơn vì chỉ dùng một stack.

(Bonus) Chiêu 3: Ninja Tiết Kiệm (Không Gian Phụ $O(1)$)

Kỹ thuật này hay ho nhưng hack não hơn, dùng biến minValue lưu min hiện tại và "mã hóa" giá trị đẩy vào stack khi min thay đổi.

Logic hoạt động (Ý tưởng chính):

• push(val):
  • Nếu stack rỗng: push val, minValue = val.
  • Nếu val >= minValue: push val bình thường.
  • Nếu val < minValue (min mới!):
    • Push giá trị mã hóa: 2 * val - minValue (đảm bảo nhỏ hơn val).
    • Cập nhật minValue = val.
• pop():
  • Lấy topVal = stack.top(). Pop.
  • Nếu topVal < minValue (là giá trị mã hóa):
    • Khôi phục minValue cũ: minValue = 2 * minValue - topVal.
    • Giá trị thực được pop là minValue (đã khôi phục).
  • Nếu topVal >= minValue: giá trị được pop là topVal.
• top():
  • Lấy topVal = stack.top().
  • Nếu topVal < minValue: trả về minValue (vì đỉnh bị mã hóa).
  • Ngược lại: trả về topVal.
• getMin():
  • Trả về minValue.

Phân tích độ phức tạp:

• Thời gian: Vẫn $O(1)$.
• Không gian: Chỉ dùng thêm biến minValue, không phụ thuộc $N$. Vậy không gian phụ là $O(1)$.

Kỹ thuật này siêu tiết kiệm không gian, nhưng đổi lại là logic phức tạp, khó debug, dễ tràn số nếu không dùng kiểu dữ liệu lớn (ví dụ: long long trong C++ khi val là int). Cũng có thể gặp vấn đề với số cực tiểu. Đây là "mẹo" hay nhưng ít thực tế hơn trừ khi bộ nhớ là yếu tố sống còn.

Bảng So Kè Các Chiêu MinStack

Rõ ràng, hai chiêu đầu ($O(N)$ không gian) là lựa chọn cân bằng nhất. Chiêu $O(1)$ không gian thì để dành khi nào bị "bóp" bộ nhớ thôi anh em ạ.

2. MinQueue: Ngắm "Người Lùn Nhất" Trong Hàng Xếp Rồng

2.1 "Xin Chào, Tôi Là Ai?" - Định Nghĩa & Mục Đích

Tương tự MinStack, Minimum Queue (Hàng đợi tối thiểu) hay MinQueue là hàng đợi hỗ trợ:

• enqueue(val): Thêm val vào cuối hàng.
• dequeue(): Tiễn khách đầu hàng.
• front() (hoặc peek()): Nhòm trộm khách đầu hàng.

Và khả năng đặc biệt:

• getMin(): Trả về phần tử có giá trị nhỏ nhất đang có mặt trong hàng đợi.

Mục tiêu là getMin() hiệu quả ($O(1)$ là ngon), trong khi vẫn giữ tính FIFO.

Tại sao cần MinQueue? Hữu ích khi cần xử lý FIFO nhưng đồng thời phải biết min hiện tại, ví dụ bài toán cửa sổ trượt (sliding window) hay các mô phỏng cần theo dõi trạng thái tối thiểu.

Phân biệt: Đừng nhầm với Priority Queue (Hàng đợi ưu tiên)! Priority Queue khi dequeue sẽ loại bỏ thằng min (hoặc max), phá vỡ thứ tự FIFO. MinQueue vẫn dequeue thằng vào đầu tiên, chỉ thêm khả năng ngó trộm min.

Ví von vui: Tưởng tượng anh em đang xếp hàng siêu thị. enqueue là có người mới nối đuôi, dequeue là người đầu hàng tính tiền xong té. getMin giống như có cái loa phóng thanh tự động, cứ vài giây lại oang oang chiều cao của người thấp nhất trong hàng (ở bất kỳ vị trí nào), mà người đó không cần bước ra!

2.2 Các Chiêu Thức Cài Đặt (Tìm Min Hiệu Quả)

Chiêu 1: Điệu Tango Hai Ngăn Xếp (Dùng Hai MinStack)

Cách kinh điển, mô phỏng queue bằng hai stack, nhưng lần này là hai MinStack.

• s1 (stack vào): Cho enqueue.
• s2 (stack ra): Cho dequeue và front.

Logic hoạt động:

• enqueue(val):
  • Đẩy val vào s1 (dùng push của MinStack để cập nhật min của s1).
• dequeue():
  • Nếu s2 rỗng: Chuyển hết từ s1 sang s2. Khi chuyển, pop từ s1 và push vào s2 (dùng push của MinStack để s2 tự cập nhật min). Thao tác này đảo ngược thứ tự, đưa thằng "già nhất" của s1 lên đỉnh s2.
  • Sau đó (hoặc nếu s2 không rỗng), pop khỏi s2.
• front():
  • Nếu s2 rỗng, chuyển từ s1 sang s2.
  • Trả về s2.top().
• getMin():
  • Nếu cả hai rỗng, queue rỗng.
  • Nếu chỉ một rỗng, trả về getMin() của stack còn lại.
  • Nếu cả hai không rỗng, trả về min(s1.getMin(), s2.getMin()).

Phân tích độ phức tạp:

• Thời gian:
  • enqueue: $O(1)$.
  • dequeue, front: $O(1)$ trung bình (amortized). Việc chuyển từ s1 sang s2 có thể tốn $O(N)$, nhưng mỗi phần tử chỉ bị chuyển đúng 1 lần. Chia đều chi phí này ra, trung bình mỗi thao tác tốn $O(1)$.
  • getMin: $O(1)$ trong trường hợp xấu nhất.
• Không gian: $O(N)$ cho hai stack.

Cách này khá thanh lịch, tái sử dụng MinStack và kỹ thuật mô phỏng queue bằng hai stack.

Chiêu 2: Nhà Vô Địch Deque (Dùng Deque Đơn Điệu)

Cách này dùng deque (hàng đợi hai đầu) để chỉ lưu những phần tử có khả năng là min trong tương lai, duy trì thứ tự đơn điệu không giảm trong deque. Kỹ thuật này gắn liền với bài toán Cửa Sổ Trượt Tối Thiểu (Sliding Window Minimum).

Logic hoạt động (dùng chỉ số để xóa đúng):

• Lưu cặp (value, index) trong deque, index là bộ đếm cnt_added tăng dần.
• Dùng bộ đếm cnt_removed cho số lần dequeue.
• enqueue(val):
  • while deque không rỗng VÀ deque.back().first >= val: deque.pop_back() (Loại bỏ mấy thằng "to con" ở cuối vì chúng hết cửa làm min khi val còn đó).
  • deque.push_back({val, cnt_added}).
  • Tăng cnt_added.
• dequeue():
  • Nếu deque không rỗng VÀ deque.front().second == cnt_removed: deque.pop_front() (Chỉ loại bỏ đầu deque nếu chỉ số nó khớp với thằng đáng lẽ bị loại theo FIFO).
  • Luôn tăng cnt_removed (để đánh dấu một phần tử logic đã bị loại).
• front(): Cách này chủ yếu tối ưu getMin. Muốn lấy front thực sự cần cấu trúc queue riêng.
• getMin():
  • Trả về deque.front().first (nếu deque không rỗng).

Phân tích độ phức tạp:

• Thời gian:
  • enqueue, dequeue: $O(1)$ trung bình (amortized). Mỗi phần tử vào/ra deque tối đa 1 lần.
  • getMin: $O(1)$ trường hợp xấu nhất.
• Không gian: $O(N)$ trường hợp xấu nhất (enqueue giảm dần). Nhưng trong bài cửa sổ trượt size $K$, thường chỉ là $O(K)$.

Cách này xây dựng trực tiếp deque đơn điệu. Loại bỏ phần tử lớn hơn từ cuối khi enqueue đảm bảo đầu deque luôn là min của đám "còn sống". Dùng chỉ số cnt_added, cnt_removed là cực kỳ quan trọng để xử lý dequeue đúng thứ tự FIFO. Đây là cốt lõi của thuật toán Sliding Window Minimum.

Bảng So Kè Các Chiêu MinQueue

Chiêu Hai MinStack dễ hình dung hơn nếu quen mô phỏng queue bằng stack. Chiêu Deque là tối ưu trực tiếp, hiệu quả hơn và liên quan đến các mẫu thuật toán quan trọng khác.

3. Thực Chiến: MinStack & MinQueue "Múa Võ" Ở Đâu?

Mấy cấu trúc "biết tuốt" này không chỉ để trưng. Chúng là hàng nóng trong kho vũ khí của dân competitive programming.

• Cửa Sổ Trượt Tối Thiểu/Tối Đa (Sliding Window Minimum/Maximum)

  • Bài toán: Cho mảng và cửa sổ K, tìm min (hoặc max) trong tất cả cửa sổ con kích thước K.
  • Giải pháp: Dùng MinQueue (hoặc MaxQueue) bằng Deque. Cửa sổ trượt sang phải -> enqueue phần tử mới, dequeue phần tử cũ. getMin() cho kết quả cửa sổ hiện tại trong $O(1)$. Tổng thời gian $O(N)$.
  • Liên kết: Ứng dụng kinh điển nhất của MinQueue dùng deque.

• Bài Toán Stock Span

  • Bài toán: Cho mảng giá cổ phiếu, với mỗi ngày i, tìm số ngày liên tiếp trước đó (tính cả i) mà giá <= giá ngày i.
  • Giải pháp: Dùng stack thông thường (lưu chỉ số). Duyệt mảng, với price[i], while stack không rỗng và price[stack.top()] <= price[i], pop khỏi stack. Span là i - stack.top() (hoặc i + 1 nếu stack rỗng). Push i vào stack. Thời gian $O(N)$.
  • Liên kết: Dùng kỹ thuật stack đơn điệu (monotonic stack) tương tự để tìm "phần tử lớn hơn gần nhất bên trái". Kỹ thuật này thường học cùng MinStack/MaxStack.

• Phần Tử Nhỏ Hơn/Lớn Hơn Gần Nhất (Nearest Smaller/Greater Element)

  • Bài toán: Với mỗi phần tử, tìm phần tử gần nhất bên trái (hoặc phải) mà nhỏ hơn (hoặc lớn hơn) nó.
  • Giải pháp: Lại là stack đơn điệu! Duyệt mảng. Để tìm nhỏ hơn gần nhất bên trái, while stack không rỗng và stack.top() >= current_element, pop. stack.top() (nếu còn) là kết quả. Push current_element. Thời gian $O(N)$.
  • Liên kết: Củng cố mẫu stack đơn điệu. LeetCode Next Greater Element I/II là ví dụ.

4. Góc Lập Trình: Code Mẫu "Cháy" Cả C++ Lẫn Python

Lý thuyết suông mãi cũng chán, phải có code chạy được mới phê! Dưới đây là code mẫu cho các chiêu chính.

(Lưu ý: Code mẫu giả định các thao tác top(), getMin(), dequeue() chỉ được gọi khi cấu trúc không rỗng, tương tự các đề bài phổ biến như LeetCode. Trong thực tế cần xử lý lỗi/exception cẩn thận hơn.)

4.1 MinStack (Dùng Ngăn xếp Phụ trợ)

C++:

class MinStackAux
{
private: stack<int> mainStack; stack<int> minStack; // Ngăn xếp phụ trợ public: MinStackAux() { // Khởi tạo minStack với giá trị lớn để xử lý trường hợp rỗng minStack.push(INT_MAX); } void push(int val) { mainStack.push(val); // Luôn đẩy min mới (hoặc min cũ nếu val lớn hơn) vào minStack minStack.push(min(val, minStack.top())); } void pop() { if (!mainStack.empty()) { mainStack.pop(); minStack.pop(); // Đồng bộ hai stack } } int top() { // Giả sử top() chỉ gọi khi stack không rỗng return mainStack.top(); } int getMin() { // Giả sử getMin() chỉ gọi khi stack không rỗng return minStack.top(); } bool empty() { return mainStack.empty(); }
};

Python:

class MinStack: def __init__(self): self.mainStack = [] # Khởi tạo minStack với giá trị vô cùng lớn self.minStack = [float('inf')] # Hoặc dùng math.inf def push(self, val: int) -> None: self.mainStack.append(val) # Luôn thêm min mới vào minStack self.minStack.append(min(val, self.minStack[-1])) def pop(self) -> None: if self.mainStack: self.mainStack.pop() self.minStack.pop() # Đồng bộ def top(self) -> int: # Giả sử top() chỉ gọi khi stack không rỗng return self.mainStack[-1] def getMin(self) -> int: # Giả sử getMin() chỉ gọi khi stack không rỗng return self.minStack[-1] def empty(self) -> bool: return not self.mainStack

4.2 MinStack (Dùng Cặp Giá trị - Min)

C++:

class MinStackPair
{
private: // Stack lưu cặp {giá trị, min_tại_thời_điểm_đó} stack<pair<int, int>> st; public: MinStackPair() {} void push(int val) { int currentMin; if (st.empty()) { currentMin = val; } else { // Min mới là min của val và min của phần tử đỉnh trước đó currentMin = min(val, st.top().second); } st.push({val, currentMin}); } void pop() { if (!st.empty()) { st.pop(); } } int top() { // Giả sử top() chỉ gọi khi stack không rỗng return st.top().first; } int getMin() { // Giả sử getMin() chỉ gọi khi stack không rỗng return st.top().second; } bool empty() { return st.empty(); }
};

Python:

class MinStackPair: def __init__(self): # Stack lưu list hoặc tuple [giá_trị, min_tại_thời_điểm_đó] self.stack = [] def push(self, val: int) -> None: current_min = val if self.stack: # Min mới là min của val và min của phần tử đỉnh trước đó current_min = min(val, self.stack[-1][1]) self.stack.append([val, current_min]) def pop(self) -> None: if self.stack: self.stack.pop() def top(self) -> int: # Giả sử top() chỉ gọi khi stack không rỗng # Trả về giá trị thực if self.stack: return self.stack[-1][0] return -1 # Hoặc raise exception def getMin(self) -> int: # Giả sử getMin() chỉ gọi khi stack không rỗng if self.stack: return self.stack[-1][1] return -1 # Hoặc raise exception def empty(self) -> bool: return not self.stack

4.3 MinQueue (Dùng Hai MinStack)

(Sử dụng lớp MinStackPair ở trên) C++:

class MinQueueTwoStacks
{
public: MinStackPair s1, s2; // s1 cho enqueue, s2 cho dequeue void enqueue(int val) { s1.push(val); } void _transfer() { // Chuyển từ s1 sang s2 nếu s2 rỗng while (!s1.empty()) { // Lưu ý: push của MinStackPair tự động xử lý min s2.push(s1.top()); s1.pop(); } } int dequeue() { if (s2.empty()) { _transfer(); } if (s2.empty()) { // Nếu vẫn rỗng sau khi chuyển (tức là queue ban đầu rỗng) cerr << "Queue is empty!" << endl; return -1; // Hoặc throw exception } int front_val = s2.top(); // Lấy giá trị thực s2.pop(); return front_val; } int front() // Thêm hàm front nếu cần { if (s2.empty()) { _transfer(); } if (s2.empty()) { cerr << "Queue is empty!" << endl; return -1; // Hoặc throw exception } return s2.top(); // Trả về giá trị thực của phần tử đầu } int getMin() { int min1 = s1.empty() ? INT_MAX : s1.getMin(); int min2 = s2.empty() ? INT_MAX : s2.getMin(); if (min1 == INT_MAX && min2 == INT_MAX) { cerr << "Queue is empty!" << endl; return -1; // Hoặc throw exception, hoặc trả về INT_MAX } return min(min1, min2); } bool empty() { return s1.empty() && s2.empty(); }
};

Python:

class MinQueueTwoStacks: def __init__(self): self.s1 = MinStackPair() # Stack cho enqueue self.s2 = MinStackPair() # Stack cho dequeue def enqueue(self, val: int) -> None: self.s1.push(val) def _transfer(self) -> None: # Hàm nội bộ để chuyển từ s1 sang s2 while not self.s1.empty(): self.s2.push(self.s1.top()) # Lấy giá trị thực từ top của MinStackPair self.s1.pop() def dequeue(self) -> int: if self.s2.empty(): self._transfer() if self.s2.empty(): # Queue thực sự rỗng print("Error: Queue is empty!") return -1 # Hoặc raise exception front_val = self.s2.top() # Lấy giá trị thực self.s2.pop() return front_val def front(self) -> int: # Thêm hàm front nếu cần if self.s2.empty(): self._transfer() if self.s2.empty(): print("Error: Queue is empty!") return -1 # Hoặc raise exception return self.s2.top() # Trả về giá trị thực def getMin(self) -> int: min1 = self.s1.getMin() if not self.s1.empty() else float('inf') min2 = self.s2.getMin() if not self.s2.empty() else float('inf') result = min(min1, min2) if result == float('inf'): print("Error: Queue is empty!") return -1 # Hoặc raise exception return result def empty(self) -> bool: return self.s1.empty() and self.s2.empty()

4.4 (Dùng Deque Đơn điệu với Chỉ số)

C++:

class MinQueueDeque
{
private: // Deque lưu cặp {giá trị, chỉ số_thêm_vào} deque<pair<int, int>> dq; int cntAdded; // Đếm số lượng đã enqueue int cntRemoved; // Đếm số lượng đã dequeue // Thêm queue phụ để lấy front() nếu cần deque<int> frontQueue; public: MinQueueDeque() : cntAdded(0), cntRemoved(0) {} void enqueue(int val) { // Loại bỏ các phần tử lớn hơn hoặc bằng ở cuối deque while (!dq.empty() && dq.back().first >= val) { dq.pop_back(); } // Thêm phần tử mới và chỉ số của nó dq.push_back({val, cntAdded}); ++cntAdded; // Thêm vào queue phụ để lấy front frontQueue.push_back(val); } void dequeue() { if (empty()) { cerr << "Queue is empty!" << endl; return; } // Chỉ pop khỏi deque chính nếu phần tử đầu deque // khớp với chỉ số của phần tử cần loại bỏ if (!dq.empty() && dq.front().second == cntRemoved) { dq.pop_front(); } // Luôn tăng cntRemoved để đánh dấu một phần tử đã bị loại bỏ (khỏi queue logic) ++cntRemoved; // Loại bỏ khỏi queue phụ frontQueue.pop_front(); } int front() { // Bây giờ có thể lấy front if (empty()) { cerr << "Queue is empty!" << endl; return -1; // Hoặc throw exception } return frontQueue.front(); } int getMin() { if (dq.empty()) { // Kiểm tra deque chính cho min cerr << "Cannot get min from empty queue!" << endl; return -1; // Hoặc trả về INT_MAX, hoặc throw exception } // Phần tử nhỏ nhất luôn ở đầu deque chính return dq.front().first; } bool empty() { // Queue logic rỗng khi số lượng thêm vào bằng số lượng loại bỏ return cntAdded == cntRemoved; }
};

Python:

class MinQueueDeque: def __init__(self): # Deque chính lưu tuple (giá_trị, chỉ_số_thêm_vào) self.dq = deque() self.cnt_added = 0 # Đếm số lượng đã enqueue self.cnt_removed = 0 # Đếm số lượng đã dequeue # Queue phụ để lấy front self.front_queue = deque() def enqueue(self, val: int) -> None: # Loại bỏ các phần tử lớn hơn hoặc bằng ở cuối deque chính while self.dq and self.dq[-1][0] >= val: self.dq.pop() # Thêm phần tử mới và chỉ số của nó vào deque chính self.dq.append((val, self.cnt_added)) self.cnt_added += 1 # Thêm vào queue phụ self.front_queue.append(val) def dequeue(self) -> None: if self.empty(): print("Error: Queue is empty!") return # Chỉ pop khỏi deque chính nếu phần tử đầu deque # khớp với chỉ số của phần tử cần loại bỏ if self.dq and self.dq[0][1] == self.cnt_removed: self.dq.popleft() # Luôn tăng cnt_removed self.cnt_removed += 1 # Loại bỏ khỏi queue phụ self.front_queue.popleft() def front(self) -> int: # Bây giờ có thể lấy front if self.empty(): print("Error: Queue is empty!") return -1 # Hoặc raise exception return self.front_queue[0] def getMin(self) -> int: if not self.dq: # Kiểm tra deque chính cho min print("Cannot get min from empty queue!") return -1 # Hoặc math.inf hoặc raise exception # Phần tử nhỏ nhất luôn ở đầu deque chính return self.dq[0][0] def empty(self) -> bool: # Queue logic rỗng khi số lượng thêm vào bằng số lượng loại bỏ return self.cnt_added == self.cnt_removed

5. Lời Kết: Tiến Lên và Tối Thiểu Hóa!

Vậy là anh em mình đã cùng nhau khám phá thế giới màu nhiệm của MinStack và MinQueue. Chúng không chỉ là bản độ của stack/queue, mà còn là minh chứng cho sự sáng tạo trong thiết kế cấu trúc dữ liệu, giúp nâng cấp đám cơ bản để giải quyết bài toán khó nhằn hơn.

Chúng ta đã thấy cách cài đặt bằng stack phụ, bằng cặp giá trị, hay cả mẹo mã hóa tiết kiệm không gian. Với MinQueue, ta có thể mô phỏng bằng hai MinStack hoặc dùng deque đơn điệu - một kỹ thuật cực mạnh cho bài toán cửa sổ trượt.

Hiểu rõ các cách này, ưu nhược điểm, độ phức tạp (thời gian, không gian, cả trung bình) là bước tiến quan trọng trên con đường bá chủ thuật toán. Đừng ngại cày cuốc trên LeetCode, GeeksforGeeks, Codeforces... để thực sự làm chủ chúng. Thử sức với bài Min Stack (LeetCode 155), Stock Span, Sliding Window Maximum xem sao!

Vậy nên, lần tới khi anh em cần stack hay queue mà không "quên" mất thằng nhỏ nhất, anh em biết phải làm gì rồi đấy! Giờ thì, căng buồm ra khơi và tối thiểu hóa thời gian chạy (và cả bug nữa nhé!).

À mà, anh em có biết tại sao MinStack lại luôn bình tĩnh khi gặp lỗi không?

... Vì nó luôn biết điểm thấp nhất của mình ở đâu! 😉

Chúc anh em code vui!