[Tutorial] Thư viện STL trong C++ : Deque

Giới thiệu về deque:

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 tương tự như vector nhưng ta có thể thao tác thêm hoặc loại phần tử ở cả hai đầu của danh sách.

Deque có các ưu điểm như:

  • Các phần tử có thể truy cập thông của chỉ số vị trí của nó.(Tương tự như vector).
  • Chèn hoặc xóa phần tử ở cuối hoặc đầu của dãy. (Vector chỉ chèn hoặc xóa phần tử ở cuối dãy).

Khai báo deque:

Ta cần khai báo thư viện deque:

Các phương thức thành viên:

Các phương thức thành viên của deque tương tự như vector, chỉ thêm 2 phương thức push_front(const x) và pop_front() để thao tác cả hai đầu của danh sách.

Capacity:
size() Trả về số lượng phần tử
empty() Trả về true(1) nếu deque rỗng, ngược lại là false (0)
Element access:  
operator [int i] Truy cập giá trị phần tử thứ i của deque, tương tự như đối mảng thông thường
at(int i) Truy cập phần tử thứ i của deque
front() Truy cập phần tử đầu tiên của deque
back() Truy cập phần tử cuối cùng của deque
Modifier:
push_back(const x) Thêm phần tử có giá trị x vào cuối deque
push_front(const x) Thêm phần tử có giá trị x vào đầu deque
pop_back() Loại bỏ phần tử cuối ra khỏi deque
pop_front() Loại bỏ phần tử đầu ra khỏi deque
insert (iterator positon,const x)insert (iterator positon,int n, const x)

 

insert (iterator positon,iterator a, itertator b)

 

Chèn phần tử có giá trị x vào trước vị trí position.Chèn n phần tử có giá trị x vào trước vị trí position.Chèn vào trước vị trí position tất cả các phần tử trong nửa khoảng [a,b) của một deque khác.
erase (iterator position)erase (iterator first, iterator last)

 

Xóa phần tử ở vị trí positionXóa tất cả các phần tử trong nửa khoảng [first,last), tức là từ phần tử thứ first đến phần tử thứ (last-1)
swap(vector v) Hoán đổi các phần tử của deque hiện hành và vector v
clear() Xóa deque

Capacity:

size():

Trả về số lượng phần tử của deque.

Ví dụ: Tạo một deque có kích thước là 10 và in ra số lượng phần tử của deque này.

Ta có thể dùng phương thức size() để truy xuất các phần tử của deque khi chưa biết kích thước của deque, ví dụ:

empty()

Trả về true(1) nếu deque rỗng, ngược lại là false (0)

Ví dụ: Kiểm tra deque có rỗng không và  in ra thông báo tương ứng.

Element access

operator [ ] :

Sử dụng [ ] để truy cập phần tử tương tự như đối với mảng thông thường.

Ví dụ: Tạo một deque 10 phần tử với giá các phần tử  lần lượt là  từ 0 đến 9. In ra các phần tử của deque

Lưu ý: Ở chương trình trên, trong vòng lặp đầu tiên, ta không thể dùng myDeque[i] =i thay cho lệnh myDeque.push_back(i) vì ta khai báo câu lệnh:

chưa xác định kích thước của deque.

Nếu ta muốn dùng myDeque[i] =i thay cho lệnh myDeque.push_back(i) thì ta phải thay đổi cách khai báo deque.

Ta có thể thay đổi câu lệnh deque<int> myDeque; thành  deque<int> myDeque(10) ;

at (int i)

Truy cập phần tử thứ i trong deque.

Phương thức at() có chức năng tương tự như operator [] .

Ví dụ: Tạo deque có 10 phần tử bao gồm 0, 10, 20, 30 , 40, 50, 60, 70, 80, 90. Sau đó, sử dụng phương thức at() để in giá trị các phần tử.

front()

Truy xuất phần tử đầu tiên của deque. Truy xuất ở đây bao gồm in hoặc chỉnh sửa giá trị.

Ví dụ: Tạo deque có 5 phần tử có giá trị lần lượt là a,b,c,d,e. Thay đổi phẩn tử đầu tiền thành ‘A’ và in ra kết quả.

back()

Truy xuất phần tử cuối cùng của deque. Truy xuất ở đây bao gồm in hoặc chỉnh sửa giá trị.

Ví dụ: Tạo deque có 5 phần tử có giá trị lần lượt là  A,B,C,D,E. Thay đổi phẩn tử cuối cùng thành ‘e’ và in ra kết quả.

Modifier

push_back(const x)

Thêm phần tử có giá trị x vào cuối deque.

queue-push_back

Phương thức push_back(x) thường dùng để khởi tạo deque một cách “động”, có nghĩa là kích thước deque chưa xác định trước.

Ví dụ: Viết chương trình cho người dùng nhập vào kích thước deque và nhập vào giá trị các phần tử. In ra các phần tử trong deque.

push_front(const x):

Thêm phần tử có giá trị x vào đầu deque.

deque - push_font

 

Ví dụ: Khởi tạo deque có các phần tử là kí tự lần lượt theo thứ tự là ‘B’,’C’,’D’,’E’. Thêm phần tử ‘A’ vào đầu danh sách. In các phần tử theo đúng thứ tự lưu trữ.

pop_back()

Loại bỏ phần tử cuối ra khỏi deque.

deque-pop_back

Ví dụ: Viết chương trình cho người dùng nhập vào kích thước deque và nhập vào giá trị các phần tử. Sau đó, loại bỏ đi một nửa các phần tử ở cuối deque.  In ra các phần tử trong deque.

pop_front()

Loại bỏ phần tử đầu tiên ra khỏi deque.

deque-pop_front

Ví dụ: Tạo danh sách có 5 phần tử lần lượt theo thứ tự là ‘a’,’b’,’c’,’d’,’e’. Loại bỏ phần tử đâu tiên ra khỏi deque và in ra màn hình các phần tử còn lại.

Lưu ý:

Việc dùng pop_back() chỉ dịch chuyển con trỏ end() về phía trước. Điều này có nghĩa là giá trị của các phần tử cuối deque sau khi dùng lệnh pop_back() vẫn còn lưu trữ. Cụ thể, trong chương trình trên, ở vòng lặp for cuối cùng, nếu ta thay đổi:

thành :

 

thì ta thấy giá trị các phần tử ta nhập ban đâu vẫn còn lưu lại.

insert

Insert có thể dùng với 3 cách sau:

insert (iterator positon,const x): Chèn phần tử có giá trị x vào trước vị trí position.

insert (iterator positon,int n, const x): Chèn n phần tử có giá trị x vào trước vị trí position.

insert (iterator positon,iterator a, itertator b): Chèn vào trước vị trí position của deque hiện hành tất cả các phần tử trong nửa khoảng [a,b) của một deque khác.

Ví dụ 1: Tạo deque có 5 phần tử đều có giá trị là 100. Chèn phần tử có giá trị 200 vào vị trí thứ 2 của deque.

Ví dụ 2: Tạo deque có 5 phần tử đều có giá trị là 100. Chèn 2 phần tử có giá trị 200 vào vị trí đầu tiên của deque.

Ví dụ 3: Tạo deque thứ nhất có 5 phần tử đều có giá trị là 100. Tạo deque thứ hai có 3 phần tử đều có giá trị là 200. Chèn tất cả các phần tử của deque thứ hai vào vị trí thứ 2 của deque thứ nhất.

Lưu ý: ngoài việc chèn deque này vào deque khác, ta có thể chèn một mảng các phần tử vào deque.

Ví dụ 4: tạo một deque có 5 phần tử đều có giá trị là 100. Tạo một mảng int có 3 phần tử lần lượt là 200, 300, 400. Chèn 2 phần tử đầu của mảng vào đầu deque.

erase

Phương thức erase có 2 cách dùng:

erase (iterator position): Xóa phần tử ở vị trị position

erase (iterator first, iterator last): Xóa tất cả các phần tử trong nửa khoảng [frist,last), có nghĩa là từ phẩn tử thứ first đến phần tử thứ (last-1).

Ví dụ 1: Tạo một deque có 10 phần tử có giá trị từ 1 đến 10. Xóa phần tử thứ 6 và in ra các phần tử còn lại.

Ví dụ 2: Tạo một deque có 10 phần tử có giá trị từ 1 đến 10. Xóa  3 phần tử ở đầu deque.

swap(deque v)

Hoán đổi deque v với deque hiện hành.

Ví dụ: Cho hai deque, deque thứ nhất có 5 phần tử đều là số 1, deque thứ hai có 5 phần tử đều là số 2. Hoán đổi hai deque trên và in ra các phần tử của mỗi deque.

clear()

Xóa hoàn toàn một deque.

Ví dụ: Tạo một deque có 5 phần tử đều có giá trị là 5. In kích thước của deque trước và sau khi dùng phương thức clear()

Lưu ý: phương thức clear() chỉ làm làm cho kích thước của deque về 0. Tuy nhiên, giá trị mà deque lưu trữ vẫn còn. Cụ thể, trong ví dụ trên, nếu ta thêm vào cuối chương trình câu lệnh:

thì ta thấy kết quả vẫn in ra được các giá trị các phần tử của deque.

Share
Share