Khóa học CTDL và GT

Bài 7.1: Stack và các ứng dụng trong giải thuật

Chào mừng các bạn quay trở lại với series Cấu trúc dữ liệu và Giải thuật của FullhouseDev! Hôm nay, chúng ta sẽ lặn sâu vào một trong những cấu trúc dữ liệu cơ bản nhưng vô cùng mạnh mẽ và có ứng dụng rộng rãi: Stack (Ngăn xếp).

Stack là một cấu trúc dữ liệu tuyến tính tuân thủ một nguyên tắc hoạt động rất đặc biệt: LIFO (Last-In, First-Out - Vào sau, Ra trước). Hãy tưởng tượng bạn đang xếp chồng những chiếc đĩa lên nhau. Chiếc đĩa bạn đặt cuối cùng lên trên cùng sẽ là chiếc đĩa bạn lấy ra đầu tiên. Đó chính là nguyên lý của Stack!

Nguyên lý LIFO làm cho Stack trở thành công cụ lý tưởng cho nhiều tác vụ trong khoa học máy tính, từ việc quản lý các lời gọi hàm cho đến xử lý các biểu thức toán học phức tạp.

Nguyên lý hoạt động của Stack: LIFO

Như đã nói, điểm cốt lõi của Stack là LIFO. Điều này có nghĩa là phần tử được thêm vào cuối cùng sẽ là phần tử đầu tiên được loại bỏ.

Các thao tác cơ bản trên Stack bao gồm:

1. push(element): Thêm một phần tử vào đỉnh (top) của Stack.
2. pop(): Loại bỏ phần tử ở đỉnh của Stack.
3. top() hoặc peek(): Truy cập (nhưng không loại bỏ) phần tử ở đỉnh của Stack.
4. isEmpty(): Kiểm tra xem Stack có rỗng hay không.
5. size(): Trả về số lượng phần tử hiện có trong Stack.

Quan trọng: Các thao tác push, pop, và top chỉ làm việc với đỉnh của Stack. Bạn không thể truy cập trực tiếp các phần tử ở giữa hoặc dưới đáy Stack một cách dễ dàng theo định nghĩa chuẩn của nó.

Cách triển khai Stack

Stack có thể được triển khai bằng nhiều cách, phổ biến nhất là sử dụng Mảng (Array) hoặc Danh sách liên kết (Linked List).

• Triển khai bằng Mảng: Đơn giản và hiệu quả về không gian nếu kích thước Stack có thể ước lượng được. Tuy nhiên, có thể gặp vấn đề tràn Stack (Stack Overflow) nếu thêm quá nhiều phần tử vượt quá kích thước mảng ban đầu.
• Triển khai bằng Danh sách liên kết: Linh hoạt hơn vì kích thước có thể tăng trưởng động theo nhu cầu. Thường tốn kém hơn một chút về mặt bộ nhớ do chi phí cho các con trỏ.

Trong thực tế và đặc biệt là trong C++, thư viện chuẩn (std::stack) cung cấp một cách triển khai Stack tiện lợi và hiệu quả, thường sử dụng std::deque (deque - double-ended queue) hoặc std::list làm container mặc định.

Hãy xem một ví dụ cơ bản về cách sử dụng std::stack trong C++:

#include <iostream>
#include <stack> // Bao gồm thư viện stack
#include <string>

int main() {
    // Khai báo một Stack chứa các số nguyên
    std::stack<int> myStack;

    std::cout << "Stack ban dau rong: " << std::boolalpha << myStack.empty() << std::endl; // boolalpha de in true/false

    // Thêm cac phan tu vao Stack (push)
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    std::cout << "Sau khi push 10, 20, 30. Stack con rong khong? " << myStack.empty() << std::endl;
    std::cout << "So luong phan tu trong Stack: " << myStack.size() << std::endl;

    // Xem phan tu o dinh Stack (top)
    std::cout << "Phan tu o dinh Stack: " << myStack.top() << std::endl; // Ket qua la 30 vi LIFO

    // Loai bo phan tu o dinh Stack (pop)
    myStack.pop();
    std::cout << "Sau khi pop mot lan, phan tu o dinh Stack: " << myStack.top() << std::endl; // Ket qua la 20

    // Pop tat ca cac phan tu cho den khi Stack rong
    std::cout << "Pop het cac phan tu:" << std::endl;
    while (!myStack.empty()) {
        std::cout << myStack.top() << " ";
        myStack.pop();
    }
    std::cout << std::endl;

    std::cout << "Stack sau khi pop het rong: " << myStack.empty() << std::endl;

    return 0;
}

Giải thích code:

• Chúng ta khai báo std::stack<int> myStack; để tạo một stack chứa các số nguyên. Bạn có thể thay int bằng bất kỳ kiểu dữ liệu nào khác (string, double, custom objects, v.v.).
• myStack.push(value) thêm value vào đỉnh.
• myStack.top() trả về giá trị của phần tử ở đỉnh nhưng không xóa nó.
• myStack.pop() xóa phần tử ở đỉnh.
• myStack.empty() trả về true nếu stack không có phần tử nào, ngược lại trả về false.
• myStack.size() trả về số lượng phần tử hiện tại.

Ví dụ này minh họa rõ ràng nguyên lý LIFO: 30 được push cuối cùng, nên khi gọi top() lần đầu nó là 30. Sau khi pop(), 30 bị loại bỏ, và 20 (phần tử được push gần cuối) trở thành đỉnh mới.

Các ứng dụng của Stack trong giải thuật

Stack không chỉ là một cấu trúc dữ liệu đơn thuần; nó là nền tảng cho việc xây dựng và thực hiện nhiều giải thuật quan trọng. Dưới đây là một số ứng dụng nổi bật:

1. Quản lý lời gọi hàm (Function Call Stack)

Đây có lẽ là ứng dụng "vô hình" nhưng quan trọng nhất của Stack mà hầu hết các lập trình viên sử dụng hàng ngày mà không nhận ra. Khi một chương trình thực thi, hệ thống sẽ sử dụng một Stack nội bộ gọi là Call Stack để quản lý các lời gọi hàm.

• Khi một hàm được gọi, thông tin về trạng thái hiện tại của hàm gọi (ví dụ: địa chỉ trả về, biến cục bộ) được push lên Call Stack. Đây gọi là tạo một stack frame.
• Khi hàm đó gọi một hàm khác, một stack frame mới cho hàm thứ hai lại được push lên đỉnh Stack.
• Khi một hàm kết thúc thực thi, stack frame tương ứng của nó sẽ bị pop khỏi Stack, và chương trình quay trở lại trạng thái của stack frame ở đỉnh Stack cũ (hàm gọi nó).

Nguyên lý LIFO đảm bảo rằng khi một hàm con kết thúc, chương trình sẽ trả về đúng nơi đã gọi nó. Nếu có quá nhiều hàm gọi lồng nhau hoặc một hàm đệ quy không có điểm dừng chính xác, Call Stack có thể bị đầy dẫn đến lỗi Stack Overflow.

2. Kiểm tra tính hợp lệ của dấu ngoặc đơn/ngoặc kép/ngoặc nhọn (Parentheses Matching)

Một bài toán kinh điển sử dụng Stack là kiểm tra xem một chuỗi biểu thức có các cặp dấu ngoặc đơn (), ngoặc vuông [], và ngoặc nhọn {} được đóng mở đúng cách và cân bằng hay không.

Giải thuật sử dụng Stack như sau:

• Duyệt qua chuỗi từ trái sang phải.
• Nếu gặp dấu ngoặc mở ((, [, {), push nó vào Stack.
• Nếu gặp dấu ngoặc đóng (), ], }), kiểm tra đỉnh Stack:
  • Nếu Stack rỗng hoặc phần tử ở đỉnh không phải là dấu ngoặc mở tương ứng, chuỗi không hợp lệ.
  • Nếu phần tử ở đỉnh là dấu ngoặc mở tương ứng, pop nó khỏi Stack (vì cặp này đã khớp).
• Sau khi duyệt hết chuỗi, nếu Stack rỗng, chuỗi hợp lệ. Nếu Stack còn phần tử, chuỗi không hợp lệ (có dấu ngoặc mở chưa được đóng).

Ví dụ minh họa bằng C++:

#include <iostream>
#include <stack>
#include <string>

bool isBalanced(const std::string& expression) {
    std::stack<char> s; // Stack de luu tru dau ngoac mo

    for (char ch : expression) {
        if (ch == '(' || ch == '[' || ch == '{') {
            // Neu la dau ngoac mo, push vao Stack
            s.push(ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            // Neu la dau ngoac dong
            if (s.empty()) {
                // Neu Stack rong ma lai co dau ngoac dong -> khong can bang
                return false;
            }

            // Lay dau ngoac mo o dinh Stack de kiem tra
            char topChar = s.top();
            s.pop(); // Loai bo dau ngoac mo vua kiem tra

            // Kiem tra xem dau ngoac dong co tuong ung voi dau ngoac mo o dinh Stack khong
            if ((ch == ')' && topChar != '(') ||
                (ch == ']' && topChar != '[') ||
                (ch == '}' && topChar != '{')) {
                return false; // Khong tuong ung -> khong can bang
            }
        }
        // Bo qua cac ky tu khac (chu cai, so, phep toan...)
    }

    // Sau khi duyet het chuoi, neu Stack rong thi cac dau ngoac deu duoc dong dung cach
    return s.empty();
}

int main() {
    std::string expr1 = "{ [ ( ) ] }"; // Hop le
    std::string expr2 = "{ [ ( ] ) }"; // Khong hop le
    std::string expr3 = "{ ( }";       // Khong hop le
    std::string expr4 = "([])";        // Hop le
    std::string expr5 = "(";           // Khong hop le (thieu dong)
    std::string expr6 = "())";         // Khong hop le (thua dong)

    std::cout << expr1 << " is balanced: " << std::boolalpha << isBalanced(expr1) << std::endl;
    std::cout << expr2 << " is balanced: " << std::boolalpha << isBalanced(expr2) << std::endl;
    std::cout << expr3 << " is balanced: " << std::boolalpha << isBalanced(expr3) << std::endl;
    std::cout << expr4 << " is balanced: " << std::boolalpha << isBalanced(expr4) << std::endl;
    std::cout << expr5 << " is balanced: " << std::boolalpha << isBalanced(expr5) << std::endl;
    std::cout << expr6 << " is balanced: " << std::boolalpha << isBalanced(expr6) << std::endl;

    return 0;
}

Giải thích code:

• Hàm isBalanced nhận một chuỗi expression.
• Sử dụng std::stack<char> s; để lưu trữ các ký tự ngoặc mở.
• Duyệt từng ký tự ch trong chuỗi.
• Nếu ch là ngoặc mở, đẩy (push) nó vào stack.
• Nếu ch là ngoặc đóng:
  • Kiểm tra xem stack có rỗng không. Nếu rỗng, có ngoặc đóng mà không có ngoặc mở tương ứng, nên trả về false.
  • Nếu không rỗng, lấy ký tự ở đỉnh stack (s.top()) và sau đó xóa nó (s.pop()).
  • So sánh ký tự ngoặc đóng hiện tại (ch) với ký tự ngoặc mở vừa lấy ra (topChar). Nếu chúng không phải là một cặp hợp lệ (ví dụ: đóng là ) nhưng mở là [), trả về false.
• Sau khi duyệt hết chuỗi, nếu stack s rỗng (s.empty() trả về true), nghĩa là mọi ngoặc mở đều đã được đóng đúng cách, hàm trả về true. Nếu stack không rỗng, có ngoặc mở chưa được đóng, trả về false.

3. Chuyển đổi và tính toán biểu thức (Expression Conversion and Evaluation)

Stack đóng vai trò quan trọng trong việc xử lý các biểu thức số học, đặc biệt là khi chuyển đổi giữa các dạng biểu diễn (Infix, Postfix, Prefix) và tính toán giá trị của chúng.

• Dạng Infix: Dạng thông thường chúng ta viết (ví dụ: A + B * C). Có quy tắc ưu tiên toán tử.
• Dạng Postfix (Reverse Polish Notation - RPN): Toán tử đứng sau toán hạng (ví dụ: A B C * +). Không cần dấu ngoặc và không cần quy tắc ưu tiên phức tạp khi tính toán.
• Dạng Prefix (Polish Notation): Toán tử đứng trước toán hạng (ví dụ: + A * B C).

Chuyển đổi từ Infix sang Postfix

Quá trình này sử dụng Stack để xử lý các toán tử và dấu ngoặc, đảm bảo quy tắc ưu tiên được giữ đúng khi chuyển sang dạng Postfix.

Thuật toán cơ bản:

1. Khởi tạo một Stack rỗng cho toán tử và một chuỗi kết quả rỗng cho Postfix.
2. Duyệt chuỗi Infix từ trái sang phải.
3. Nếu là toán hạng (chữ cái hoặc số): Thêm vào chuỗi kết quả.
4. Nếu là ngoặc mở (: Push vào Stack.
5. Nếu là ngoặc đóng ): Pop toán tử từ Stack và thêm vào chuỗi kết quả cho đến khi gặp ngoặc mở (. Pop cả ngoặc mở đó ra (nhưng không thêm vào kết quả).
6. Nếu là toán tử (+, -, *, /):
   • Pop các toán tử từ Stack và thêm vào chuỗi kết quả miễn là Stack không rỗng, đỉnh Stack là toán tử, và toán tử ở đỉnh có độ ưu tiên lớn hơn hoặc bằng toán tử hiện tại.
   • Push toán tử hiện tại vào Stack.
7. Sau khi duyệt hết chuỗi Infix: Pop tất cả các toán tử còn lại trong Stack và thêm vào chuỗi kết quả.

Cần có hàm xác định độ ưu tiên của toán tử.

Ví dụ minh họa bằng C++ (đơn giản với +, -, *, /):

#include <iostream>
#include <stack>
#include <string>
#include <cctype> // De su dung isalnum

// Ham kiem tra do uu tien cua toan tu
// Tra ve gia tri cao hon cho do uu tien cao hon
int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0; // Cac ky tu khac (ngoac) hoac khong phai toan tu
}

std::string infixToPostfix(const std::string& infix) {
    std::stack<char> opStack; // Stack de luu tru toan tu
    std::string postfix = ""; // Chuoi ket qua

    for (char ch : infix) {
        if (std::isalnum(ch)) {
            // Neu la toan hang (chu hoac so), them vao ket qua
            postfix += ch;
        } else if (ch == '(') {
            // Neu la ngoac mo, push vao stack
            opStack.push(ch);
        } else if (ch == ')') {
            // Neu la ngoac dong, pop toan tu tu stack cho den khi gap ngoac mo
            while (!opStack.empty() && opStack.top() != '(') {
                postfix += opStack.top();
                opStack.pop();
            }
            if (!opStack.empty() && opStack.top() == '(') {
                opStack.pop(); // Loai bo ngoac mo khoi stack
            }
        } else { // La toan tu
            // Pop cac toan tu co do uu tien >= toan tu hien tai
            while (!opStack.empty() && precedence(opStack.top()) >= precedence(ch)) {
                postfix += opStack.top();
                opStack.pop();
            }
            // Push toan tu hien tai vao stack
            opStack.push(ch);
        }
    }

    // Pop tat ca toan tu con lai trong stack va them vao ket qua
    while (!opStack.empty()) {
        postfix += opStack.top();
        opStack.pop();
    }

    return postfix;
}

int main() {
    std::string infix1 = "A+B*C";      // Output: ABC*+
    std::string infix2 = "(A+B)*C";    // Output: AB+C*
    std::string infix3 = "A*(B+C/D)";  // Output: ABCD/+*
    std::string infix4 = "A*B+C/D";    // Output: AB*CD/+

    std::cout << "Infix: " << infix1 << " -> Postfix: " << infixToPostfix(infix1) << std::endl;
    std::cout << "Infix: " << infix2 << " -> Postfix: " << infixToPostfix(infix2) << std::endl;
    std::cout << "Infix: " << infix3 << " -> Postfix: " << infixToPostfix(infix3) << std::endl;
    std::cout << "Infix: " << infix4 << " -> Postfix: " << infixToPostfix(infix4) << std::endl;

    return 0;
}

Giải thích code:

• Hàm precedence đơn giản hóa việc xác định toán tử nào ưu tiên hơn.
• Sử dụng một stack opStack để tạm thời giữ các toán tử.
• Duyệt chuỗi infix.
• Nếu là ký tự chữ/số (toán hạng), thêm ngay vào chuỗi postfix.
• Nếu là (: đẩy vào stack.
• Nếu là ): đẩy các toán tử từ stack ra kết quả cho đến khi gặp (, sau đó bỏ ( ra khỏi stack.
• Nếu là toán tử: Lặp và đẩy các toán tử từ stack ra kết quả nếu chúng có độ ưu tiên lớn hơn hoặc bằng toán tử hiện tại, sau đó đẩy toán tử hiện tại vào stack.
• Sau vòng lặp, đẩy hết các toán tử còn lại trong stack ra kết quả.

Tính toán giá trị biểu thức Postfix

Việc tính toán biểu thức Postfix đơn giản hơn nhiều vì không cần quan tâm đến độ ưu tiên toán tử.

Thuật toán:

1. Khởi tạo một Stack rỗng cho các toán hạng.
2. Duyệt chuỗi Postfix từ trái sang phải.
3. Nếu là toán hạng (số): Chuyển nó thành số và push vào Stack toán hạng.
4. Nếu là toán tử:
   • Pop hai toán hạng từ Stack (toán hạng thứ hai bị pop ra trước là toán hạng bên phải, toán hạng đầu tiên bị pop ra là toán hạng bên trái).
   • Thực hiện phép toán với hai toán hạng vừa pop và toán tử hiện tại.
   • Push kết quả của phép toán trở lại Stack.
5. Sau khi duyệt hết chuỗi Postfix, kết quả cuối cùng sẽ nằm ở đỉnh Stack. Pop nó ra.

Ví dụ minh họa bằng C++ (với các toán hạng là số đơn):

#include <iostream>
#include <stack>
#include <string>
#include <cctype> // De su dung isdigit

// Ham thuc hien phep toan don gian
int applyOperation(int a, int b, char op) {
    switch(op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/':
            if (b == 0) {
                std::cerr << "Loi: Chia cho 0!" << std::endl;
                // Co the throw exception hoac thoat chuong trinh tuy yeu cau
                exit(1);
            }
            return a / b;
    }
    return 0; // Truong hop khong hop le
}

int evaluatePostfix(const std::string& postfix) {
    std::stack<int> operandStack; // Stack de luu tru toan hang (ket qua trung gian)

    for (char ch : postfix) {
        if (std::isdigit(ch)) {
            // Neu la chu so, chuyen thanh so va push vao stack
            // Tru tru '0' de chuyen char '1' thanh int 1, '2' thanh int 2, v.v.
            operandStack.push(ch - '0');
        } else { // La toan tu
            // Can it nhat 2 toan hang trong stack de thuc hien phep toan
            if (operandStack.size() < 2) {
                 std::cerr << "Loi: Bieu thuc Postfix khong hop le (thieu toan hang)!" << std::endl;
                 exit(1);
            }

            // Pop 2 toan hang (LIFO!)
            int operand2 = operandStack.top(); operandStack.pop();
            int operand1 = operandStack.top(); operandStack.pop();

            // Thuc hien phep toan va push ket qua tro lai stack
            int result = applyOperation(operand1, operand2, ch);
            operandStack.push(result);
        }
    }

    // Sau khi duyet het chuoi, ket qua cuoi cung nam o dinh stack
    if (operandStack.size() != 1) {
        std::cerr << "Loi: Bieu thuc Postfix khong hop le (thua toan hang/toan tu)!" << std::endl;
        exit(1);
    }

    return operandStack.top();
}

int main() {
    std::string postfix1 = "231*+9-"; // 2 + (3*1) - 9 = 2 + 3 - 9 = -4
    std::string postfix2 = "12+3*";   // (1+2)*3 = 3*3 = 9
    std::string postfix3 = "45+2/5*"; // ((4+5)/2)*5 = (9/2)*5 = 4*5 = 20 (chia so nguyen)

    std::cout << "Postfix: " << postfix1 << " = " << evaluatePostfix(postfix1) << std::endl;
    std::cout << "Postfix: " << postfix2 << " = " << evaluatePostfix(postfix2) << std::endl;
    std::cout << "Postfix: " << postfix3 << " = " << evaluatePostfix(postfix3) << std::endl;

    return 0;
}

Giải thích code:

• Hàm evaluatePostfix sử dụng std::stack<int> operandStack để lưu trữ các giá trị số học.
• Duyệt từng ký tự ch trong chuỗi postfix.
• Nếu ch là chữ số (isdigit), chuyển nó thành số nguyên (ch - '0') và đẩy vào stack.
• Nếu ch là toán tử:
  • Kiểm tra xem có đủ 2 toán hạng trong stack không. Nếu không, biểu thức không hợp lệ.
  • Lấy hai toán hạng từ đỉnh stack (lưu ý thứ tự pop: cái thứ hai là toán hạng bên phải).
  • Thực hiện phép toán bằng hàm applyOperation.
  • Đẩy kết quả trở lại stack.
• Sau khi duyệt xong, kết quả cuối cùng nằm ở đỉnh stack. Kiểm tra xem stack chỉ còn 1 phần tử để đảm bảo biểu thức hợp lệ.

4. Thuật toán duyệt đồ thị theo chiều sâu (Iterative Depth First Search - DFS)

DFS là một thuật toán quan trọng để khám phá các đỉnh và cạnh của một đồ thị hoặc cây. Mặc dù DFS thường được triển khai tự nhiên bằng đệ quy (sử dụng Call Stack), nó cũng có thể được triển khai lặp (không dùng đệ quy) bằng cách sử dụng một Stack tường minh.

Thuật toán DFS lặp sử dụng Stack:

1. Chọn một đỉnh bắt đầu, push nó vào Stack. Đánh dấu đỉnh này đã được thăm.
2. Trong khi Stack chưa rỗng:
   • Pop một đỉnh u từ Stack. Xử lý đỉnh u (ví dụ: in tên đỉnh).
   • Duyệt qua tất cả các đỉnh kề v của u.
   • Nếu đỉnh v chưa được thăm:
     • Đánh dấu v đã được thăm.
     • Push v vào Stack.

Nguyên lý LIFO của Stack đảm bảo rằng thuật toán sẽ ưu tiên đi sâu vào một nhánh của đồ thị trước khi quay trở lại khám phá các nhánh khác, giống như cách DFS hoạt động.

Ví dụ minh họa bằng C++ (ví dụ đơn giản trên đồ thị biểu diễn bằng danh sách kề):

#include <iostream>
#include <vector>
#include <stack>
#include <vector> // Bao gồm vector

// Bieu dien do thi bang danh sach ke
class Graph {
public:
    int V; // So luong dinh
    std::vector<std::vector<int>> adj; // Danh sach ke

    Graph(int V) : V(V), adj(V) {}

    // Them canh vao do thi
    void addEdge(int v, int w) {
        adj[v].push_back(w);
        // adj[w].push_back(v); // Bo chu thich neu la do thi vo huong
    }

    // Duyet DFS lap tu mot dinh bat dau
    void iterativeDFS(int startNode) {
        std::stack<int> s; // Stack de luu tru cac dinh can tham
        std::vector<bool> visited(V, false); // Mang danh dau cac dinh da tham

        // Push dinh bat dau vao stack va danh dau da tham
        s.push(startNode);
        visited[startNode] = true;

        std::cout << "Ket qua DFS bat dau tu dinh " << startNode << ": ";

        while (!s.empty()) {
            // Pop mot dinh tu stack
            int u = s.top();
            s.pop();

            // Xu ly dinh u (in ra)
            std::cout << u << " ";

            // Duyet cac dinh ke cua u
            // Duyet nguoc danh sach ke de co thu tu giong DFS de quy thong thuong hon
            for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) {
                int v = *it;
                // Neu dinh ke chua duoc tham
                if (!visited[v]) {
                    visited[v] = true; // Danh dau da tham
                    s.push(v);         // Push vao stack de tham sau
                }
            }
            // Note: Neu duyet xuoi danh sach ke, thu tu tham cac dinh ke se nguoc lai
            // so voi DFS de quy, nhung van dam bao tham het cac dinh.
        }
        std::cout << std::endl;
    }
};

int main() {
    // Tao mot do thi co 5 dinh (0 toi 4)
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 4);

    g.iterativeDFS(0); // Bat dau DFS tu dinh 0

    return 0;
}

Giải thích code:

• Chúng ta định nghĩa lớp Graph với danh sách kề adj để biểu diễn đồ thị.
• Hàm iterativeDFS nhận đỉnh startNode làm điểm bắt đầu.
• Sử dụng std::stack<int> s; để lưu trữ các đỉnh cần thăm.
• Sử dụng std::vector<bool> visited(V, false); để theo dõi các đỉnh đã được thăm, tránh lặp vô hạn trong đồ thị có chu trình.
• Đẩy đỉnh bắt đầu vào stack và đánh dấu đã thăm.
• Vòng lặp while (!s.empty()) tiếp tục cho đến khi không còn đỉnh nào trong stack để thăm.
• Trong vòng lặp, lấy (pop) đỉnh hiện tại u từ stack. In nó ra hoặc xử lý theo mục đích của bài toán.
• Duyệt qua các đỉnh kề v của u. Nếu v chưa được thăm, đánh dấu nó và đẩy vào stack. Đẩy vào stack nghĩa là nó sẽ được thăm tiếp theo (nguyên lý LIFO) khi chúng ta quay trở lại nhánh này.
• Việc duyệt ngược danh sách kề (rbegin() đến rend()) là một kỹ thuật nhỏ để làm cho thứ tự các đỉnh kề được đẩy vào stack giống với thứ tự mà DFS đệ quy sẽ xử lý (thường duyệt từ trái sang phải trong danh sách kề).

5. Đảo ngược thứ tự (Reversing Order)

Nhờ nguyên lý LIFO, Stack là công cụ cực kỳ hiệu quả để đảo ngược thứ tự của một tập hợp các phần tử (ví dụ: đảo ngược chuỗi, đảo ngược danh sách).

Cách thực hiện:

1. Duyệt qua tập hợp gốc từ đầu đến cuối.
2. Push từng phần tử vào Stack.
3. Pop từng phần tử từ Stack và xây dựng tập hợp mới. Các phần tử sẽ được pop ra theo thứ tự ngược lại so với khi chúng được push vào.

Ví dụ đảo ngược chuỗi bằng C++:

#include <iostream>
#include <stack>
#include <string>
#include <algorithm> // Can cho reverse neu muon so sanh

std::string reverseStringWithStack(const std::string& input) {
    std::stack<char> charStack;

    // Push tung ky tu vao stack
    for (char ch : input) {
        charStack.push(ch);
    }

    std::string reversedString = "";

    // Pop tung ky tu tu stack va them vao chuoi ket qua
    while (!charStack.empty()) {
        reversedString += charStack.top();
        charStack.pop();
    }

    return reversedString;
}

int main() {
    std::string str = "Hello World!";
    std::string reversedStr = reverseStringWithStack(str);

    std::cout << "Chuoi goc: " << str << std::endl;
    std::cout << "Chuoi dao nguoc (dung Stack): " << reversedStr << std::endl;

    // So sanh voi ham dao nguoc san cua C++
    std::string stdReversedStr = str;
    std::reverse(stdReversedStr.begin(), stdReversedStr.end());
    std::cout << "Chuoi dao nguoc (dung std::reverse): " << stdReversedStr << std::endl;


    return 0;
}

Giải thích code:

• Hàm reverseStringWithStack nhận một chuỗi input.
• Tạo một std::stack<char> để lưu trữ các ký tự.
• Vòng lặp đầu tiên duyệt qua chuỗi input và đẩy từng ký tự vào stack. Ký tự đầu tiên của chuỗi sẽ nằm dưới đáy stack, ký tự cuối cùng nằm ở đỉnh.
• Tạo một chuỗi rỗng reversedString.
• Vòng lặp while (!charStack.empty()) tiếp tục cho đến khi stack rỗng. Trong mỗi lần lặp, lấy ký tự ở đỉnh stack (charStack.top()) và thêm vào cuối chuỗi reversedString, sau đó loại bỏ ký tự đó khỏi stack (charStack.pop()).
• Vì các ký tự được pop ra theo thứ tự LIFO (ngược với thứ tự push vào), chuỗi reversedString sẽ là phiên bản đảo ngược của chuỗi gốc.

Các ứng dụng khác

Ngoài những ứng dụng trên, Stack còn được sử dụng trong:

• Undo/Redo functionality: Lưu trữ các hành động đã thực hiện vào một stack để có thể hoàn tác (undo). Một stack khác có thể được sử dụng để lưu trữ các hành động đã hoàn tác để có thể làm lại (redo).
• Backtracking: Trong các thuật toán tìm kiếm hoặc giải quyết vấn đề cần quay lui (backtracking), stack có thể giúp lưu trữ các trạng thái trước đó để quay về khi cần.
• Trình biên dịch (Compilers): Sử dụng stack để phân tích cú pháp (parsing) và tạo mã.
• Máy ảo (Virtual Machines): Một số máy ảo (ví dụ: Java Virtual Machine) sử dụng stack để lưu trữ dữ liệu và thực hiện các phép toán.

Bài tập ví dụ:

Thao tác ngăn xếp

Trong một buổi họp về quản lý tài liệu văn phòng, FullHouse Dev được giao nhiệm vụ tối ưu hóa việc sắp xếp tài liệu trong các ngăn xếp. Họ cần tìm ra cách để đạt được hiệu quả cao nhất trong việc di chuyển và sắp xếp lại các tài liệu quan trọng.

Bài toán

FullHouse Dev có một ngăn xếp gồm \(N\) tài liệu được đánh số. Trong một thao tác, họ có thể lấy ra một tài liệu từ đỉnh ngăn xếp hoặc đặt lại một tài liệu đã lấy ra vào đỉnh ngăn xếp. Nhiệm vụ của họ là tối đa hóa giá trị của tài liệu ở đỉnh ngăn xếp sau khi thực hiện đúng \(K\) thao tác. Nếu ngăn xếp trở nên trống rỗng sau \(K\) thao tác và không có cách nào khác để giữ ngăn xếp có tài liệu, in ra -1.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) cách nhau bởi dấu cách.
• Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách biểu thị các phần tử trong ngăn xếp. Phần tử đầu tiên là đỉnh ngăn xếp và phần tử cuối cùng là đáy ngăn xếp.

OUTPUT FORMAT:

• In ra giá trị lớn nhất có thể của phần tử đỉnh ngăn xếp sau khi thực hiện đúng \(K\) thao tác.

Ràng buộc:

• Các giá trị đều là số nguyên dương

Ví dụ

INPUT

6 4
1 2 4 3 3 5

OUTPUT

4

Giải thích

Trong 3 thao tác đầu tiên, FullHouse Dev lấy ra các tài liệu có giá trị 1, 2, 4 và trong thao tác thứ tư, họ đặt lại tài liệu có giá trị 4 vào đỉnh ngăn xếp. Do đó, đáp án là 4.

Hướng dẫn giải bài toán "Thao tác ngăn xếp" bằng C++:

1. Đọc dữ liệu: Đọc hai số nguyên N và K. Đọc N số nguyên tiếp theo vào một cấu trúc dữ liệu phù hợp biểu diễn ngăn xếp ban đầu (ví dụ: std::vector trong C++, với phần tử đầu tiên của vector là đỉnh ngăn xếp).

2. Xử lý trường hợp đặc biệt:

   • Nếu ngăn xếp ban đầu chỉ có 1 phần tử (N = 1) và số thao tác là 1 (K = 1): Bạn chỉ có thể thực hiện thao tác lấy ra phần tử đó, khiến ngăn xếp rỗng. Không thể thực hiện thao tác nào khác để đưa phần tử trở lại đỉnh. Kết quả là -1.

3. Phân tích các trường hợp theo K:

   • Trường hợp K > N: Bạn có đủ số thao tác để lấy ra tất cả N phần tử khỏi ngăn xếp (tốn N thao tác). Khi đó, tất cả các phần tử ban đầu đều "có sẵn" để được đặt lại. Bạn còn lại K - N thao tác. Để tối đa hóa giá trị đỉnh sau đúng K thao tác, bạn có thể dùng thao tác thứ K để đặt phần tử có giá trị lớn nhất trong số N phần tử ban đầu trở lại đỉnh. Các thao tác còn lại (K - N - 1, nếu K - N > 0) có thể được sử dụng để thực hiện các cặp thao tác lấy ra/đặt lại các phần tử khác mà không làm thay đổi trạng thái cuối cùng của ngăn xếp (ngoại trừ phần tử đặt cuối cùng). Điều này luôn khả thi nếu K - N - 1 >= 0 (tức là K > N). Do đó, nếu K > N, kết quả là giá trị lớn nhất trong tất cả N phần tử ban đầu.

   • Trường hợp K <= N: Bạn không có đủ (hoặc chỉ vừa đủ) thao tác để chắc chắn lấy hết tất cả các phần tử. Có hai cách chính để kết thúc với một phần tử ở đỉnh sau K thao tác:

     • Thực hiện đúng K thao tác lấy ra (pop): Điều này chỉ khả thi nếu K <= N. Nếu bạn thực hiện K thao tác lấy ra liên tiếp, ngăn xếp sẽ còn lại N - K phần tử. Phần tử ban đầu ở vị trí thứ K (tính từ đỉnh ban đầu, chỉ số 0) sẽ trở thành đỉnh mới. Nếu K < N, đây là một ứng viên cho giá trị đỉnh lớn nhất: s[K] (với s là vector lưu các phần tử ban đầu, s[0] là đỉnh). Nếu K = N, sau N thao tác lấy ra liên tiếp, ngăn xếp sẽ rỗng, không có đỉnh.

     • Thực hiện một số thao tác lấy ra, và thao tác cuối cùng (thao tác thứ K) là thao tác đặt lại (push): Để đặt lại một phần tử, nó phải là một phần tử đã được lấy ra trước đó. Để tối đa hóa giá trị đỉnh, bạn muốn đặt lại phần tử lớn nhất trong số các phần tử bạn đã lấy ra trong K-1 thao tác đầu tiên. Giả sử bạn lấy ra i+1 phần tử đầu tiên của ngăn xếp ban đầu (tức là các phần tử s[0] đến s[i]), tốn i+1 thao tác. Điều này làm cho các phần tử s[0] đến s[i] có thể được đặt lại. Để có thể đặt lại một trong số chúng bằng thao tác thứ K, bạn cần phải thực hiện i+1 thao tác pop và sau đó còn ít nhất 1 thao tác nữa (thao tác thứ K) để push. Tổng số thao tác là i+1 + (K - (i+1)) = K. Bạn cần i+1 <= K-1 (vì thao tác thứ K là push), tức là i <= K-2. Bạn cũng cần i+1 <= N (vì bạn chỉ có thể pop N lần). Do đó, bạn có thể xem xét việc lấy ra i+1 phần tử ban đầu, với i chạy từ 0 đến min(N-1, K-2). Phần tử có thể được đặt lại (như thao tác thứ K) là giá trị lớn nhất trong số s[0] đến s[i].

     • Kết hợp cho K <= N: Giá trị đỉnh lớn nhất có thể là giá trị lớn nhất giữa:

       • s[K] (nếu K < N, từ k pops).
       • Giá trị lớn nhất của max(s[0]...s[i]) xét trên tất cả i từ 0 đến min(N-1, K-2) (từ việc pop i+1 phần tử đầu tiên và push lại max).

4. Tính toán và Xuất kết quả:

   • Khởi tạo giá trị đỉnh lớn nhất tiềm năng max_val = -1.
   • Nếu K > N, tính giá trị lớn nhất của toàn bộ vector s và gán cho max_val.
   • Nếu K <= N:
     • Nếu K < N, cập nhật max_val = max(max_val, s[K]).
     • Duyệt i từ 0 đến min(N-1, K-2). Trong mỗi bước lặp, tính giá trị lớn nhất của các phần tử từ s[0] đến s[i] (có thể dùng một biến phụ để theo dõi giá trị max trong prefix đang xét) và cập nhật max_val với giá trị này.
   • In ra max_val.

5. Sử dụng thư viện chuẩn C++: Bạn có thể sử dụng std::vector để lưu trữ ngăn xếp ban đầu, std::max hoặc std::max_element để tìm giá trị lớn nhất trong các phần tử hoặc các đoạn con của vector.

Lưu ý: Các chỉ số mảng/vector thường bắt đầu từ 0 trong C++. Đỉnh ngăn xếp ban đầu được mô tả là phần tử đầu tiên, tương ứng với chỉ số 0 trong vector.

Ví dụ N=6, K=4, s = [1, 2, 4, 3, 3, 5]: K=4 <= N=6.

• K < N: max_val = max(-1, s[4]) = max(-1, 3) = 3.
• Loop i từ 0 đến min(6-1, 4-2) = min(5, 2) = 2.
  • i=0: prefix_max = max(-1, s[0]=1) = 1. max_val = max(3, 1) = 3.
  • i=1: prefix_max = max(1, s[1]=2) = 2. max_val = max(3, 2) = 3.
  • i=2: prefix_max = max(2, s[2]=4) = 4. max_val = max(3, 4) = 4. Kết quả: 4.

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