Deque trong Python

Deque là viết tắt của Double-Ended Queue. Đây là một cấu trúc dữ liệu cho phép thêm và xóa các phần tử từ cả hai đầu một cách hiệu quả. Không giống như các hàng đợi thông thường, thường được vận hành theo nguyên tắc FIFO (First In, First Out), deque hỗ trợ cả hoạt động FIFO và LIFO (Last In, First Out).

Ví dụ:

from collections import deque 
    
# khai báo deque 
de = deque(['name','age','DOB'])  
    
print(de)

Đầu ra

deque(['name', 'age', 'DOB'])

Các loại đầu vào Deque bị hạn chế

• Deque hạn chế đầu vào : Đầu vào bị giới hạn ở một đầu trong khi được phép xóa ở cả hai đầu.

• Deque bị hạn chế đầu ra : đầu ra bị giới hạn ở một đầu nhưng được phép chèn ở cả hai đầu.

Các hoạt động trên deque 

Sau đây là bảng liệt kê các hoạt động tích hợp của deque trong Python kèm theo mô tả và độ phức tạp thời gian tương ứng của chúng:

Thêm và xóa các mục Dequeue

• append(x): Thêm x vào cuối bên phải của deque.

• appendleft(x): Thêm x vào đầu bên trái của deque.

• extend(iterable): Thêm tất cả các phần tử từ iterable vào đầu bên phải.

• extendleft(iterable): Thêm tất cả các phần tử từ iterable vào đầu bên trái (theo thứ tự ngược lại).

• remove(value): Xóa lần xuất hiện đầu tiên của giá trị được chỉ định khỏi deque. Nếu không tìm thấy giá trị, nó sẽ đưa ra ValueError.

• pop(): Xóa và trả về một phần tử ở phía bên phải.

• popleft(): Xóa và trả về một phần tử ở phía bên trái.

• clear(): Xóa tất cả các phần tử khỏi deque.

from collections import deque

# Tạo một deque với các phần tử ban đầu
dq = deque([10, 20, 30])

# Thêm phần tử vào bên phải (cuối hàng)
dq.append(40)  

# Thêm phần tử vào bên trái (đầu hàng)
dq.appendleft(5)  

# extend(iterable) – thêm nhiều phần tử vào bên phải
dq.extend([50, 60, 70]) 
print("Sau extend([50, 60, 70]):", dq)

# extendleft(iterable) – thêm nhiều phần tử vào bên trái (lưu ý: theo thứ tự ngược lại)
dq.extendleft([0, 5])  
print("Sau extendleft([0, 5]):", dq)

# Xóa phần tử cụ thể (đầu tiên gặp)
dq.remove(20)
print("Sau remove(20):", dq)

# Xóa phần tử ở bên phải (cuối hàng)
dq.pop()

# Xóa phần tử ở bên trái (đầu hàng)
dq.popleft()  

print("Sau pop và popleft:", dq)

# clear() – Xóa toàn bộ phần tử khỏi deque
dq.clear()  
print("Sau clear():", dq)

Đầu ra:

Sau extend([50, 60, 70]): deque([5, 10, 20, 30, 40, 50, 60, 70]) 
Sau extendleft([0, 5]): deque([5, 0, 5, 10, 20, 30, 40, 50, 60, 70]) 
Sau remove(20): deque([5, 0, 5, 10, 30, 40, 50, 60, 70]) 
Sau pop và popleft: deque([0, 5, 10, 30, 40, 50, 60]) 
Sau clear(): deque([])

Truy cập mục và độ dài của deque

• Lập chỉ mục: Truy cập các phần tử theo vị trí bằng cách sử dụng chỉ mục dương hoặc âm.

• len(): Trả về số lượng phần tử trong deque.

import collections

dq = collections.deque([1, 2, 3, 3, 4, 2, 4])

# Truy cập các phần tử theo chỉ mục
print(dq[0])  
print(dq[-1]) 

# tìm độ dài của deque
print(len(dq))

Đầu ra:

1 
4 
7

Đếm, Quay và Đảo ngược một deque

• count(value): Phương pháp này đếm số lần xuất hiện của một phần tử cụ thể trong deque.

• rotate(n): Phương pháp này xoay deque theo n bước. n dương xoay sang phải và n âm xoay sang trái.

• reverse(): Phương pháp này đảo ngược thứ tự các phần tử trong deque.

from collections import deque

# Tạo một deque với các phần tử ban đầu
dq = deque([10, 20, 30, 40, 50, 20, 30, 20])

# 1. Đếm số lần xuất hiện của một giá trị
print(dq.count(20))  # Đếm số lần xuất hiện của 20
print(dq.count(30))  # Đếm số lần xuất hiện của 30

# 2. Xoay deque
dq.rotate(2)  # Xoay deque 2 bước sang phải
print(dq)

dq.rotate(-3)  # Xoay deque 3 bước sang trái
print(dq)

# 3. Đảo ngược deque
dq.reverse()  # Đảo ngược deque
print(dq)

Đầu ra:

3 
2 
deque([30, 20, 10, 20, 30, 40, 50, 20]) 
deque([20, 30, 40, 50, 20, 30, 20, 10]) 
deque([10, 20, 30, 20, 50, 40, 30, 20])