Deque trong Python

Trong Python, deque là cấu trúc dữ liệu giống stack và queue. Nó cho phép thêm và xóa (append/pop) từ cả hai đầu của hàng đợi. Điều này làm cho nó khác biệt với các cấu trúc dữ liệu khác. Có nhiều phép toán áp dụng cho deque. Trong bài viết này, xem ví dụ cho từng phép toán. Module collections được dùng để triển khai deque.

Các phép toán Deque

Dưới đây là một số phép toán hữu ích dùng deque:

• append() - Chèn giá trị tham số vào cuối bên phải của deque.
• appendleft() - Chèn giá trị tham số vào cuối bên trái của deque.
• pop() - Xóa phần tử từ cuối bên phải của deque.
• popleft() - Xóa phần tử từ cuối bên trái của deque.
• extend(iterable) - Thêm nhiều giá trị vào cuối bên phải của deque. Tham số là iterable.
• extendleft(iterable) - Thêm nhiều giá trị vào cuối bên trái của deque. Tham số là iterable. Thứ tự bị đảo ngược do appendleft.
• reverse() - Đảo ngược thứ tự các phần tử deque.
• rotate() - Xoay deque theo số chỉ định trong tham số. Nếu số âm, xoay trái. Ngược lại xoay phải.

Ví dụ

Chương trình dưới cho thấy cách triển khai các phép toán trên dùng deque và module collections.

import collections
de = collections.deque([10, 20, 30, 40])
print(de)
de.append(50)
print("\nThêm vào phải deque là : ")
print(de)
de.appendleft(60)
print("\nThêm vào trái deque là : ")
print(de)
de.pop()
print("\nXóa từ phải deque là: ")
print(de)
de.popleft()
print("\nXóa từ trái deque là: ")
print(de)
de.extend([70, 80])
print("\nMở rộng deque ở cuối là : ")
print(de)
de.extendleft([100, 90])
print("\nMở rộng deque ở đầu là : ")
print(de)
de.rotate(-2)
print("\nXoay deque là : ")
print(de)
de.reverse()
print("\nĐảo ngược deque là : ")
print(de)

Kết quả

Chạy đoạn code trên cho kết quả sau:

deque([10, 20, 30, 40])
Thêm vào phải deque là : deque([10, 20, 30, 40, 50])
Thêm vào trái deque là : deque([60, 10, 20, 30, 40, 50])
Xóa từ phải deque là: deque([60, 10, 20, 30, 40])
Xóa từ trái deque là: deque([10, 20, 30, 40])
Mở rộng deque ở cuối là : deque([10, 20, 30, 40, 70, 80])
Mở rộng deque ở đầu là : deque([90, 100, 10, 20, 30, 40, 70, 80])
Xoay deque là : deque([10, 20, 30, 40, 70, 80, 90, 100])
Đảo ngược deque là : deque([100, 90, 80, 70, 40, 30, 20, 10])