Khóa học CTDL và GT

Bài 6.5. Bài tập tổng hợp về Cấu trúc dữ liệu cơ bản

Chào mừng trở lại với hành trình khám phá thế giới Cấu trúc dữ liệu và Giải thuật!

Chúng ta đã cùng nhau đi qua lý thuyết về các loại cấu trúc dữ liệu cơ bản như mảng, danh sách liên kết, stack, queue, và hiểu được nguyên lý hoạt động cũng như ưu nhược điểm của từng loại. Tuy nhiên, lý thuyết chỉ là bước khởi đầu. Để thực sự nắm vững và có thể vận dụng linh hoạt các cấu trúc dữ liệu này vào việc giải quyết các bài toán thực tế, việc thực hành là vô cùng quan trọng.

Bài viết này được thiết kế như một buổi thực hành tổng hợp. Chúng ta sẽ cùng nhau giải quyết một loạt các bài tập, từ đơn giản đến phức tạp hơn một chút, sử dụng các cấu trúc dữ liệu cơ bản đã học. Mục tiêu là để bạn đọc củng cố kiến thức, làm quen với cách triển khai các cấu trúc này trong ngôn ngữ C++, và quan trọng nhất là phát triển khả năng suy luận và chọn lựa cấu trúc dữ liệu phù hợp cho từng vấn đề cụ thể.

Hãy cùng đi sâu vào các bài tập!

Bài tập 1: Phân tích dữ liệu cơ bản trên Mảng

Mảng là cấu trúc dữ liệu đơn giản và phổ biến nhất. Mảng lưu trữ các phần tử cùng kiểu dữ liệu tại các vị trí bộ nhớ liên tiếp, cho phép truy cập ngẫu nhiên (truy cập bất kỳ phần tử nào) rất nhanh bằng chỉ số. Nhược điểm chính là kích thước cố định sau khi được khai báo (hoặc thay đổi kích thước tốn kém nếu sử dụng các cấu trúc động như std::vector).

Trong bài tập này, chúng ta sẽ thực hiện các thao tác cơ bản trên một mảng số nguyên: tính tổng, tìm phần tử lớn nhất và nhỏ nhất.

Mô tả Bài tập:

Viết một hàm C++ nhận vào một mảng (hoặc std::vector) các số nguyên. Hàm này sẽ tính tổng của tất cả các phần tử, tìm giá trị nhỏ nhất và giá trị lớn nhất trong mảng, sau đó in kết quả ra màn hình.

Code C++ Minh họa:

Chúng ta sẽ sử dụng std::vector trong C++ vì tính linh hoạt và các hàm tiện ích sẵn có, mô phỏng một mảng động.

#include <iostream>
#include <vector>      // De su dung std::vector
#include <numeric>     // De su dung std::accumulate (tinh tong)
#include <algorithm>   // De su dung std::min_element, std::max_element (tim min/max)
#include <limits>      // De su dung numeric_limits

void analyzeArray(const std::vector<int>& arr) {
    // Xu ly truong hop mang rong
    if (arr.empty()) {
        std::cout << "Mang rong, khong co du lieu de phan tich." << std::endl;
        return;
    }

    // 1. Tinh tong cac phan tu
    // std::accumulate(bat_dau, ket_thuc, gia_tri_khoi_tao, phep_toan)
    // Dung 0LL (long long) de tranh tran so neu tong lon
    long long sum = std::accumulate(arr.begin(), arr.end(), 0LL);

    // 2. Tim phan tu nho nhat va lon nhat
    // std::min_element va std::max_element tra ve iterator den phan tu
    auto min_it = std::min_element(arr.begin(), arr.end());
    auto max_it = std::max_element(arr.begin(), arr.end());

    int min_val = *min_it; // Lay gia tri tu iterator
    int max_val = *max_it; // Lay gia tri tu iterator

    // In ket qua
    std::cout << "Mang: ";
    for (int x : arr) { // Duyet qua cac phan tu theo kieu range-based for loop
        std::cout << x << " ";
    }
    std::cout << std::endl;

    std::cout << "Tong cac phan tu: " << sum << std::endl;
    std::cout << "Phan tu nho nhat: " << min_val << std::endl;
    std::cout << "Phan tu lon nhat: " << max_val << std::endl;
}

int main() {
    // Test case 1
    std::vector<int> my_array = {10, 5, 20, 15, 25, 8, 30};
    analyzeArray(my_array);
    std::cout << "---" << std::endl;

    // Test case 2 voi so am
    std::vector<int> another_array = {-5, -1, -10, 0, 50, -2};
    analyzeArray(another_array);
    std::cout << "---" << std::endl;

    // Test case rong
    std::vector<int> empty_array;
    analyzeArray(empty_array);
    std::cout << "---" << std::endl;

    // Test case 1 phan tu
     std::vector<int> single_element_array = {99};
    analyzeArray(single_element_array);
    std::cout << "---" << std::endl;


    return 0;
}

Giải thích Code:

1. Includes: Chúng ta bao gồm các thư viện cần thiết: <iostream> cho nhập xuất, <vector> để sử dụng std::vector, <numeric> cho hàm std::accumulate, <algorithm> cho std::min_element và std::max_element, và <limits> (mặc dù không dùng trực tiếp trong hàm chính, nó hữu ích nếu bạn tự triển khai min/max bằng vòng lặp, khởi tạo giá trị ban đầu).
2. analyzeArray function:
   • Hàm nhận vào một const std::vector<int>& arr. Sử dụng const& giúp tránh sao chép dữ liệu lớn và đảm bảo hàm không thay đổi mảng gốc.
   • Kiểm tra mảng rỗng (arr.empty()) là quan trọng để tránh lỗi khi thao tác trên mảng không có phần tử nào.
   • std::accumulate(arr.begin(), arr.end(), 0LL): Hàm này tính tổng các phần tử trong phạm vi từ arr.begin() đến arr.end(). 0LL là giá trị khởi tạo (0) với kiểu long long để đảm bảo tổng có thể chứa các giá trị lớn hơn phạm vi của int.
   • std::min_element(arr.begin(), arr.end()) và std::max_element(arr.begin(), arr.end()): Các hàm này trả về iterator trỏ đến phần tử nhỏ nhất và lớn nhất trong phạm vi.
   • *min_it và *max_it: Dùng toán tử * để lấy giá trị thực sự mà iterator đang trỏ tới.
   • Vòng lặp for (int x : arr) là cách duyệt mảng std::vector hiện đại trong C++, giúp code gọn gàng hơn.
3. main function: Tạo các std::vector mẫu và gọi hàm analyzeArray để kiểm tra các trường hợp khác nhau, bao gồm cả mảng rỗng và mảng chỉ có một phần tử.

Bài tập này giúp bạn ôn lại cách làm việc với mảng (hoặc vector) và sử dụng các hàm tiện ích sẵn có trong STL (Standard Template Library) của C++ để xử lý dữ liệu.

Bài tập 2: Xây dựng và Duyệt Danh sách Liên kết Đơn

Danh sách liên kết là một cấu trúc dữ liệu động, bao gồm các node. Mỗi node chứa dữ liệu và một con trỏ (hoặc liên kết) đến node tiếp theo trong danh sách. Ưu điểm là chèn và xóa phần tử hiệu quả (O(1)) nếu đã có con trỏ đến vị trí cần thao tác. Nhược điểm là truy cập phần tử theo chỉ số tốn kém (O(n)) vì phải duyệt từ đầu danh sách.

Trong bài tập này, chúng ta sẽ tự tay xây dựng cấu trúc của một node và một danh sách liên kết đơn, sau đó viết hàm để thêm phần tử vào cuối danh sách và duyệt toàn bộ danh sách để in ra các phần tử.

Mô tả Bài tập:

Implement cấu trúc Node và lớp SinglyLinkedList cho danh sách liên kết đơn trong C++. Cung cấp các hàm:

• Constructor để khởi tạo danh sách rỗng.
• Destructor để giải phóng bộ nhớ đã cấp phát cho các node.
• Hàm append(int val) để thêm một node mới với giá trị val vào cuối danh sách.
• Hàm printList() để duyệt từ đầu đến cuối danh sách và in giá trị của từng node.

Code C++ Minh họa:

#include <iostream>

// Dinh nghia cau truc (struct) cho mot Node trong danh sach lien ket don
struct Node {
    int data;     // Du lieu cua node
    Node* next;   // Con tro den node tiep theo

    // Constructor giup khoi tao Node nhanh hon
    Node(int val) : data(val), next(nullptr) {}
};

// Dinh nghia lop cho Danh sach lien ket don
class SinglyLinkedList {
private:
    Node* head; // Con tro den phan tu dau tien (head) cua danh sach

public:
    // Constructor: Khoi tao danh sach rong, head tro den nullptr
    SinglyLinkedList() : head(nullptr) {}

    // Destructor: Ham quan trong de giai phong tat ca bo nho da cap phat dong cho cac node
    ~SinglyLinkedList() {
        Node* current = head;
        Node* next_node;
        // Duyet qua tung node va xoa
        while (current != nullptr) {
            next_node = current->next; // Luu con tro den node tiep theo truoc khi xoa node hien tai
            delete current;          // Giai phong bo nho cua node hien tai
            current = next_node;     // Di chuyen den node tiep theo
        }
        head = nullptr; // Dam bao head tro ve nullptr sau khi tat ca cac node da bi xoa
        std::cout << "Danh sach da bi huy (cac node da duoc giai phong bo nho)." << std::endl;
    }

    // Them mot node moi vao cuoi danh sach
    void append(int val) {
        Node* new_node = new Node(val); // 1. Tao mot node moi tren heap (bo nho dong)

        // 2. Kiem tra neu danh sach dang rong (head la nullptr)
        if (head == nullptr) {
            head = new_node; // Node moi tro thanh head
        } else {
            // 3. Neu danh sach khong rong, tim den node cuoi cung
            Node* current = head;
            while (current->next != nullptr) { // Duyet cho den khi con tro next cua current la nullptr
                current = current->next;     // Di chuyen den node tiep theo
            }
            // 4. Node cuoi cung da duoc tim thay (current), gan con tro next cua no den node moi
            current->next = new_node;
        }
        // std::cout << "Da them " << val << " vao cuoi danh sach." << std::endl; // Co the bo dong nay de output gon hon
    }

    // Duyet qua danh sach tu dau den cuoi va in gia tri cac node
    void printList() const {
        Node* current = head; // Bat dau tu head
        if (current == nullptr) {
            std::cout << "Danh sach rong." << std::endl;
            return;
        }
        std::cout << "Danh sach: ";
        while (current != nullptr) { // Duyet cho den khi het danh sach (gap nullptr)
            std::cout << current->data << " -> "; // In du lieu cua node hien tai
            current = current->next;     // Di chuyen den node tiep theo
        }
        std::cout << "nullptr" << std::endl; // Ket thuc danh sach bang nullptr de hien thi ro
    }
};

int main() {
    // Tao mot doi tuong danh sach lien ket
    SinglyLinkedList list;

    // Them cac phan tu
    list.append(10);
    list.append(20);
    list.append(30);

    // In danh sach
    list.printList(); // Du kien: Danh sach: 10 -> 20 -> 30 -> nullptr

    // Them them phan tu
    list.append(5);
    list.append(25);

    // In danh sach lai
    list.printList(); // Du kien: Danh sach: 10 -> 20 -> 30 -> 5 -> 25 -> nullptr

    // Tao mot danh sach khac, test danh sach rong
    SinglyLinkedList empty_list;
    empty_list.printList(); // Du kien: Danh sach rong.

    // Khi main ket thuc, destructor cua ca 'list' va 'empty_list' se duoc goi tu dong
    return 0;
}

Giải thích Code:

1. struct Node: Định nghĩa cấu trúc của một node. Nó chứa một trường data (ở đây là int) và một con trỏ next kiểu Node*, trỏ đến node kế tiếp. Constructor Node(int val) là cách tiện lợi để tạo một node mới và khởi tạo giá trị cho data, đồng thời đặt next ban đầu là nullptr.
2. class SinglyLinkedList:
   • Chứa một con trỏ head (Node* head), đây là điểm truy cập duy nhất vào danh sách. Ban đầu, head là nullptr (danh sách rỗng).
   • Constructor SinglyLinkedList(): Khởi tạo head bằng nullptr.
   • Destructor ~SinglyLinkedList(): Rất quan trọng khi làm việc với bộ nhớ động. Nó duyệt qua tất cả các node trong danh sách và dùng toán tử delete để giải phóng bộ nhớ mà mỗi node chiếm giữ. Nếu không có destructor này, sẽ xảy ra memory leak (rò rỉ bộ nhớ).
   • append(int val): Thêm một node mới vào cuối.
     • Tạo new_node bằng new Node(val). new cấp phát bộ nhớ cho node trên heap và trả về con trỏ đến nó.
     • Nếu danh sách rỗng (head == nullptr), new_node trở thành head.
     • Nếu không rỗng, cần duyệt từ head đến node cuối cùng. Node cuối cùng là node có con trỏ next bằng nullptr.
     • Sau khi tìm được node cuối cùng (gọi là current), gán current->next = new_node; để liên kết node mới vào cuối danh sách.
   • printList(): Duyệt từ head. Bắt đầu với current = head. Trong vòng lặp while (current != nullptr), in dữ liệu của current, sau đó cập nhật current = current->next; để di chuyển đến node kế tiếp. Dừng lại khi current trở thành nullptr (đã đi qua node cuối cùng).
3. main function: Tạo đối tượng list, gọi append để thêm các số, và gọi printList để xem kết quả. Cũng thêm một test case cho danh sách rỗng. Chú ý rằng destructor được gọi tự động khi đối tượng list và empty_list ra khỏi phạm vi (khi main kết thúc).

Bài tập này giúp bạn hiểu rõ cơ chế hoạt động của danh sách liên kết thông qua việc tự cài đặt, đặc biệt là việc quản lý con trỏ và giải phóng bộ nhớ.

Bài tập 3: Sử dụng Stack để Đảo ngược Chuỗi

Stack (Ngăn xếp) là một cấu trúc dữ liệu tuân thủ nguyên tắc LIFO (Last-In, First-Out - Vào sau, Ra trước). Các thao tác chính là push (thêm phần tử vào đỉnh), pop (xóa phần tử ở đỉnh), và top hoặc peek (xem phần tử ở đỉnh mà không xóa). Stack thường được dùng trong các bài toán liên quan đến thứ tự ngược, như kiểm tra cân bằng dấu ngoặc, quản lý lời gọi hàm, duyệt đồ thị theo chiều sâu (DFS).

Một ứng dụng kinh điển của Stack là đảo ngược thứ tự các phần tử. Trong bài tập này, chúng ta sẽ sử dụng Stack để đảo ngược một chuỗi ký tự.

Mô tả Bài tập:

Viết một hàm C++ nhận vào một chuỗi (std::string). Sử dụng std::stack<char> để đảo ngược thứ tự các ký tự trong chuỗi đó và trả về chuỗi đã đảo ngược.

Code C++ Minh họa:

STL trong C++ cung cấp sẵn lớp std::stack, giúp việc sử dụng Stack trở nên rất đơn giản.

#include <iostream>
#include <string>
#include <stack>   // Bao gom thu vien cho std::stack

std::string reverseStringUsingStack(const std::string& str) {
    // 1. Tao mot stack de luu tru cac ky tu
    std::stack<char> char_stack;

    // 2. Duyet qua chuoi goc va day (push) tung ky tu vao stack
    // Cac ky tu se duoc them vao stack theo thu tu tu trai sang phai
    for (char c : str) {
        char_stack.push(c);
    }

    // 3. Tao mot chuoi moi de luu ket qua dao nguoc
    std::string reversed_str = "";

    // 4. Lay (pop) tung ky tu ra khoi stack va them vao chuoi moi
    // Do stack theo nguyen tac LIFO, cac ky tu se duoc lay ra theo thu tu nguoc lai voi luc them vao
    while (!char_stack.empty()) { // Lap cho den khi stack rong
        reversed_str += char_stack.top(); // Lay ky tu o dinh stack ma khong xoa
        char_stack.pop();               // Xoa ky tu o dinh stack
    }

    return reversed_str;
}

int main() {
    std::string original_str1 = "Hello Stack Example!";
    std::string reversed_str1 = reverseStringUsingStack(original_str1);
    std::cout << "Chuoi goc: " << original_str1 << std::endl;
    std::cout << "Chuoi dao nguoc: " << reversed_str1 << std::endl; // Du kien: !elpmaxE kcatS olleH

    std::cout << "---" << std::endl;

    std::string original_str2 = "Lap Trinh CTDL & GT";
    std::string reversed_str2 = reverseStringUsingStack(original_str2);
    std::cout << "Chuoi goc: " << original_str2 << std::endl;
    std::cout << "Chuoi dao nguoc: " << reversed_str2 << std::endl;

     std::cout << "---" << std::endl;

    std::string original_str3 = "";
    std::string reversed_str3 = reverseStringUsingStack(original_str3);
    std::cout << "Chuoi goc: '" << original_str3 << "'" << std::endl;
    std::cout << "Chuoi dao nguoc: '" << reversed_str3 << "'" << std::endl; // Du kien: ''

    return 0;
}

Giải thích Code:

1. Include <stack>: Để sử dụng std::stack.
2. reverseStringUsingStack function:
   • Nhận vào chuỗi gốc str (dưới dạng const&).
   • Tạo một std::stack<char> có tên char_stack. Đây là stack sẽ lưu trữ các ký tự.
   • Vòng lặp đầu tiên: Duyệt qua từng ký tự (char c) trong chuỗi str và dùng char_stack.push(c) để đẩy ký tự đó vào đỉnh stack. Ký tự đầu tiên của chuỗi sẽ nằm ở đáy stack, ký tự cuối cùng sẽ nằm ở đỉnh.
   • Tạo một chuỗi rỗng reversed_str.
   • Vòng lặp thứ hai: Sử dụng while (!char_stack.empty()) để lặp cho đến khi stack không còn ký tự nào.
     • Trong mỗi lần lặp, char_stack.top() lấy ký tự ở đỉnh stack (mà không xóa). Đây là ký tự cuối cùng được push vào.
     • Ký tự này được nối vào cuối chuỗi reversed_str.
     • char_stack.pop() xóa ký tự ở đỉnh stack.
   • Vì các ký tự được lấy ra theo thứ tự ngược lại với lúc thêm vào (do LIFO), chuỗi reversed_str cuối cùng sẽ là chuỗi gốc được đảo ngược.
3. main function: Minh họa cách sử dụng hàm với các chuỗi khác nhau, bao gồm cả chuỗi rỗng.

Bài tập này cho thấy cách Stack có thể được sử dụng một cách hiệu quả để đảo ngược thứ tự, một tính chất rất hữu ích trong nhiều thuật toán.

Bài tập 4: Mô phỏng Hàng đợi (Queue)

Queue (Hàng đợi) là cấu trúc dữ liệu tuân thủ nguyên tắc FIFO (First-In, First-Out - Vào trước, Ra trước). Các thao tác chính là push (thêm vào cuối), pop (xóa phần tử ở đầu), front (xem phần tử ở đầu), back (xem phần tử ở cuối), và isEmpty. Queue thường được dùng để mô phỏng các tình huống xếp hàng chờ xử lý, như hàng đợi tác vụ trong hệ điều hành, hàng đợi gói tin mạng, hay duyệt đồ thị theo chiều rộng (BFS).

Trong bài tập này, chúng ta sẽ mô phỏng một hàng đợi đơn giản xử lý các "tác vụ".

Mô tả Bài tập:

Sử dụng std::queue trong C++ để mô phỏng một hàng đợi xử lý các tác vụ (có thể là các số nguyên đại diện cho ID tác vụ). Thêm một vài tác vụ vào hàng đợi, sau đó xử lý chúng theo đúng thứ tự vào trước, ra trước.

Code C++ Minh họa:

STL của C++ cũng cung cấp sẵn lớp std::queue trong thư viện <queue>.

#include <iostream>
#include <queue>   // Bao gom thu vien cho std::queue
#include <string>  // De su dung std::string

void simulateTaskQueue() {
    // 1. Tao mot queue de luu tru cac ID cong viec (int)
    std::queue<int> task_queue;

    std::cout << "Them cong viec vao hang doi (enqueue)..." << std::endl;

    // 2. Them cac cong viec (enqueue) vao cuoi hang doi
    task_queue.push(101); // Cong viec 101 vao truoc nhat
    std::cout << " -> Da them cong viec ID: 101" << std::endl;
    task_queue.push(102);
    std::cout << " -> Da them cong viec ID: 102" << std::endl;
    task_queue.push(103); // Cong viec 103 vao sau cung trong dot dau tien
    std::cout << " -> Da them cong viec ID: 103" << std::endl;

    std::cout << "\nXu ly cong viec tu hang doi (dequeue)..." << std::endl;

    // 3. Xu ly cac cong viec theo thu tu FIFO (lay ra tu dau hang doi)
    while (!task_queue.empty()) { // Lap cho den khi hang doi rong
        int current_task_id = task_queue.front(); // Lay cong viec o dau hang doi (khong xoa)
        std::cout << " <- Dang xu ly cong viec ID: " << current_task_id << std::endl;
        task_queue.pop();                     // Xoa cong viec o dau hang doi
        // (Tai day co the them logic xu ly cong viec thuc te)
    }

    std::cout << "\nHang doi hien tai co rong khong? " << (task_queue.empty() ? "Co" : "Khong") << std::endl; // Kiem tra sau khi xu ly het

     std::cout << "\nThem them cong viec..." << std::endl;
     task_queue.push(201);
     std::cout << " -> Da them cong viec ID: 201" << std::endl;
     task_queue.push(202);
     std::cout << " -> Da them cong viec ID: 202" << std::endl;

     std::cout << "\nXu ly cong viec tiep theo..." << std::endl;
     while (!task_queue.empty()) {
        int current_task_id = task_queue.front();
        std::cout << " <- Dang xu ly cong viec ID: " << current_task_id << std::endl;
        task_queue.pop();
     }
      std::cout << "\nHang doi hien tai co rong khong? " << (task_queue.empty() ? "Co" : "Khong") << std::endl;
}

int main() {
    simulateTaskQueue();
    return 0;
}

Giải thích Code:

1. Include <queue>: Để sử dụng std::queue.
2. simulateTaskQueue function:
   • Tạo một std::queue<int> có tên task_queue. Queue này sẽ lưu trữ các số nguyên (ID tác vụ).
   • Thêm vào hàng đợi (Enqueue): Sử dụng task_queue.push(value) để thêm các tác vụ vào cuối hàng đợi. Các tác vụ được thêm vào theo thứ tự 101, 102, 103.
   • Xử lý/Lấy ra khỏi hàng đợi (Dequeue): Sử dụng vòng lặp while (!task_queue.empty()) để tiếp tục xử lý cho đến khi hàng đợi hết tác vụ.
     • task_queue.front(): Lấy giá trị của phần tử ở đầu hàng đợi (tác vụ đã vào queue sớm nhất) mà không xóa nó.
     • task_queue.pop(): Xóa phần tử ở đầu hàng đợi.
   • Quá trình này đảm bảo rằng các tác vụ được xử lý theo đúng thứ tự chúng được thêm vào (FIFO).
   • Sau khi vòng lặp đầu tiên kết thúc, hàng đợi rỗng. Minh họa thêm tác vụ mới và xử lý tiếp.
3. main function: Gọi hàm simulateTaskQueue() để chạy mô phỏng.

Bài tập này minh họa cách Queue hoạt động theo nguyên tắc FIFO và cách sử dụng nó để quản lý thứ tự xử lý các mục.

Bài tập 5: Kiểm tra Cân bằng Dấu ngoặc bằng Stack

Đây là một bài tập kinh điển sử dụng Stack để kiểm tra tính đúng đắn của một biểu thức, cụ thể là kiểm tra xem các cặp dấu ngoặc (), [], {} trong biểu thức có được đóng mở đúng thứ tự và đầy đủ hay không.

Mô tả Bài tập:

Viết một hàm C++ nhận vào một chuỗi (std::string) biểu thức. Hàm này sẽ sử dụng Stack để kiểm tra xem các dấu ngoặc trong biểu thức có cân bằng hay không (mỗi dấu ngoặc mở đều có dấu ngoặc đóng tương ứng, đúng loại, và đúng thứ tự). Trả về true nếu cân bằng, false nếu không.

Code C++ Minh họa:

Chúng ta sẽ sử dụng std::stack<char> và một std::map để dễ dàng kiểm tra cặp dấu ngoặc tương ứng.

#include <iostream>
#include <string>
#include <stack>   // Cho std::stack
#include <map>     // Cho std::map

bool areBracketsBalanced(const std::string& expression) {
    // 1. Tao mot stack de luu tru cac dau ngoac mo
    std::stack<char> bracket_stack;

    // 2. Tao mot map de luu tru cap dong/mo cua cac dau ngoac
    // Key la dau ngoac dong, Value la dau ngoac mo tuong ung
    std::map<char, char> bracket_map;
    bracket_map[')'] = '(';
    bracket_map[']'] = '[';
    bracket_map['}'] = '{';

    // 3. Duyet qua tung ky tu trong chuoi bieu thuc
    for (char c : expression) {
        // Neu ky tu la dau ngoac mo, day vao stack
        if (c == '(' || c == '[' || c == '{') {
            bracket_stack.push(c);
        }
        // Neu ky tu la dau ngoac dong
        else if (c == ')' || c == ']' || c == '}') {
            // Kiem tra:
            // a. Stack co rong khong? Neu rong ma gap dau ngoac dong -> Sai (thieu dau mo)
            // b. Dau ngoac mo o dinh stack co phai la loai tuong ung voi dau ngoac dong hien tai khong?
            //    bracket_map[c] se tra ve dau ngoac mo tuong ung voi 'c'
            if (bracket_stack.empty() || bracket_stack.top() != bracket_map[c]) {
                return false; // Khong can bang
            }
            // Neu stack khong rong va dau ngoac mo tuong ung o dinh, thi lay no ra
            bracket_stack.pop();
        }
        // Bo qua cac ky tu khac (so, phep toan, chu cai...)
    }

    // 4. Sau khi duyet het chuoi, neu stack rong thi tat ca cac dau ngoac mo deu da co cap dong tuong ung
    // Neu stack con phan tu, tuc la co dau ngoac mo bi thieu dau dong
    return bracket_stack.empty();
}

int main() {
    std::string exp1 = "{([])}";
    std::cout << exp1 << " co can bang khong? " << (areBracketsBalanced(exp1) ? "Co" : "Khong") << std::endl; // Du kien: Co

    std::string exp2 = "([)]";
    std::cout << exp2 << " co can bang khong? " << (areBracketsBalanced(exp2) ? "Co" : "Khong") << std::endl; // Du kien: Khong

    std::string exp3 = "((()))";
    std::cout << exp3 << " co can bang khong? " << (areBracketsBalanced(exp3) ? "Co" : "Khong") << std::endl; // Du kien: Co

    std::string exp4 = "{[}]"; // Sai vi sap xep sai
    std::cout << exp4 << " co can bang khong? " << (areBracketsBalanced(exp4) ? "Co" : "Khong") << std::endl; // Du kien: Khong

    std::string exp5 = ""; // Chuoi rong duoc coi la can bang
    std::cout << "Chuoi rong '" << exp5 << "' co can bang khong? " << (areBracketsBalanced(exp5) ? "Co" : "Khong") << std::endl; // Du kien: Co

     std::string exp6 = "{[("; // Thieu dau dong
    std::cout << exp6 << " co can bang khong? " << (areBracketsBalanced(exp6) ? "Co" : "Khong") << std::endl; // Du kien: Khong

    return 0;
}

Giải thích Code:

1. Include <stack> và <map>: Cần hai thư viện này.
2. areBracketsBalanced function:
   • Tạo một std::stack<char> để lưu trữ các dấu ngoặc mở gặp trên đường đi.
   • Tạo một std::map<char, char> để ánh xạ dấu ngoặc đóng với dấu ngoặc mở tương ứng của nó (ví dụ: ')' ánh xạ với '('). Điều này giúp kiểm tra cặp dễ dàng.
   • Duyệt qua từng ký tự c trong chuỗi expression:
     • Nếu c là dấu ngoặc mở ((, [, hoặc {), đẩy nó vào bracket_stack.
     • Nếu c là dấu ngoặc đóng (), ], hoặc }):
       • Kiểm tra xem stack có rỗng không (bracket_stack.empty()). Nếu rỗng, nghĩa là gặp dấu ngoặc đóng mà không có dấu mở nào trước đó -> không cân bằng, trả về false.
       • Nếu stack không rỗng, kiểm tra xem dấu ngoặc mở ở đỉnh stack (bracket_stack.top()) có phải là cặp tương ứng với dấu ngoặc đóng hiện tại (bracket_map[c]) không. Nếu không khớp -> không cân bằng, trả về false.
       • Nếu khớp, lấy dấu ngoặc mở tương ứng ra khỏi stack bằng bracket_stack.pop().
     • Các ký tự khác ngoài dấu ngoặc được bỏ qua.
   • Sau khi duyệt hết chuỗi, kiểm tra bracket_stack.empty().
     • Nếu stack rỗng, nghĩa là mọi dấu ngoặc mở đều đã tìm thấy cặp đóng tương ứng và được lấy ra khỏi stack theo đúng thứ tự -> cân bằng, trả về true.
     • Nếu stack không rỗng, nghĩa là còn sót lại dấu ngoặc mở chưa có cặp đóng -> không cân bằng, trả về false.
3. main function: Thử nghiệm hàm với nhiều chuỗi biểu thức khác nhau để kiểm tra các trường hợp cân bằng, không cân bằng do sai cặp, không cân bằng do sai thứ tự, và chuỗi rỗng.

Bài tập này là một ví dụ tuyệt vời về việc sử dụng Stack để theo dõi "trạng thái" tạm thời cần được xử lý theo thứ tự ngược (dấu ngoặc mở nào được nhìn thấy cuối cùng thì phải được đóng đầu tiên).

Bài tập 6: Cài đặt Queue bằng hai Stack

Bài tập này nâng cao hơn một chút, yêu cầu bạn sử dụng các cấu trúc dữ liệu đã biết (Stack) để cài đặt một cấu trúc dữ liệu khác (Queue). Đây là một cách hay để hiểu sâu hơn về cách các cấu trúc dữ liệu có thể được xây dựng dựa trên nhau và các đánh đổi về hiệu năng.

Mô tả Bài tập:

Cài đặt một lớp QueueUsingTwoStacks mô phỏng hoạt động của Queue (FIFO) nhưng chỉ sử dụng hai đối tượng Stack bên trong. Cung cấp các hàm enqueue (thêm vào cuối), dequeue (lấy ra từ đầu), front (xem phần tử ở đầu), và isEmpty.

Code C++ Minh họa:

Chúng ta sẽ sử dụng hai std::stack<int>: một cho việc thêm vào (enqueue_stack) và một cho việc lấy ra (dequeue_stack).

#include <iostream>
#include <stack> // Cho std::stack
#include <stdexcept> // Cho std::runtime_error (xu ly loi)

class QueueUsingTwoStacks {
private:
    std::stack<int> enqueue_stack; // Stack de them phan tu vao (tuong tu enqueue)
    std::stack<int> dequeue_stack; // Stack de lay phan tu ra (tuong tu dequeue)

    // Ham ho tro: Chuyen tat ca phan tu tu enqueue_stack sang dequeue_stack
    // Chi thuc hien khi dequeue_stack rong
    void transfer_stacks() {
        if (dequeue_stack.empty()) {
            while (!enqueue_stack.empty()) {
                dequeue_stack.push(enqueue_stack.top()); // Day tu stack 1 sang stack 2
                enqueue_stack.pop();                     // Xoa khoi stack 1
            }
        }
    }

public:
    // Them phan tu vao cuoi hang doi (Enqueue)
    void enqueue(int val) {
        enqueue_stack.push(val); // Chi can day vao stack them vao
        std::cout << "Enqueue: " << val << std::endl;
    }

    // Lay phan tu dau hang doi (Dequeue)
    int dequeue() {
        // Dam bao dequeue_stack co du lieu de lay.
        // Neu rong, thi phai chuyen tu enqueue_stack sang.
        transfer_stacks();

        // Neu sau khi chuyen ma dequeue_stack van rong, tuc la hang doi thuc su rong
        if (dequeue_stack.empty()) {
            std::cerr << "Loi: Hang doi rong, khong the dequeue." << std::endl;
             // Lua chon: tra ve gia tri bao loi, hoac throw exception
             // throw std::runtime_error("Dequeue tren hang doi rong");
             return -1; // Tra ve -1 hoac gia tri bat thuong de bao loi
        }

        // Lay gia tri va xoa phan tu o dau hang doi (dinh cua dequeue_stack)
        int front_val = dequeue_stack.top();
        dequeue_stack.pop();
        std::cout << "Dequeue: " << front_val << std::endl;
        return front_val;
    }

    // Xem phan tu dau hang doi ma khong xoa (Front/Peek)
    int front() {
         // Dam bao dequeue_stack co du lieu
        transfer_stacks();

        // Neu sau khi chuyen ma dequeue_stack van rong
        if (dequeue_stack.empty()) {
            std::cerr << "Loi: Hang doi rong, khong co phan tu de xem." << std::endl;
            // throw std::runtime_error("Front tren hang doi rong");
            return -1; // Tra ve -1 hoac gia tri bat thuong de bao loi
        }

        // Tra ve gia tri o dinh dequeue_stack
        return dequeue_stack.top();
    }

    // Kiem tra hang doi co rong khong
    bool isEmpty() const {
        // Hang doi rong khi ca hai stack deu rong
        return enqueue_stack.empty() && dequeue_stack.empty();
    }
};

int main() {
    QueueUsingTwoStacks q;

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    std::cout << "\nDequeueing..." << std::endl;
    q.dequeue(); // Du kien: 10 (lay tu dequeue_stack sau khi chuyen)
    q.dequeue(); // Du kien: 20

    std::cout << "\nEnqueueing more..." << std::endl;
    q.enqueue(40);
    q.enqueue(50);

    std::cout << "\nDequeueing more..." << std::endl;
    q.dequeue(); // Du kien: 30 (lay tiep tu dequeue_stack)
    q.dequeue(); // Du kien: 40 (lay tiep tu dequeue_stack)
    q.dequeue(); // Du kien: 50 (lay tiep tu dequeue_stack)

    std::cout << "\nDequeueing from empty queue..." << std::endl;
    q.dequeue(); // Du kien: Loi va tra ve -1

    std::cout << "\nHang doi co rong khong? " << (q.isEmpty() ? "Co" : "Khong") << std::endl; // Du kien: Co

    return 0;
}

Giải thích Code:

1. Hai Stack: Lớp QueueUsingTwoStacks chứa hai thành viên là std::stack<int>: enqueue_stack và dequeue_stack.
2. enqueue(int val): Khi thêm một phần tử, chúng ta chỉ đơn giản là đẩy (push) nó vào enqueue_stack. Thao tác này là O(1).
3. dequeue() và front(): Đây là phần logic chính. Để lấy hoặc xem phần tử ở đầu hàng đợi (FIFO), chúng ta cần lấy từ dequeue_stack.
   • Hàm transfer_stacks(): Hàm này kiểm tra xem dequeue_stack có rỗng không. Nếu nó rỗng, điều đó có nghĩa là tất cả các phần tử từ enqueue_stack cần được chuyển sang dequeue_stack để có thể lấy ra theo đúng thứ tự FIFO. Quá trình chuyển diễn ra bằng cách lặp lại việc lấy phần tử ở đỉnh enqueue_stack (top()) và đẩy nó vào dequeue_stack (push()), sau đó xóa nó khỏi enqueue_stack (pop()). Do Stack là LIFO, việc chuyển này sẽ đảo ngược thứ tự một lần nữa, đưa các phần tử về đúng thứ tự FIFO ban đầu khi chúng được thêm vào enqueue_stack.
   • Logic Dequeue/Front: Trước khi thực hiện top() và pop() trên dequeue_stack, luôn gọi transfer_stacks() để đảm bảo dequeue_stack có dữ liệu nếu có thể chuyển được. Sau đó, kiểm tra lại dequeue_stack.empty(). Nếu vẫn rỗng, tức là cả hai stack đều rỗng, hàng đợi thực sự rỗng, cần xử lý lỗi (ví dụ: in thông báo và trả về giá trị báo lỗi hoặc ném ngoại lệ). Nếu không rỗng, thực hiện top() để xem hoặc top() kèm pop() để lấy phần tử.
   • Chi phí: Thao tác enqueue luôn là O(1). Thao tác dequeue (hoặc front) có thể tốn O(N) trong trường hợp xấu nhất (khi dequeue_stack rỗng và tất cả N phần tử phải được chuyển từ enqueue_stack). Tuy nhiên, xét trên toàn bộ chuỗi các thao tác, mỗi phần tử chỉ được chuyển giữa hai stack tối đa một lần. Do đó, chi phí trung bình (amortized cost) cho mỗi thao tác dequeue vẫn là O(1).
4. isEmpty(): Hàng đợi được coi là rỗng khi và chỉ khi cả hai stack enqueue_stack và dequeue_stack đều rỗng.

Bài tập ví dụ:

Die Hard

Bộ phim "Die Hard" mới vừa được phát hành! Có n người tại phòng vé rạp chiếu phim đứng thành một hàng lớn. Mỗi người trong số họ có một tờ tiền mệnh giá 100, 50 hoặc 25 rúp. Một vé "Die Hard" có giá 25 rúp. Nhân viên đặt phòng có thể bán vé cho mỗi người và trả tiền thừa nếu ban đầu anh ta không có tiền và bán vé theo đúng thứ tự mọi người trong hàng không?

Input Format

Dòng đầu tiên chứa số nguyên n:số người trong hàng. Dòng tiếp theo chứa n số nguyên, mỗi số bằng 25, 50 hoặc 100 - giá trị của các tờ tiền mà mọi người có.(1≤n≤10^6)

Constraints

.

Output Format

In YES nếu người bán hàng có thể bán và trả tiền thừa cho mọi người trong hàng, ngược lại in NO.

Ví dụ:

Dữ liệu vào

5
25 25 50 25 100

Dữ liệu ra

YES

Đây là hướng dẫn giải bài "Die Hard" bằng C++ một cách ngắn gọn:

1. Ý tưởng chính: Mô phỏng quá trình bán vé của người bán hàng, theo dõi số lượng các tờ tiền mệnh giá 25 và 50 rúp mà người bán đang có.
2. Khởi tạo: Bắt đầu với 0 tờ tiền 25 rúp và 0 tờ tiền 50 rúp.
3. Duyệt từng người: Lần lượt xử lý từng người trong hàng theo đúng thứ tự.
4. Xử lý thanh toán: Đối với mỗi người, kiểm tra mệnh giá tờ tiền họ đưa:
   • Nếu là 25 rúp: Người bán nhận 25 rúp, không cần trả lại tiền thừa. Tăng số lượng tờ 25 rúp của người bán lên 1.
   • Nếu là 50 rúp: Người bán nhận 50 rúp, cần trả lại 25 rúp tiền thừa. Kiểm tra xem người bán có ít nhất một tờ 25 rúp không. Nếu có, trả lại một tờ 25 rúp (giảm số lượng tờ 25 rúp đi 1) và ghi nhận tờ 50 rúp nhận được (tăng số lượng tờ 50 rúp lên 1). Nếu không đủ tờ 25 rúp để trả thừa, người bán không thể bán vé cho người này -> In ra "NO" và kết thúc chương trình.
   • Nếu là 100 rúp: Người bán nhận 100 rúp, cần trả lại 75 rúp tiền thừa. Có hai cách trả 75 rúp bằng các tờ 25 và 50:
     • Cách 1: Một tờ 50 rúp và một tờ 25 rúp. Ưu tiên dùng cách này trước để giữ lại các tờ 25 rúp quý giá cho việc trả thừa 25 rúp sau này. Kiểm tra xem người bán có ít nhất một tờ 50 rúp VÀ ít nhất một tờ 25 rúp không. Nếu có, trả tiền thừa bằng cách này (giảm số lượng tờ 50 rúp đi 1, giảm số lượng tờ 25 rúp đi 1).
     • Cách 2: Ba tờ 25 rúp. Nếu không thể dùng Cách 1, kiểm tra xem người bán có ít nhất ba tờ 25 rúp không. Nếu có, trả tiền thừa bằng cách này (giảm số lượng tờ 25 rúp đi 3).
     • Nếu không thể trả tiền thừa bằng cả Cách 1 và Cách 2, người bán không thể bán vé cho người này -> In ra "NO" và kết thúc chương trình.
5. Kết thúc: Nếu vòng lặp xử lý hết tất cả mọi người mà không bị dừng lại ở bước nào vì thiếu tiền thừa, nghĩa là người bán đã thành công bán vé cho tất cả mọi người -> In ra "YES".

Lưu ý: Bạn chỉ cần theo dõi số lượng tờ 25 và 50 rúp. Số lượng tờ 100 rúp người bán nhận được không quan trọng vì tờ 100 rúp không bao giờ được dùng để trả tiền thừa 25 hoặc 75 rúp.

Làm thêm nhiều bài tập miễn phí tại đây