C++: Deque
Tổng quan
Deque - viết gọn của double-ended queue (hàng đợi 2 đầu) là một cấu trúc dữ liệu dạng đặc biệt của queue. Cấu trúc dữ liệu queue (hàng đợi) chỉ cho phép chèn phần tử vào cuối và xóa phần tử từ phía trước. Hàng đợi hai đầu hỗ trợ các thao tác chèn và xóa có thể thực hiện được ở cả hai đầu.
Sử dụng deque
Cài đặt deque sử dụng mảng
#include <iostream>
template <typename T, int MAX_SIZE>
class Deque {
private:
T arr[MAX_SIZE];
int front, rear;
public:
Deque() : front(-1), rear(-1) {}
bool isEmpty() {
return (front == -1 && rear == -1);
}
bool isFull() {
return ((rear + 1) % MAX_SIZE == front);
}
void insertFront(T value) {
if (isFull()) {
std::cout << "Deque is full. Cannot insert at front: " << value << std::endl;
return;
} else if (isEmpty()) {
front = rear = 0;
} else {
front = (front - 1 + MAX_SIZE) % MAX_SIZE;
}
arr[front] = value;
}
void insertRear(T value) {
if (isFull()) {
std::cout << "Deque is full. Cannot insert at rear: " << value << std::endl;
return;
} else if (isEmpty()) {
front = rear = 0;
} else {
rear = (rear + 1) % MAX_SIZE;
}
arr[rear] = value;
}
void deleteFront() {
if (isEmpty()) {
std::cout << "Deque is empty. Cannot delete from front" << std::endl;
return;
} else if (front == rear) {
front = rear = -1;
} else {
front = (front + 1) % MAX_SIZE;
}
}
void deleteRear() {
if (isEmpty()) {
std::cout << "Deque is empty. Cannot delete from rear" << std::endl;
return;
} else if (front == rear) {
front = rear = -1;
} else {
rear = (rear - 1 + MAX_SIZE) % MAX_SIZE;
}
}
T getFront() {
if (isEmpty()) {
std::cout << "Deque is empty. No front element" << std::endl;
return T();
}
return arr[front];
}
T getRear() {
if (isEmpty()) {
std::cout << "Deque is empty. No rear element" << std::endl;
return T();
}
return arr[rear];
}
};
int main() {
Deque<int, 5> dq;
dq.insertRear(10);
dq.insertRear(20);
dq.insertFront(30);
dq.insertFront(40);
std::cout << "Front of deque: " << dq.getFront() << std::endl; // In ra: Front of deque: 40
std::cout << "Rear of deque: " << dq.getRear() << std::endl; // In ra: Rear of deque: 20
dq.deleteFront();
dq.deleteRear();
std::cout << "After delete operations:" << std::endl;
std::cout << "Front of deque: " << dq.getFront() << std::endl; // In ra: Front of deque: 30
std::cout << "Rear of deque: " << dq.getRear() << std::endl; // In ra: Rear of deque: 10
return 0;
}
Chú thích: Duy trì 2 biến front là chỉ số của phần tử đầu deque và rear là chỉ số của phần tử cuối dequeue. Khi ta thêm một phần tử vào đầu (push front), ta chỉ cần giảm chỉ số đầu (front) rồi gán phần tử ấy vào chỉ số mới. Ngược lại khi ta thêm một phần tử vào cuối (push back), ta chỉ cần tăng chỉ số đầu (rear) rồi gán phần tử ấy vào. Còn khi ta ta xóa một phần tử ở đầu (pop front), ta chỉ việc tăng chỉ số đầu, còn xóa phần tử ở cuối (pop back) thì ta sẽ giảm chỉ số cuối. Tuy nhiên, trong trường hợp ta thêm một phần tử vào đầu (push front), rồi lại xóa đi phần tử cuối (pop back), rồi thêm lại phần tử đầu (push front), … Tiếp tục như vậy, deque mà ta xây dựng dù luôn luôn chỉ có tối đa một phần tử, thế nhưng hai chỉ số đầu và chỉ số cuối lại tăng lên liên tục dẫn tới việc bị tràn giới hạn mảng. Để khắc phục vấn đề này, ta sẽ cho phép các chỉ số được xoay vòng. Tức là khi chỉ số front hoặc rear đạt đến giới hạn MAX_SIZE, ta sẽ cho nó về 0 và tương tự khi chỉ số bị giảm về -1 ta sẽ đặt nó về MAX_SIZE - 1. Việc này được thực hiện bằng cách sử dụng toán tử mod (modulo - %).
Cài đặt deque sử dụng danh sách liên kết
Cài đặt bằng mảng xoay vòng hầu như đã là phương pháp tối ưu, tuy nhiên trong một vài trường hợp, khi mà số lượng phần tử cần không thể xác định được, lúc này ta sẽ sử dụng danh sách liên kết (linked list) để biểu diễn deque.
#include <iostream>
template <typename T>
class Node {
public:
T data;
Node* next;
Node* prev;
Node(T value) : data(value), next(nullptr), prev(nullptr) {}
};
template <typename T>
class Deque {
private:
Node<T>* front;
Node<T>* rear;
public:
Deque() : front(nullptr), rear(nullptr) {}
bool isEmpty() {
return (front == nullptr && rear == nullptr);
}
void insertFront(T value) {
Node<T>* newNode = new Node<T>(value);
if (isEmpty()) {
front = rear = newNode;
} else {
newNode->next = front;
front->prev = newNode;
front = newNode;
}
}
void insertRear(T value) {
Node<T>* newNode = new Node<T>(value);
if (isEmpty()) {
front = rear = newNode;
} else {
rear->next = newNode;
newNode->prev = rear;
rear = newNode;
}
}
void deleteFront() {
if (isEmpty()) {
std::cout << "Deque is empty. Cannot delete from front" << std::endl;
return;
} else {
Node<T>* temp = front;
if (front == rear) {
front = rear = nullptr;
} else {
front = front->next;
front->prev = nullptr;
}
delete temp;
}
}
void deleteRear() {
if (isEmpty()) {
std::cout << "Deque is empty. Cannot delete from rear" << std::endl;
return;
} else {
Node<T>* temp = rear;
if (front == rear) {
front = rear = nullptr;
} else {
rear = rear->prev;
rear->next = nullptr;
}
delete temp;
}
}
T getFront() {
if (isEmpty()) {
std::cout << "Deque is empty. No front element" << std::endl;
return T();
}
return front->data;
}
T getRear() {
if (isEmpty()) {
std::cout << "Deque is empty. No rear element" << std::endl;
return T();
}
return rear->data;
}
};
int main() {
Deque<int> dq;
dq.insertRear(10);
dq.insertRear(20);
dq.insertFront(30);
dq.insertFront(40);
std::cout << "Front of deque: " << dq.getFront() << std::endl; // In ra: Front of deque: 40
std::cout << "Rear of deque: " << dq.getRear() << std::endl; // In ra: Rear of deque: 20
dq.deleteFront();
dq.deleteRear();
std::cout << "After delete operations:" << std::endl;
std::cout << "Front of deque: " << dq.getFront() << std::endl; // In ra: Front of deque: 30
std::cout << "Rear of deque: " << dq.getRear() << std::endl; // In ra: Rear of deque: 10
return 0;
}
Sử dụng thư viện STL
Thư viện chuẩn STL cung cấp deque với một số các thao tác cơ bản:
push_back(): Thêm một phần tử vào cuối deque.
push_front(): Thêm một phần tử vào đầu deque.
pop_back(): Xóa phần tử ở cuối deque.
pop_front(): Xóa phần tử ở đầu deque.
back(): Trả về tham chiếu đến phần tử cuối cùng của deque.
front(): Trả về tham chiếu đến phần tử đầu tiên của deque.
size(): Trả về số lượng phần tử trong deque.
empty(): Kiểm tra xem deque có rỗng không.
at(): Trả về tham chiếu đến phần tử tại vị trí chỉ định trong deque.
clear(): Xóa tất cả các phần tử trong deque.
emplace_back(): Thêm một phần tử mới vào cuối deque thông qua việc gọi constructor với các đối số cho phép.
emplace_front(): Thêm một phần tử mới vào đầu deque thông qua việc gọi constructor với các đối số cho phép.
insert(): Chèn một hoặc nhiều phần tử vào vị trí chỉ định trong deque.
erase(): Xóa một hoặc nhiều phần tử từ vị trí chỉ định trong deque.
resize(): Thay đổi kích thước của deque.
Ví dụ
#include <iostream>
#include <deque>
int main() {
std::deque<int> myDeque;
// Thêm phần tử vào cuối deque
myDeque.push_back(10);
myDeque.push_back(20);
// Thêm phần tử vào đầu deque
myDeque.push_front(5);
myDeque.push_front(2);
// Hiển thị các phần tử trong deque
std::cout << "Deque elements: ";
for (auto element : myDeque) {
std::cout << element << " ";
}
std::cout << std::endl;
// Truy cập phần tử ở đầu và cuối deque
std::cout << "Front element: " << myDeque.front() << std::endl;
std::cout << "Back element: " << myDeque.back() << std::endl;
// Xóa phần tử ở đầu và cuối deque
myDeque.pop_front();
myDeque.pop_back();
// Kiểm tra kích thước và rỗng
std::cout << "Size of deque: " << myDeque.size() << std::endl;
std::cout << "Is deque empty: " << (myDeque.empty() ? "Yes" : "No") << std::endl;
return 0;
}
Output:
Deque elements: 2 5 10 20
Front element: 2
Back element: 20
Size of deque: 2
Is deque empty: No