Nghiên cứu về các thao tác cơ bản của cấu trúc dữ liệu Stack và Queue
Bài viết này tập trung vào việc khám phá và củng cố các phương pháp thao tác thường gặp với hai cấu trúc dữ liệu cơ bản: Stack (ngăn xếp) và Queue (hàng đợi). Chúng ta sẽ cùng nhau phân tích một số bài toán điển hình để hiểu rõ hơn cách áp dụng chúng trong thực tế.
Stack (Ngăn xếp)
Stack là một cấu trúc dữ liệu tuân thủ nguyên tắc "Vào sau, ra trước" (LIFO - Last In, First Out). Tức là phần tử được thêm vào cuối cùng sẽ là phần tử đầu tiên được lấy ra. Một ứng dụng tiêu biểu của stack là xử lý thứ tự các phép toán trong biểu thức.
Bài toán ví dụ 1: Kiểm tra chuỗi thao tác Stack hợp lệ (P4387)
Mô tả bài toán
Cho một chuỗi các số được đưa vào stack (chuỗi nhập) và một chuỗi các số được lấy ra khỏi stack (chuỗi xuất). Cần xác định xem chuỗi xuất có thể được tạo thành từ chuỗi nhập đã cho theo nguyên tắc của stack hay không.
Phân tích
Để giải quyết bài toán này, chúng ta có thể mô phỏng trực tiếp quá trình hoạt động của stack. Ta duyệt qua chuỗi nhập, lần lượt đẩy các phần tử vào stack. Sau mỗi lần đẩy, kiểm tra xem phần tử trên cùng của stack có trùng khớp với phần tử tiếp theo cần được lấy ra theo chuỗi xuất hay không. Nếu có, ta liên tục lấy phần tử ra khỏi stack cho đến khi stack rỗng hoặc phần tử trên cùng không còn khớp. Quá trình này được thực hiện một cách tham lam: luôn cố gắng lấy ra khỏi stack ngay khi có thể.
Sau khi duyệt hết chuỗi nhập và thực hiện các thao tác đẩy/lấy tương ứng, nếu stack hoàn toàn rỗng và tất cả các phần tử trong chuỗi xuất đã được xử lý, chuỗi xuất là hợp lệ. Ngược lại, nếu stack vẫn còn phần tử, hoặc chuỗi xuất chưa được xử lý hết, thì chuỗi xuất là không hợp lệ.
Mã nguồn minh họa
#include <iostream>
#include <vector>
#include <stack>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
int test_cases;
std::cin >> test_cases;
while (test_cases--) {
int n_elements;
std::cin >> n_elements;
std::vector<int> input_sequence(n_elements);
std::vector<int> output_sequence(n_elements);
for (int i = 0; i < n_elements; ++i) {
std::cin >> input_sequence[i];
}
for (int i = 0; i < n_elements; ++i) {
std::cin >> output_sequence[i];
}
std::stack<int> processing_stack;
int current_output_idx = 0;
for (int i = 0; i < n_elements; ++i) {
processing_stack.push(input_sequence[i]);
while (!processing_stack.empty() && current_output_idx < n_elements && processing_stack.top() == output_sequence[current_output_idx]) {
processing_stack.pop();
current_output_idx++;
}
}
if (processing_stack.empty() && current_output_idx == n_elements) {
std::cout << "Yes\n";
} else {
std::cout << "No\n";
}
// Clear stack for next test case (though usually stack is local for competitive programming)
// while (!processing_stack.empty()) {
// processing_stack.pop();
// }
}
return 0;
}
Bài toán ví dụ 2: Cân bằng chuỗi dấu ngoặc (P3056)
Mô tả bài toán
Cho một chuỗi dấu ngoặc có độ dài chẵn. Cần tìm số lượng thao tác thay đổi dấu ngoặc tối thiểu để chuỗi trở thành cân bằng. (Lưu ý: đây là bài toán thay đổi dấu ngoặc, không phải kiểm tra tính hợp lệ).
Phân tích
Ý tưởng chính là phân loại các dấu ngoặc. Đầu tiên, chúng ta sử dụng một stack để tìm và loại bỏ tất cả các cặp dấu ngoặc hợp lệ (ví dụ: "()"). Các dấu ngoặc mở '(' sẽ được đẩy vào stack. Khi gặp một dấu ngoặc đóng ')', nếu stack không rỗng và trên cùng là một dấu ngoặc mở, ta thực hiện pop để loại bỏ cặp hợp lệ đó. Ngược lại, nếu stack rỗng, dấu ngoặc đóng này là một dấu ngoặc đóng không có dấu ngoặc mở tương ứng.
Sau bước này, stack sẽ chỉ chứa các dấu ngoặc mở không có dấu ngoặc đóng tương ứng (gọi là left_remaining), và chúng ta cũng có một số lượng các dấu ngoặc đóng không có dấu ngoặc mở tương ứng (gọi là right_unmatched).
Tổng số dấu ngoặc còn lại (left_remaining + right_unmatched) phải là số chẵn, vì độ dài chuỗi ban đầu là chẵn và các cặp đã ghép cũng là chẵn. Do đó, left_remaining và right_unmatched phải luôn cùng tính chẵn lẻ (cả hai cùng chẵn hoặc cả hai cùng lẻ).
Để cân bằng các dấu ngoặc còn lại, ta cần thực hiện các thay đổi.
- Mỗi hai dấu ngoặc mở `((` có thể được cân bằng thành `()` bằng 1 thao tác thay đổi. Do đó, `left_remaining / 2` là số thao tác cần thiết cho các dấu mở dư.
- Tương tự, mỗi hai dấu ngoặc đóng `))` có thể được cân bằng thành `()` bằng 1 thao tác thay đổi. Do đó, `right_unmatched / 2` là số thao tác cần thiết cho các dấu đóng dư.
Nếu cả left_remaining và right_unmatched đều là số lẻ, điều đó có nghĩa là sau khi ghép các cặp `((` và `))` có thể, chúng ta còn lại một dấu ngoặc mở đơn độc và một dấu ngoặc đóng đơn độc. Ví dụ: `...(` và `)...`. Khi ghép chúng lại, chúng sẽ tạo thành một cấu trúc `)(`. Để biến `)(` thành một cặp cân bằng `()` (ví dụ: đổi dấu đóng thành mở và dấu mở thành đóng), chúng ta cần thêm 2 thao tác nữa. Vì left_remaining và right_unmatched luôn cùng tính chẵn lẻ, việc kiểm tra `left_remaining % 2 != 0` là đủ để biết cả hai đều lẻ.
Mã nguồn minh họa
#include <iostream>
#include <stack>
#include <string>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::stack<char> parentheses_stack;
int unmatched_closing_count = 0; // Counts ')' that don't find a matching '('
char current_char;
while (std::cin >> current_char) {
if (current_char == '(') {
parentheses_stack.push(current_char);
} else { // current_char == ')'
if (!parentheses_stack.empty()) {
parentheses_stack.pop(); // Found a match for an opening parenthesis
} else {
unmatched_closing_count++; // This ')' has no matching '('
}
}
}
int remaining_opening_count = parentheses_stack.size(); // '(' without a matching ')'
int total_modifications = (remaining_opening_count / 2) + (unmatched_closing_count / 2);
// If both remaining_opening_count and unmatched_closing_count are odd,
// they form a ')(', which needs 2 extra modifications.
// Since they always have the same parity, checking one is sufficient.
if (remaining_opening_count % 2 != 0) { // This implies unmatched_closing_count is also odd
total_modifications += 2;
}
std::cout << total_modifications << std::endl;
return 0;
}
Bài toán ví dụ 3: Stack đơn điệu (Monotonic Stack) (P2866)
Bài toán này là một ví dụ kinh điển cho cấu trúc dữ liệu Stack đơn điệu (Monotonic Stack). Monotonic Stack là một loại stack mà các phần tử của nó luôn được duy trì theo một thứ tự tăng dần hoặc giảm dần. Nó thường được sử dụng để tìm phần tử lớn hơn/nhỏ hơn đầu tiên bên trái/bên phải của mỗi phần tử trong một mảng, hoặc để giải quyết các bài toán liên quan đến vùng con lớn nhất/nhỏ nhất. Chi tiết về Monotonic Stack có thể được tìm hiểu sâu hơn trong các tài liệu chuyên biệt về thuật toán.
Queue (Hàng đợi)
Queue là một cấu trúc dữ liệu tuân thủ nguyên tắc "Vào trước, ra trước" (FIFO - First In, First Out). Phần tử được thêm vào đầu tiên sẽ là phần tử đầu tiên được lấy ra. Hàng đợi thường được dùng để quản lý các tác vụ theo thứ tự đến.
Bài toán ví dụ 1: Thao tác Queue hai đầu (P2952)
Mô tả bài toán
Quản lý một hàng đợi mà các phần tử (ví dụ: những con bò) có thể được thêm vào hoặc loại bỏ từ cả hai đầu (trước hoặc sau). Thực hiện một chuỗi các thao tác và in ra các phần tử còn lại trong hàng đợi theo đúng thứ tự từ trước ra sau.
Phân tích
Với yêu cầu thao tác từ cả hai đầu của hàng đợi, cấu trúc dữ liệu std::deque (double-ended queue, hàng đợi hai đầu) trong C++ Standard Template Library (STL) là lựa chọn phù hợp nhất. deque hỗ trợ các thao tác thêm/bớt phần tử ở cả đầu và cuối với độ phức tạp thời gian O(1).
Mã nguồn minh họa
#include <iostream>
#include <deque>
#include <string> // Not strictly needed for char, but good practice for full string ops
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
int num_operations;
std::cin >> num_operations;
std::deque<int> animal_queue;
int next_animal_id = 1;
for (int op_count = 0; op_count < num_operations; ++op_count) {
char operation_type;
std::cin >> operation_type;
if (operation_type == 'A') { // Add operation
char add_direction;
std::cin >> add_direction;
if (add_direction == 'L') { // Add to left (front)
animal_queue.push_front(next_animal_id++);
} else { // Add to right (back)
animal_queue.push_back(next_animal_id++);
}
} else if (operation_type == 'D') { // Delete operation
char delete_direction;
int num_to_delete;
std::cin >> delete_direction >> num_to_delete;
if (delete_direction == 'L') { // Delete from left (front)
for (int i = 0; i < num_to_delete; ++i) {
if (!animal_queue.empty()) { // Ensure queue is not empty before popping
animal_queue.pop_front();
} else {
break; // Stop if queue becomes empty
}
}
} else { // Delete from right (back)
for (int i = 0; i < num_to_delete; ++i) {
if (!animal_queue.empty()) { // Ensure queue is not empty before popping
animal_queue.pop_back();
} else {
break; // Stop if queue becomes empty
}
}
}
}
}
while (!animal_queue.empty()) {
std::cout << animal_queue.front() << "\n";
animal_queue.pop_front();
}
return 0;
}
Bài toán ví dụ 2: Cửa sổ trượt (Sliding Window) (P3662)
Mô tả bài toán
Có N đèn tín hiệu, trong đó B đèn bị hỏng. Cần sửa tối thiểu bao nhiêu đèn để có được K đèn tín hiệu liên tiếp hoạt động tốt.
Phân tích
Bài toán này có thể được giải quyết hiệu quả bằng kỹ thuật "cửa sổ trượt" (Sliding Window). Đầu tiên, ta biểu diễn trạng thái của các đèn tín hiệu: 1 nếu đèn hỏng (cần sửa) và 0 nếu đèn hoạt động tốt. Mục tiêu là tìm một đoạn con liên tiếp có độ dài K sao cho tổng số đèn hỏng trong đoạn đó là nhỏ nhất. Tổng này chính là số đèn cần sửa trong đoạn đó.
Chúng ta khởi tạo một "cửa sổ" có độ dài K, bắt đầu từ vị trí 1 đến K. Tính tổng số đèn hỏng trong cửa sổ này. Đây là số lượng sửa chữa ban đầu. Sau đó, ta trượt cửa sổ sang phải từng bước một: mỗi khi cửa sổ dịch chuyển, ta loại bỏ phần tử ở đầu cửa sổ cũ và thêm phần tử mới ở cuối cửa sổ mới. Đồng thời, cập nhật tổng số đèn hỏng trong cửa sổ hiện tại và so sánh với giá trị tối thiểu đã tìm được.
Cụ thể hơn:
- Tạo một mảng đánh dấu các đèn bị hỏng (
is_broken[i] = 1nếu đènihỏng,0nếu không). - Tính tổng số đèn hỏng trong cửa sổ ban đầu từ
1đếnconsecutive_needed. Lưu giá trị này vào biếnmin_repairsvàcurrent_repairs. - Trượt cửa sổ từ
left_ptr = 1đếntotal_lights - consecutive_needed. Trong mỗi bước trượt:- Xác định
right_ptr = left_ptr + consecutive_needed(phần tử mới thêm vào cửa sổ). - Giảm
current_repairsđiis_broken[left_ptr](loại bỏ đèn ở đầu cũ). - Tăng
current_repairsthêmis_broken[right_ptr](thêm đèn ở cuối mới). - Cập nhật
min_repairs = std::min(min_repairs, current_repairs).
- Xác định
Mã nguồn minh họa
#include <iostream>
#include <vector>
#include <algorithm> // For std::min
const int LARGE_INT = 1e9 + 7; // A sufficiently large integer value for initialization
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
int total_lights, consecutive_needed, num_broken_lights;
std::cin >> total_lights >> consecutive_needed >> num_broken_lights;
std::vector<int> is_broken(total_lights + 1, 0); // Using 1-indexed lights
for (int i = 0; i < num_broken_lights; ++i) {
int broken_pos;
std::cin >> broken_pos;
is_broken[broken_pos] = 1; // Mark as broken (needs repair)
}
int current_repairs = 0;
// Calculate initial window sum (from 1 to consecutive_needed)
for (int i = 1; i <= consecutive_needed; ++i) {
current_repairs += is_broken[i];
}
int min_repairs = current_repairs; // Initialize min_repairs with the first window's sum
// Slide the window
// `left_ptr` is the start of the window
for (int left_ptr = 1; left_ptr <= total_lights - consecutive_needed; ++left_ptr) {
int right_ptr = left_ptr + consecutive_needed; // The element entering the window
// Remove element leaving the window from the left
current_repairs -= is_broken[left_ptr];
// Add element entering the window from the right
current_repairs += is_broken[right_ptr];
min_repairs = std::min(min_repairs, current_repairs);
}
std::cout << min_repairs << std::endl;
return 0;
}