Dequeue là gì

Double-Ended Queue (Deque) là Double-Ended Queue (deque). Đây là nghĩa tiếng Việt của thuật ngữ Double-Ended Queue (Deque) - một thuật ngữ thuộc nhóm Technology Terms - Công nghệ thông tin.

Nội dung chính Show

Giải thích ý nghĩa
What is the Double-Ended Queue (Deque)? - Definition
Understanding the Double-Ended Queue (Deque)
Thuật ngữ liên quan
2. Xây dựng hàng đợi bằng mảng
3. Xây dựng hàng đợi bằng danh sách liên kết

Độ phổ biến(Factor rating): 5/10

Một hàng đợi đúp kết thúc là một loại đặc biệt của dữ liệu trong lĩnh vực lập trình máy tính. Trong kiểu dữ liệu trừu tượng này, yếu tố có thể được thêm từ cả phía trước và phía sau của hàng đợi. do khách sạn này, nó cũng được biết đến như một danh sách liên kết đầu đuôi. Trong đó, hàng đợi thực sự tượng trưng cho một bộ sưu tập các mặt hàng được sắp xếp tương tự như một dòng với hai kết thúc. Mục có thể được thêm vào hoặc lấy ra từ hai đầu mà không cần bất kỳ loại những hạn chế. Nhiều ngôn ngữ lập trình sử dụng kỹ thuật này do nhiều của nó các ứng dụng.

Xem thêm: Thuật ngữ công nghệ A-Z

Giải thích ý nghĩa

Một deque cho phép lập trình viên tự do tương tác với danh sách các đối tượng. Trong khi một deque dường như có tất cả các tính năng của ngăn xếp và hàng đợi bình thường, nó thiếu một số hạn chế của họ. Ví dụ, FIFO và LIFO đơn đặt hàng không theo yêu cầu của cấu trúc dữ liệu deque, trong khi họ là những yêu cầu rất nghiêm ngặt về bình thường hàng đợi và ngăn xếp.

What is the Double-Ended Queue (Deque)? - Definition

A double-ended queue is a special type of data in the field of computer programming. In this abstract data type, elements can be added from both the front and the back of the queue. Due to this property, it is also known as a head-tail linked list. In this, the queue actually symbolizes a collection of items arranged similarly to a line with two ends. Items can be added or removed from either end without any type of restrictions. Many programming languages use this technique due to its many applications.

Understanding the Double-Ended Queue (Deque)

A deque allows the programmer to freely interact with the list of objects. While a deque seems to have all the features of stacks and normal queues, it lacks some of their limitations. For example, FIFO and LIFO orders are not required by the deque data structure, while they are very strict requirements of normal queues and stacks.

Thuật ngữ liên quan

Queue
Stack
Commit
Access Modifiers
Acyclic
Appending Virus
Armored Virus
Binder
Countermeasure
Level Design

Source: Double-Ended Queue (Deque) là gì? Technology Dictionary - Filegi - Techtopedia - Techterm

Hàng đợi (queue) là một cấu trúc dữ liệu hoạt động theo cơ chế FIFO (First In First Out), tạm dịch là “vào trước ra trước”. Có nghĩa là phần tử nào được thêm hàng đợi trước thì sẽ được lấy ra trước.

Có thể hình dung hàng đợi như một đoàn người xếp hàng mua vé. Người nào xếp hàng trước sẽ được mua vé trước và ra khỏi hàng để nhường vị trí cho người xếp hàng ngay phía sau.

Có thể xem hàng đợi (queue) là một kiểu danh sách có 2 phép toán đặc trưng là:

- Bổ sung một phần tử vào cuối danh sách (rear)
- Loại bỏ một phần tử ở đầu danh sách (front)

Một số thao tác thông dụng trên queue như:

enqueue(): thêm một phần tử vào queue.
dequeue(): loại bỏ một phần tử ra khỏi queue.
isFull(): kiểm tra queue có đầy chưa. Số lượng phần tử trong queue do người dùng quy định. Tùy trường hợp chúng ta mới cần sử dụng hàm isFull().
isEmpty(): kiểm tra queue có rỗng hay không.

Trong lập trình, có 2 cách thường dùng để xây dựng queue là sử dụng mảng (array) và danh sách liên kết (linked list).

2. Xây dựng hàng đợi bằng mảng

Khi xây dựng queue bằng mảng thì chúng ta lưu ý một số vấn đề sau:

- Cần có hai chỉ số front và rear để lưu chỉ số phần tử đầu và chỉ số phần tử cuối trong queue. Khởi tạo queue rỗng thì front = 0 và rear = -1.
- Để thêm một phần tử vào queue, ta tăng rear lên 1 và đưa giá trị đó vào phần tử thứ rear trong mảng.
- Để loại bỏ một phần tử khỏi queue, ta tăng front lên 1.
- Chỉ những phần tử của mảng từ vị trí front tới rear mới được xem là các phần tử trong queue.
- Khi front > rear thì queue đang rỗng.
- Khi rear tăng lên hết khoảng chỉ số của mảng thì mảng đã đầy, không thể thêm phần tử vào nữa.

#include <iostream> using namespace std; #define max 10000 int Queue[max]; int front, rear; void QueueInit(){ front = 0; rear = -1; } void enqueue(int V){ if(rear >= max-1){ cout<<"Queue is full"; }else{ rear++; Queue[rear] = V; } } int dequeue(){ if(front > rear){ cout<<"Queue is empty"; return -1; }else{ int res = Queue[front]; front++; return res; } } //print Queue void printQueue(){ if(front > rear){ cout<<"Queue is empty"; }else{ cout<<"Elements in Queue:"; for(int i=front;i<=rear;i++){ cout<<Queue[i]<<" "; } } } int main(){ //init Queue QueueInit(); //enqueue to Queue enqueue(5); enqueue(21); enqueue(10); enqueue(99); enqueue(101); //print Queue printQueue(); //dequeue from Queue cout<<endl<<"Dequeue fromt Queue:"; cout<<dequeue()<<" "; cout<<dequeue()<<endl; //print Queue after dequeue cout<<"Print Queue after dequeue"<<endl; printQueue(); system("pause"); }

Kết quả

Elements in Queue:5 21 10 99 101 Dequeue fromt Queue:5 21 Print Queue after dequeue Elements in Queue:10 99 101

Nhận xét:

Khi sử dụng mảng để cài đặt queue, chỉ số rear và front chỉ tăng lên chứ không giảm đi, kể cả khi lấy các phần tử ra khỏi hàng đợi. Chỉ có các phần tử từ vị trí front tới rear là thuộc queue. Các phần tử từ vị trí 0 tới front-1 bị lãng phí.

Hơn nữa, nếu chỉ số rear tăng lên vượt quá số lượng phần tử cho phép trong mảng thì queue cũng bị tràn, không thể thêm phần tử vào queue nữa.

Chúng ta có thể sử dụng danh sách liên kết để cài đặt queue nhằm khắc phục các khuyết điểm trên.

3. Xây dựng hàng đợi bằng danh sách liên kết

Khi sử dụng danh sách liên kết đơn để xây dựng queue, nếu muốn thêm một phần tử vào queue thì ta thêm vào cuối danh sách. Nếu muốn lấy một phần tử ra khỏi queue thì ta hủy phần tử đầu danh sách.

Lập trình giao tiếp cảm biến DHT với board mạch Arduino
Khai báo và khởi tạo mảng 1 chiều (one dimensional array) trong Java
Giới thiệu môn học Lập trình Arduino cơ bản
Sửa (update) dữ liệu và câu lệnh drop trong MySQL với Python
Các cấu trúc điều khiển vòng lặp for và for-each trong Java

#include <iostream> using namespace std; struct node{ int data; node *next; }; node * front; node *rear; void QueueInit(){ front = NULL; rear = NULL; } void enqueue(int V){ node *p; p = new node; p->data = V; p->next = NULL; if (front!=NULL){ rear->next = p; }else{ front = p; } rear = p; } int dequeue(){ if (front == NULL){ cout<<"Queue is empty"; return -1; }else{ int res = front->data; node *p = front->next; delete front; front = p; if(front == NULL){ rear = NULL; } return res; } } //print Queue void printQueue(){ node *p; p = front; cout<<"Elements in Queue:"; while (p!= NULL){ cout<<p->data<<" "; p = p->next; } } int main(){ //init Queue QueueInit(); //enqueue to Queue enqueue(5); enqueue(21); enqueue(10); enqueue(99); enqueue(101); //print Queue printQueue(); //dequeue from Queue cout<<endl<<"Dequeue fromt Queue:"; cout<<dequeue()<<" "; cout<<dequeue()<<endl; //print Queue after dequeue cout<<"Print Queue after dequeue"<<endl; printQueue(); system("pause"); }