- Phân loại hàng đợi kết thúc kép
- Các thao tác cơ bản của deque
- Deque Minh họa
- Triển khai Deque
- Các ứng dụng
- Kết luận
Hướng dẫn chuyên sâu về Deque hoặc Hàng đợi kết thúc kép trong C++. Hướng dẫn giải thích Deque là gì, Thao tác cơ bản, C++ & Ứng dụng và triển khai Java:
Hàng đợi kết thúc kép hay gọi đơn giản là “Deque” là phiên bản tổng quát của Hàng đợi.
Sự khác biệt giữa Hàng đợi và Deque là nó không tuân theo FIFO (First In, First Out) phương pháp tiếp cận. Tính năng thứ hai của Deque là chúng ta có thể chèn và xóa các phần tử từ đầu trước hoặc đầu sau.
Phân loại hàng đợi kết thúc kép
Deque có thể được phân loại như sau:
Deque giới hạn đầu vào: Trong giới hạn đầu vào, việc xóa có thể được thực hiện từ cả hai đầu nhưng việc chèn chỉ có thể được thực hiện ở đầu phía sau của queue.
Deque giới hạn đầu ra: Trong hàng đợi giới hạn đầu ra, việc thêm có thể được thực hiện từ cả hai đầu nhưng việc xóa chỉ được thực hiện ở một đầu, tức là đầu phía trước của hàng đợi.
Chúng ta cũng có thể triển khai ngăn xếp và hàng đợi bằng cách sử dụng deque.
Các thao tác cơ bản của deque
Sau đây là các thao tác cơ bản có thể được thực hiện trên deque.
- insert front: Chèn hoặc thêm mục vào phía trước deque.
- insertLast: Chèn hoặc thêm mục tại phía sau của hàng đợi.
- xóa Phía trước: Xóa hoặc xóa mục khỏi phía trước hàng đợi.
- xóa cuối cùng: Xóa hoặc xóa mục từ phía sau củaqueue.
- getFront: Truy xuất mục phía trước trong deque.
- getLast: Truy xuất mục cuối cùng trong hàng đợi.
- isEmpty: Kiểm tra xem deque có trống không.
- isFull: Kiểm tra xem deque có đầy không.
Deque Minh họa
Một deque rỗng được biểu diễn như sau:
Tiếp theo, chúng ta chèn phần tử 1 vào phía trước.
Bây giờ, chúng ta chèn phần tử 3 vào phía sau.
Tiếp theo, chúng ta thêm phần tử 5 vào phía trước và khi tăng lên thì phần tử phía trước chỉ vào 4.
Sau đó, chúng tôi chèn các phần tử 7 ở phía sau và 9 ở phía trước. Deque sẽ trông như hình bên dưới.
Tiếp theo, hãy xóa một phần tử ở phía trước.
Như vậy, ta thấy khi đưa phần tử vào phía trước thì vị trí phía trước giảm đi còn vị trí phía trước thì tăng lên khi lấy phần tử ra. Đối với giao diện phía sau, vị trí được tăng lên khi chèn và giảm đi khi xóa .
Triển khai Deque
Triển khai Deque C++
Chúng tôi có thể triển khai deque trong C++ sử dụng mảng cũng như danh sách liên kết. Ngoài ra, Thư viện mẫu chuẩn (STL) có một lớp “deque” thực hiện tất cả các chức năng cho cấu trúc dữ liệu này.
Việc triển khai mảng của deque đã được đưa ra bên dưới. Vì đây là hàng đợi hai đầu nên chúng tôi đã sử dụng mảng tròn chotriển khai.
#includeusing namespace std; #define MAX_size 10 // Maximum size of array or Dequeue // Deque class class Deque { int array[MAX_size]; int front; int rear; int size; public : Deque(int size) { front = -1; rear = 0; this->size = size; } // Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); int getFront(); int getRear(); // Check if Deque is full bool isFull() return ((front == 0 && rear == size-1) // Check if Deque is empty bool isEmpty(){ return (front == -1); } }; // Insert an element at front of the deque void Deque::insertfront(int key) { if (isFull()) { cout "Overflow!!\n" endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (front == 0) // front is first position of queue front = size - 1 ; else // decrement front 1 position front = front-1; array[front] = key ; // insert current element into Deque } // insert element at the rear end of deque void Deque ::insertrear(int key) { if (isFull()) { cout " Overflow!!\n " endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (rear == size-1) // rear is at last position of queue rear = 0; else // increment rear by 1 position rear = rear+1; array[rear] = key ; // insert current element into Deque } // Delete element at front of Deque void Deque ::deletefront() { if (isEmpty()) { cout "Queue Underflow!!\n" endl; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else // back to initial position if (front == size -1) front = 0; else // remove current front value from Deque;increment front by 1 front = front+1; } // Delete element at rear end of Deque void Deque::deleterear() { if (isEmpty()) { cout " Underflow!!\n" endl ; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size-1; else rear = rear-1; } // retrieve front element of Deque int Deque::getFront() { if (isEmpty()) { cout " Underflow!!\n" endl; return -1 ; } return array[front]; } // retrieve rear element of Deque int Deque::getRear() { if(isEmpty() || rear 0) { cout " Underflow!!\n" endl; return -1 ; } return array[rear]; } //main program int main() { Deque dq(5); cout "Insert element 1 at rear end \n"; dq.insertrear(1); cout "insert element 3 at rear end \n"; dq.insertrear(3); cout "rear element of deque " " " dq.getRear() endl; dq.deleterear(); cout "After deleterear, rear = " dq.getRear() endl; cout "inserting element 5 at front end \n"; dq.insertfront(5); cout "front element of deque " " " dq.getFront() endl; dq.deletefront(); cout "After deletefront, front = " dq.getFront() endl; return 0; }
Đầu ra:
Chèn phần tử 1 ở phía sau
chèn phần tử 3 ở phía sau
phần tử phía sau của deque 3
Sau khi xóa, phía sau =
chèn phần tử 5 vào giao diện người dùng
phần tử phía trước của deque 5
Sau khi xóa phía trước, phía trước =
Triển khai Java Deque
Giao diện deque trong Java, “java.util.Deque” có nguồn gốc từ giao diện “java.util.Queue”. Deque có thể được sử dụng như một hàng đợi (First In, First Out) hoặc ngăn xếp (Last In, First Out). Các triển khai này hoạt động nhanh hơn so với danh sách được liên kết.
Đưa ra bên dưới là hệ thống phân cấp cho giao diện Deque trong Java.
Chúng ta cần nhớ một số điểm về giao diện Deque trong Java:
- Việc triển khai không an toàn theo luồng vì không có đồng bộ hóa bên ngoài.
- Deque không hỗ trợ đồng thời theo nhiều luồng.
- Deque được triển khai bằng cách sử dụng mảng không cho phép sử dụng các phần tử NULL.
- Mảng được phép phát triển theo yêu cầu, với dung lượng không hạn chế và hỗ trợ mảng có thể thay đổi kích thước là hai tính năng quan trọng nhất.
Sau đây là các phương thức khác nhau được giao diện Deque hỗ trợ:
| Không. | Phương thức | Mô tả |
|---|---|---|
| 1 | add(element) | Thêm một phần tử vào đuôi. |
| 2 | addFirst(element) | Thêm một phần tử vàohead/front. |
| 3 | addLast(element) | Thêm một phần tử vào tail/rear. |
| 4 | offer(element) | Thêm một element vào đuôi; trả về một giá trị boolean để cho biết việc chèn có thành công hay không. |
| 5 | offerFirst(element) | Thêm một phần tử vào phần đầu; trả về một giá trị boolean để cho biết việc chèn có thành công hay không. |
| 6 | offerLast(element) | Thêm một phần tử vào đuôi; trả về một giá trị boolean để cho biết liệu việc chèn có thành công hay không. |
| 7 | iterator() | Trả về một trình vòng lặp cho deque. |
| 8 | descendingIterator() | Trả về một iterator có thứ tự ngược lại cho deque này. |
| 9 | push(element) | Thêm một phần tử vào phần đầu của deque. |
| 10 | pop(element) | Xóa phần tử khỏi phần đầu của deque và trả về phần tử đó. |
| 11 | removeFirst() | Xóa phần tử tại phần đầu của deque. |
| 12 | removeLast() | Xóa phần tử ở phần đuôi của deque. |
| 13 | poll() | Lấy và xóa phần tử đầu tiên của deque (được đại diện bởi phần đầu của deque); trả về NULL nếu deque trống. |
| 14 | pollFirst() | Lấy và loại bỏ phần tử đầu tiên của deque này; trả về null nếu deque này làtrống. |
| 15 | pollLast() | Truy xuất và xóa phần tử cuối cùng của deque này; trả về null nếu deque này trống. |
| 16 | peek() | Lấy phần đầu (phần tử đầu tiên của deque) của hàng đợi được biểu diễn bởi deque này; trả về null nếu deque này trống. Lưu ý: Thao tác này không xóa phần tử. |
| 17 | peekFirst() | Truy xuất phần tử đầu tiên của deque này; trả về null nếu deque này trống. Lưu ý: Thao tác này không xóa phần tử. |
| 18 | peekLast() | Truy xuất phần tử cuối cùng của deque này hoặc trả về null nếu deque này trống. Lưu ý: Thao tác này không xóa phần tử. |
Việc triển khai Java sau đây minh họa các hoạt động khác nhau được thảo luận ở trên.
import java.util.*; class Main { public static void main(String[] args) { Dequedeque = new LinkedList(); // We can add elements to the queue in various ways deque.add(1); // add to tail deque.addFirst(3); deque.addLast(5); deque.push(7); //add to head deque.offer(9); deque.offerFirst(11); deque.offerLast(13); System.out.println("The deque : " + deque + "\n"); // Iterate through the queue elements. System.out.println("Standard Iterator"); Iterator iterator = deque.iterator(); while (iterator.hasNext()) System.out.print(" " + iterator.next()); // Reverse order iterator Iterator reverse = deque.descendingIterator(); System.out.println("\nReverse Iterator"); while (reverse.hasNext()) System.out.print(" " + reverse.next()); // Peek returns the head, without deleting // it from the deque System.out.println("\n\nPeek " + deque.peek()); System.out.println("After peek: " + deque); // Pop returns the head, and removes it from // the deque System.out.println("\nPop " + deque.pop()); System.out.println("After pop: " + deque); // We can check if a specific element exists // in the deque System.out.println("\nContains element 3?: " + deque.contains(3)); // We can remove the first / last element. deque.removeFirst(); deque.removeLast(); System.out.println("Deque after removing " + "first and last elements: " + deque); } } Đầu ra:
The deque : [11, 7, 3, 1, 5, 9, 13]
Trình lặp tiêu chuẩn
11 7 3 1 5 9 13
Trình lặp đảo ngược
13 9 5 1 3 7 1
Peek 11
Sau nháy: [11, 7, 3, 1, 5, 9, 13]
Bật 11
Sau bật: [7, 3, 1, 5, 9, 13]
Chứa phần tử 3?: true
Deque sau khi xóa phần tử đầu tiên và cuối: [3, 1, 5, 9]
Trong chương trình trên, chúng ta đã sử dụng giao diện Deque của Java và chúng ta đã định nghĩa một deque gồm các phần tử số nguyên. Sau đó, chúng tôi thực hiện các thao tác khác nhau trên deque này và xuất kết quả của các thao tác này làđược hiển thị.
Các ứng dụng
Deque có thể được sử dụng trong một số ứng dụng sau.
#1) Thuật toán lập lịch: Thuật toán lập lịch trình, “Thuật toán lập lịch trình A-steal” thực hiện lập lịch tác vụ cho các bộ xử lý khác nhau trong hệ thống đa bộ xử lý. Việc triển khai này sử dụng deque và bộ xử lý lấy phần tử đầu tiên từ deque để thực thi.
#2) Hoàn tác Danh sách Hoạt động: Trong các ứng dụng phần mềm, chúng ta có nhiều hành động. Một là "hoàn tác". Khi chúng tôi đã thực hiện hành động hoàn tác nhiều lần, tất cả các hành động này được lưu trữ trong một danh sách. Danh sách này được duy trì dưới dạng deque để chúng tôi có thể dễ dàng thêm/xóa mục từ bất kỳ đầu nào.
#3) Xóa mục sau một thời gian: Làm mới ứng dụng các mục nhập trong danh sách của họ, chẳng hạn như các ứng dụng liệt kê các mục nhập kho, v.v. Các ứng dụng này sẽ xóa các mục nhập sau một thời gian và cũng chèn các mục nhập mới. Điều này được thực hiện bằng cách sử dụng deque.
Kết luận
Deque là hàng đợi hai đầu cho phép chúng ta thêm/xóa các phần tử ở cả hai đầu, tức là phía trước và phía sau của hàng đợi. Deque có thể được thực hiện bằng cách sử dụng mảng hoặc danh sách liên kết. Tuy nhiên, chúng tôi cũng có một lớp Thư viện mẫu chuẩn (STL) thực hiện các hoạt động khác nhau của Deque.
Trong Java, chúng tôi có giao diện Deque được kế thừa từ giao diện hàng đợi để triển khai Deque. Ngoài các hoạt động tiêu chuẩn cơ bản của Deque, giao diện này hỗ trợ nhiềucác hoạt động khác có thể được thực hiện trên Deque.
Deque thường được sử dụng cho các ứng dụng yêu cầu thêm/bớt các phần tử ở cả hai đầu. Nó cũng chủ yếu được sử dụng trong việc lập lịch trình của các bộ xử lý trong các hệ thống nhiều bộ xử lý.
Xem Chuỗi đào tạo C++ hoàn chỉnh