Deque (Double-ended queue) về cơ bản là sự khái quát hóa của cấu trúc stack (ngăn xếp) và queue (hàng đợi), nơi nó được khởi tạo từ trái sang phải. Nó sử dụng đối tượng list để tạo deque. Nó cung cấp độ phức tạp thời gian O(1) cho các thao tác pop (lấy ra) và append (thêm vào).
Deque là một lớp thư viện chuẩn, nằm trong module collections.
Để sử dụng, trước tiên cần nhập module collections:
import collections
Phần này sẽ trình bày một số hàm của lớp Deque.
Các hàm thêm phần tử (Appending) trên Deque
Có hai loại append khác nhau. Phương thức append() dùng để thêm phần tử vào đầu phải của hàng đợi, và phương thức appendleft() dùng để thêm phần tử vào đầu trái của hàng đợi.
Mã ví dụ
import collections as col
# Chèn một số phần tử vào hàng đợi ban đầu
my_deque = col.deque('124dfre')
print('Dequeue: ' + str(my_deque))
# Chèn x ở phải và B ở trái
my_deque.append('x')
my_deque.appendleft('B')
print('Dequeue sau khi append: ' + str(my_deque))
Kết quả
Dequeue: deque(['1', '2', '4', 'd', 'f', 'r', 'e']) Dequeue sau khi append: deque(['B', '1', '2', '4', 'd', 'f', 'r', 'e', 'x'])
Các hàm lấy phần tử (Popping) trên Deque
Giống như append, có hai loại hàm pop. Phương thức pop() dùng để xóa và trả về phần tử ở cuối bên phải, và popleft() dùng để xóa và trả về phần tử ở cuối bên trái.
Mã ví dụ
import collections as col
# Chèn một số phần tử vào hàng đợi ban đầu
my_deque = col.deque('124dfre')
print('Dequeue: ' + str(my_deque))
# Xóa phần tử từ phải và trái
item = my_deque.pop()
print('Phần tử popped: ' + str(item))
item = my_deque.popleft()
print('Phần tử popped: ' + str(item))
print('Dequeue sau các thao tác pop: ' + str(my_deque))
Kết quả
Dequeue: deque(['1', '2', '4', 'd', 'f', 'r', 'e']) Phần tử popped: e Phần tử popped: 1 Dequeue sau các thao tác pop: deque(['2', '4', 'd', 'f', 'r'])
Các hàm liên quan đến phần tử trong Deque
Một số hàm trong Deque dùng để lấy thông tin liên quan đến phần tử. Có các hàm như index(), count(), v.v. Phương thức index() dùng để lấy chỉ mục của lần xuất hiện đầu tiên của một phần tử. Khi không truyền đối số cùng với phần tử, nó sẽ chọn toàn bộ danh sách; khi giới hạn cụ thể được chỉ định, nó kiểm tra chỉ mục trong giới hạn đó. Ngược lại, phương thức count() đếm tần suất xuất hiện của một mục trong Deque.
Mã ví dụ
import collections as col
# Chèn một số phần tử vào hàng đợi ban đầu
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))
# Tìm chỉ mục của D
print('Chỉ mục của D: ' + str(my_deque.index('D')))
print('Chỉ mục của D trong khoảng 5 đến 8: ' + str(my_deque.index('D', 5, 8)))
# Đếm số lần xuất hiện
print('Số lần xuất hiện của A: ' + str(my_deque.count('A')))
print('Số lần xuất hiện của D: ' + str(my_deque.count('D')))
Kết quả
Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D']) Chỉ mục của D: 4 Chỉ mục của D trong khoảng 5 đến 8: 5 Số lần xuất hiện của A: 2 Số lần xuất hiện của D: 3
Hàm insert() và remove() trong Deque
Chúng ta đã thấy các hàm append và pop trong Deque để chèn và xóa phần tử tương ứng. Có hai phương thức khác liên quan đến chèn và xóa. Phương thức insert() dùng để chèn một phần tử tại vị trí chỉ định (cung cấp chỉ mục). Và phương thức remove() dùng để xóa lần xuất hiện đầu tiên của một phần tử.
Mã ví dụ
import collections as col
# Chèn một số phần tử vào hàng đợi ban đầu
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))
# Chèn chữ G và H vào vị trí 5, 7 tương ứng
my_deque.insert(5, 'G')
my_deque.insert(7, 'H')
print('Dequeue sau khi chèn: ' + str(my_deque))
# Xóa lần xuất hiện đầu tiên của chữ D
my_deque.remove('D')
print('Dequeue sau khi xóa: ' + str(my_deque))
Kết quả
Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D']) Dequeue sau khi chèn: deque(['A', 'A', 'B', 'C', 'D', 'G', 'D', 'H', 'E', 'F', 'D']) Dequeue sau khi xóa: deque(['A', 'A', 'B', 'C', 'G', 'D', 'H', 'E', 'F', 'D'])
Các hàm mở rộng (Extending) trong Deque
Các hàm mở rộng dùng để thêm nhiều phần tử vào Deque. Chúng ta có thể dùng các collection như list, tuple để cung cấp nhiều giá trị. Có hai loại hàm mở rộng. Phương thức extend() thêm phần tử vào bên phải, tương tự như gọi lặp lại append(). Và phương thức extendleft() thêm phần tử vào bên trái, tương tự như gọi lặp lại appendleft().
Mã ví dụ
import collections as col
# Chèn một số phần tử vào hàng đợi ban đầu
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))
# Mở rộng bằng cách thêm 1, 3, 5, 7 vào phải và x, y, z vào trái
my_deque.extend([1, 3, 5, 7])
my_deque.extendleft(['x', 'y', 'z'])
print('Dequeue sau khi Extending: ' + str(my_deque))
Kết quả
Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D']) Dequeue sau khi Extending: deque(['z', 'y', 'x', 'A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D', 1, 3, 5, 7])
Các hàm đảo ngược (Reversing) và xoay (Rotating) trong Deque
Chúng ta có thể đảo ngược trình tự của deque bằng phương thức reverse(). Có phương thức khác gọi là rotate(). Sử dụng rotate, deque có thể được xoay với số lượng chỉ định làm đối số. Nếu đối số dương, nó xoay sang phải; nếu số âm, xoay sang trái.
Mã ví dụ
import collections as col
# Chèn một số phần tử vào hàng đợi ban đầu
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))
my_deque.reverse()
print('Deque sau khi Reversing: ' + str(my_deque))
# Xoay sang phải, 3 phần tử
my_deque.rotate(3)
print('Deque sau khi rotating: ' + str(my_deque))
Kết quả
Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D']) Deque sau khi Reversing: deque(['D', 'F', 'E', 'D', 'D', 'C', 'B', 'A', 'A']) Deque sau khi rotating: deque(['B', 'A', 'A', 'D', 'F', 'E', 'D', 'D', 'C'])