Chuyển tới nội dung chính

std::stack

#include <stack>

template <class T, class Container = std::deque<T>> class stack;

std::stack trong C++ là một container adaptor (bộ điều hợp chứa), cung cấp giao diện của một ngăn xếp (stack). Ngăn xếp là một cấu trúc dữ liệu hoạt động theo nguyên tắc LIFO (Last-In, First-Out), nghĩa là phần tử được thêm vào cuối cùng sẽ là phần tử được lấy ra đầu tiên.

Tham số​

T​

  • Kiểu dữ liệu của các phần tử trong stack.

Container​

  • Container underlying được sử dụng để lưu trữ các phần tử. Mặc định là std::deque<T>, nhưng bạn cũng có thể sử dụng std::vector<T> hoặc std::list<T>.

stack​

  • Tên của stack bạn muốn tạo.

Đặc điểm​

  1. LIFO (Last-In, First-Out): Phần tử được thêm vào cuối cùng sẽ là phần tử được lấy ra đầu tiên.
  2. Container Adaptor: std::stack không phải là một container độc lập, mà là một container adaptor. Nó sử dụng một container khác (mặc định là std::deque) để lưu trữ các phần tử.
  3. Hạn chế truy cập: Bạn chỉ có thể truy cập phần tử ở đỉnh của stack (thông qua top()). Không thể truy cập ngẫu nhiên các phần tử bên trong.
  4. Không có iterator: std::stack không cung cấp iterator để duyệt qua các phần tử.
  5. Các thao tác chính: push() (thêm vào đỉnh), pop() (xóa khỏi đỉnh), top() (truy cập đỉnh), empty() (kiểm tra rỗng), size() (lấy kích thước).
  6. Ưu điểm:
    • Thực hiện cấu trúc dữ liệu ngăn xếp một cách dễ dàng.
    • Các thao tác push(), pop(), top() có độ phức tạp O(1).
    • Dễ sử dụng và hiểu.
  7. Nhược điểm:
    • Hạn chế quyền truy cập, chỉ thao tác được với phần tử ở đỉnh.
    • Không hỗ trợ duyệt qua các phần tử.
  8. Khi nào nên sử dụng std::stack:
    • Khi bạn cần một cấu trúc dữ liệu hoạt động theo nguyên tắc LIFO.
    • Khi bạn cần giải quyết các bài toán như:
      • Kiểm tra dấu ngoặc.
      • Chuyển đổi biểu thức trung tố sang hậu tố.
      • Undo/Redo trong các ứng dụng.
      • Quản lý stack trong các chương trình đệ quy.

Ví dụ:​

#include <iostream>
#include <stack>
#include <vector>

int main() {
  // 1. Khởi tạo stack rỗng
  std::stack<int> stack1;

  // 2. Khởi tạo stack với container underlying là std::vector
  std::stack<int, std::vector<int>> stack2;

  // 3. Thêm phần tử vào stack
  stack1.push(10);
  stack1.push(20);
  stack1.push(30);

  // 4. Lấy phần tử trên cùng của stack (không xóa)
  std::cout << "stack1.top(): " << stack1.top() << '\n'; // Output: stack1.top(): 30

  // 5. Xóa phần tử trên cùng của stack
  stack1.pop();

  // 6. Kiểm tra stack rỗng
  if (stack1.empty()) {
    std::cout << "stack1 is empty\n";
  } else {
    std::cout << "stack1 is not empty\n"; // Output: stack1 is not empty
  }

  // 7. Lấy kích thước stack
  std::cout << "stack1.size(): " << stack1.size() << '\n'; // Output: stack1.size(): 2

  // 8. Hoán đổi nội dung của 2 stack (C++11)
  std::stack<int> stack3;
  stack3.push(1);
  stack3.push(2);
  
  stack1.swap(stack3);
  
  std::cout << "stack1: ";
  while (!stack1.empty()) {
    std::cout << stack1.top() << " ";
    stack1.pop();
  }
  std::cout << '\n'; // Output: stack1: 2 1

  std::cout << "stack3: ";
  while (!stack3.empty()) {
    std::cout << stack3.top() << " ";
    stack3.pop();
  }
  std::cout << '\n'; // Output: stack3: 20 10

  // 9. Sử dụng emplace (C++11)
  std::stack<std::pair<int, int>> stack4;
  stack4.emplace(1, 2);
  stack4.emplace(3, 4);
  std::cout << "stack4.top().second: " << stack4.top().second << '\n'; // Output: stack4.top().second: 4
  
  return 0;
}

Các cách phổ biến khai báo và khởi tạo một std::stack​

lưu ý
  • std::stack là một container adaptor, nó không tự lưu trữ các phần tử. Nó sử dụng một container khác (mặc định là std::deque) để lưu trữ.
  • Bạn không thể khởi tạo std::stack trực tiếp từ initializer_list.
  • Khi khởi tạo std::stack từ một container khác, các phần tử sẽ được sao chép (hoặc di chuyển) vào container underlying của std::stack theo thứ tự đảo ngược để đảm bảo tính chất LIFO của stack.

  1. Khai báo một std::stack rỗng (sử dụng container mặc định std::deque):​

    #include <stack>

    std::stack<int> stack1; // stack rỗng, kiểu int, sử dụng std::deque làm container underlying

  2. Khai báo một std::stack rỗng với container underlying cụ thể:​

    #include <stack>
    #include <vector>
    #include <list>

    std::stack<int, std::vector<int>> stack2; // stack rỗng, kiểu int, sử dụng std::vector
    std::stack<float, std::list<float>> stack3; // stack rỗng, kiểu float, sử dụng std::list

  3. Khởi tạo std::stack từ một container khác (copy):​

    Bạn không thể trực tiếp khởi tạo một std::stack từ một container khác bằng copy constructor. Bạn cần phải tạo một container underlying trước, sau đó khởi tạo std::stack từ container đó. 
    #include <stack>
    #include <vector>
    #include <deque>

    int main() {
      std::vector<int> vec = {1, 2, 3, 4, 5};
      std::deque<int> deq = {5,4,3,2,1};
        
      std::stack<int, std::vector<int>> stack4(vec); // Khởi tạo stack từ vector (copy)
      std::stack<int> stack5(deq); // Khởi tạo stack từ deque mặc định (copy)

      std::cout << "stack4: ";
      while (!stack4.empty()) {
          std::cout << stack4.top() << " ";
          stack4.pop();
      }
      std::cout << std::endl;

      std::cout << "stack5: ";
      while (!stack5.empty()) {
          std::cout << stack5.top() << " ";
          stack5.pop();
      }
      std::cout << std::endl;

      return 0;
    }

  4. Khởi tạo std::stack từ một container khác (move - C++11):​

    Tương tự như copy, bạn không thể trực tiếp move, bạn cần thông qua container underlying 
    #include <stack>
    #include <vector>
    #include <deque>

    int main() {
      std::vector<int> vec = {1, 2, 3, 4, 5};
      std::deque<int> deq = { 5,4,3,2,1 };

      std::stack<int, std::vector<int>> stack6(std::move(vec)); // Khởi tạo stack từ vector (move)
      std::stack<int> stack7(std::move(deq)); // Khởi tạo stack từ deque mặc định (move)
      
        std::cout << "stack6: ";
        while (!stack6.empty()) {
            std::cout << stack6.top() << " ";
            stack6.pop();
        }
        std::cout << std::endl;

        std::cout << "stack7: ";
        while (!stack7.empty()) {
            std::cout << stack7.top() << " ";
            stack7.pop();
        }
        std::cout << std::endl;

      return 0;
    }

Các kiểu dữ liệu của std::stack​

lưu ý

std::stack là một container adaptor, nó không trực tiếp lưu trữ dữ liệu mà dựa vào underlying container. Do đó, std::stack có thể chứa bất kỳ kiểu dữ liệu nào mà underlying container hỗ trợ, miễn là kiểu dữ liệu đó thỏa mãn các yêu cầu sau:

  • CopyAssignable (có thể gán bằng sao chép): push() có thể sử dụng đến.
  • MoveAssignable (có thể gán bằng di chuyển, từ C++11): push() và emplace() có thể sử dụng đến.
  • Destructible (có thể hủy): Cần thiết để giải phóng bộ nhớ khi các phần tử bị xóa khỏi stack.
  • EqualityComparable (có thể so sánh bằng, nếu sử dụng toán tử == hoặc !=): Để so sánh 2 stack với nhau.
  • LessThanComparable (có thể so sánh nhỏ hơn, nếu sử dụng các toán tử <, <=, >, >=): Để so sánh 2 stack với nhau.
  1. Các kiểu dữ liệu cơ bản:
    int, float, double, char, bool, long, short,...
  2. Con trỏ:
    int*, char*, MyClass*,...
  3. Các kiểu dữ liệu chuẩn:
    std::string, std::vector, std::list, std::map, std::set, std::pair, std::tuple,...
  4. Các kiểu dữ liệu do người dùng định nghĩa (Classes và Structs):
    Với điều kiện các kiểu dữ liệu này phải thỏa mãn các yêu cầu CopyAssignable/MoveAssignable và Destructible như đã đề cập ở trên.
  5. Smart pointers:
    std::unique_ptr, std::shared_ptr

Các hàm thành viên​

emptyKiểm tra xem std::stack có rỗng hay không
sizeTrả về số lượng phần tử hiện có trong std::stack
topTrả về tham chiếu đến phần tử ở đỉnh của std::stack
pushThêm một phần tử mới vào đỉnh của std::stack
emplaceXây dựng (construct) một phần tử mới trực tiếp tại đỉnh của std::stack
popXóa phần tử ở đỉnh của std::stack
swapHoán đổi nội dung của hai std::stack với nhau

Toán tử quan hệCác toán tử quan hệ trong std::stack
Cập nhật lần cuối vào bởi yutijang

 2025 © cppDocs. Built with Docusaurus.