Deque (hàng đợi hai đầu) trong C++

Deque hay còn được gọi là hàng đợi hai đầu

  • Deque (thuờng được phát âm giống như “deck”) là từ viết tắt của double-ended queue (hàng đợi hai đầu).
  • Deque có các ưu điểm như:
  1. Các phần tử có thể truy cập thông cua chỉ số vị trí của nó. O(1)
  2. Chèn hoặc xóa phần tử ở cuối hoặc đầu của dãy. O(1)

Khai báo: #include <deque>

 

Capacity:

  • size : trả về số lượng phần tử của deque. ĐPT O(1).
  • empty : trả về true(1) nếu deque rỗng, ngược lại là false(0). ĐPT O(1).

Truy cập phần tử:

  • operator [] : trả về giá trị phần tử thứ []. ĐPT O(1).
  • at : tương tự như trên. ĐPT O(1).
  • front: trả về giá trị phần tử đầu tiên. ĐPT O(1).
  • back: trả về giá trị phần tử cuối cùng. ĐPT O(1).

 

Chỉnh sửa:

  • push_back : thêm phần tử vào ở cuối deque. ĐPT O(1).
  • push_front : thêm phần tử vào đầu deque. ĐPT O(1).
  • pop_back : loại bỏ phần tử ở cuối deque. ĐPT O(1).
  • pop_front : loại bỏ phần tử ở đầu deque. ĐPT O(1).
  • insert (iterator,x): chèn “x” vào trước vị trí “iterator” ( x có thể là phần tử hay iterator của 1 đoạn phần tử…). ĐPT O(n).
  • erase : xóa phần tử ở vị trí iterator. ĐPT O(n).
  • swap : đổi 2 deque cho nhau (ví dụ: first.swap(second);). ĐPT O(n). clear: xóa vector. ĐPT O(1).
Khuyên dùng

 

Speak Your Mind

*