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

std::queue

#include <queue>

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

std::queue trong C++ là một container adaptor (bộ điều hợp chứa), cung cấp giao diện của một hàng đợi (queue). Hàng đợi là một cấu trúc dữ liệu hoạt động theo nguyên tắc FIFO (First-In, First-Out), nghĩa là phần tử được thêm vào đầu tiên 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 queue.

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::list<T>.
  • std::vector không phù hợp để làm underlying container cho std::queue vì nó không hỗ trợ pop_front() hiệu quả.

queue​

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

Đặc điểm​

  1. FIFO (First-In, First-Out): Phần tử được thêm vào đầu tiên sẽ là phần tử được lấy ra đầu tiên.
  2. Container Adaptor: std::queue 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ử ở đầu (front) và cuối (back) của queue. Không thể truy cập ngẫu nhiên các phần tử bên trong.
  4. Không có iterator: std::queue 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 cuối), pop() (xóa khỏi đầu), front() (truy cập đầu), back() (truy cập cuối), 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 hàng đợi một cách dễ dàng.
    • Các thao tác push(), pop(), front(), back() có độ phức tạp O(1).
  7. Nhược điểm:
    • Hạn chế quyền truy cập, chỉ thao tác được với phần tử ở đầu và cuối.
    • Không hỗ trợ duyệt qua các phần tử.
  8. Khi nào nên sử dụng std::queue:
    • Khi bạn cần một cấu trúc dữ liệu hoạt động theo nguyên tắc FIFO.
    • Khi bạn cần giải quyết các bài toán như:
      • Mô phỏng hàng đợi trong thực tế (ví dụ: hàng đợi chờ phục vụ).
      • Xử lý các tác vụ theo thứ tự ưu tiên (với std::priority_queue).
      • Bộ đệm (buffer) cho việc truyền dữ liệu.

Ví dụ:​

#include <iostream>
#include <queue>
#include <list>

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

  // 2. Khởi tạo queue với container underlying là std::list
  std::queue<int, std::list<int>> queue2;

  // 3. Thêm phần tử vào queue (cuối hàng đợi)
  queue1.push(10);
  queue1.push(20);
  queue1.push(30);

  // 4. Lấy phần tử đầu tiên của queue (không xóa)
  std::cout << "queue1.front(): " << queue1.front() << '\n'; // Output: queue1.front(): 10

  // 5. Xóa phần tử đầu tiên của queue
  queue1.pop();

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

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

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

  std::cout << "queue3: ";
  while (!queue3.empty()) {
    std::cout << queue3.front() << " ";
    queue3.pop();
  }
  std::cout << '\n'; // Output: queue3: 20 30

  // 9. Sử dụng emplace (C++11)
  std::queue<std::pair<int, int>> queue4;
  queue4.emplace(1, 2);
  queue4.emplace(3, 4);
  std::cout << "queue4.back().second: " << queue4.back().second << '\n'; // Output: queue4.back().second: 4

  return 0;
}

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

lưu ý
  • std::queue 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::queue trực tiếp từ initializer_list.
  • Khi khởi tạo std::queue 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::queue theo thứ tự giữ nguyên để đảm bảo tính chất FIFO của queue.
  • std::vector không phải là lựa chọn tốt để làm underlying container cho std::queue vì std::vector không hỗ trợ thao tác pop_front() hiệu quả (độ phức tạp O(n)).

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

    #include <queue>

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

  2. Khai báo một std::queue rỗng với container underlying cụ thể (ví dụ: std::list):​

    #include <queue>
    #include <list>

    std::queue<int, std::list<int>> queue2; // queue rỗng, kiểu int, sử dụng std::list

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

    Giống như std::stack, bạn không thể trực tiếp khởi tạo một std::queue 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::queue từ container đó. 
    #include <queue>
    #include <deque>
    #include <list>

    int main() {
      std::deque<int> deq = {1, 2, 3, 4, 5};
      std::list<int> list = {6,7,8,9,10};
        
      std::queue<int> queue3(deq);             // Khởi tạo queue từ deque (copy)
      std::queue<int, std::list<int>> queue4(list);  // Khởi tạo queue từ list (copy)

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

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

      return 0;
    }

  4. Khởi tạo std::queue 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 <queue>
    #include <deque>
    #include <list>

    int main() {
      std::deque<int> deq = {1, 2, 3, 4, 5};
      std::list<int> list = { 6,7,8,9,10 };

      std::queue<int> queue5(std::move(deq));             // Khởi tạo queue từ deque (move)
      std::queue<int, std::list<int>> queue6(std::move(list));  // Khởi tạo queue từ list (move)

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

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

      return 0;
    }

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

lưu ý

std::queue 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::queue 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 queue.
  • EqualityComparable (có thể so sánh bằng, nếu sử dụng toán tử == hoặc !=): Để so sánh 2 queue 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 queue 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::queue có rỗng hay không
sizeTrả về số lượng phần tử hiện có trong std::queue
frontTrả về tham chiếu đến phần tử ở đầu của std::queue
backTrả về tham chiếu đến phần tử ở cuối của std::queue
pushThêm một phần tử mới vào cuối std::queue
emplaceXây dựng (construct) một phần tử mới trực tiếp tại cuối của std::queue
popXóa phần tử ở đầu của std::queue
swapHoán đổi nội dung của hai std::queue với nhau

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

 2025 © cppDocs. Built with Docusaurus.