ENQUEUE LÀ GÌ

Chào ace, bài này chúng ta sẽ tìm hiểu về Queue và cài đặt Queue bằng mảng một chiều trong series tự học về cấu trúc dữ liệu(CTDL) và giải thuật, sau đây cqaugusta.com sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.

Bạn đang xem: Enqueue là gì

Giống với Stack (ngăn xếp), thì Queue (hàng đợi) cũng là một cấu trúc dữ liệu tuyến tính tuân theo một thứ tự cụ thể mà trong đó các phép thao tác được thực hiện. Thứ tự trong Queue là First In First Out – Vào trước Ra trước. Một ví dụ điển hình về Queue là một hàng người đang đợi ở trước quầy thanh toán trong siêu thị, khi đó ai là người đến trước, đứng trước ở trong hàng, sẽ được thanh toán xong trước.

Sự khác biệt giữa Stack và Queue được thể hiện khi thực hiện thao tác xóa phần tử. Trong một Stack, chúng ta sẽ xóa phần tử mới được chèn thêm vào gần đây nhất. Còn trong một Queue, chúng ta sẽ xóa phần tử mà đã được chèn thêm vào Queue lâu nhất rồi.


Nội dung chính


1. Các thao tác có thể thực hiện trên Queue

Dưới đây là các phép thao tác dữ liệu cơ bản có thể thực hiện được trên Queue:


1. Enqueue

Chèn thêm một phần tử vào Queue. Nếu Queue đã đầy, lúc này đã đạt đến điều kiện tràn cận trên của Queue, không thể chèn thêm phần tử mới vào nữa.

2. Dequeue: 

Xóa một phần tử khỏi Queue. Các phần tử khi được xóa sẽ được đưa ra khỏi Queue theo cùng một thứ tự như khi chúng được đẩy vào trong Queue. Nếu Queue rỗng mà ta vẫn cố tình thực hiện xóa phần tử thì lúc này điều kiện tràn cận dưới của Queue sẽ được kích hoạt.

Xem thêm: Hoa Đẹp Thiên Nhiên

3. Front:


Lấy ra phần tử nằm ở đầu Queue

4. Rear:

Lấy ra phần tử nằm ở cuối Queue

*

2. Ứng dụng của Queue

Queue được sử dụng khi mọi thứ không cần phải được xử lý ngay lập tức, mà phải được xử lý theo thử tứ First In First Out – Vào Trước Ra Trước giống như thuật toán BFS – Breadth First Search (tìm kiếm theo chiều rộng). Thuộc tính này của Queue làm cho nó vô cùng hữu dụng trong các loại tình huống sau:

1. Khi một tài nguyên được chia sẻ giữa nhiều đối tượng có nhu cầu. Ví dụ: Quá trình lập lịch CPU, quá trình lập lịch đĩa.

2. Khi dữ liệu được truyền một cách bất đồng bộ (dữ liệu không nhất thiết phải được nhận ở cùng tỷ lệ như khi được gửi) giữa hai tiến trình (process). Ví dụ: các IO Buffers, pipes, file IO, v.v…

3. Cài đặt Queue bằng mảng một chiều

Để cài đặt Queue, chúng ta cần theo dõi hai chỉ số, đó là front và rear. Chúng ta sẽ enqueue – chèn thêm một phần tử vào rear và dequeue – xóa đi một phần tử khỏi front. Nếu chúng ta chỉ tăng các chỉ số front và rear, thì có thể một vấn đề sẽ xảy ra, đó là chỉ số front có thể đạt đến mức cuối mảng. Giải pháp cho vấn đề này là tăng front và rear theo cách xoay vòng.

Dưới đây là các đoạn code ví dụ mô tả cách cài đặt một queue, và các thao tác xử lý dữ liệu trên queue:

CÁC ĐOẠN CODE VÍ DỤ ĐƯỢC VIẾT BẰNG C++ C JAVA PYTHON3 C#

C++


// CPP program for array // implementation of queue #include using namespace std; // A structure to represent a queue class Queue { public: int front, rear, size; unsigned capacity; int* array; }; // function to create a queue // of given capacity. // It initializes size of queue as 0 Queue* createQueue(unsigned capacity) { Queue* queue = new Queue(); queue->capacity = capacity; queue->front = queue->size = 0; // This is important, see the enqueue queue->rear = capacity - 1; queue->array = new int<( queue->capacity * sizeof(int))>; return queue; } // Queue is full when size // becomes equal to the capacity int isFull(Queue* queue) { return (queue->size == queue->capacity); } // Queue is empty when size is 0 int isEmpty(Queue* queue) { return (queue->size == 0); } // Function to add an item to the queue. // It changes rear and size void enqueue(Queue* queue, int item) { if (isFull(queue)) return; queue->rear = (queue->rear + 1) % queue->capacity; queue->arrayrear> = item; queue->size = queue->size + 1; cout arrayfront>; queue->front = (queue->front + 1) % queue->capacity; queue->size = queue->size - 1; return item; } // Function to get front of queue int front(Queue* queue) { if (isEmpty(queue)) return INT_MIN; return queue->arrayfront>; } // Function to get rear of queue int rear(Queue* queue) { if (isEmpty(queue)) return INT_MIN; return queue->arrayrear>; } // Driver code int main() { Queue* queue = createQueue(1000); enqueue(queue, 10); enqueue(queue, 20); enqueue(queue, 30); enqueue(queue, 40); cout C

// C program for array implementation of queue #include #include #include // A structure to represent a queue struct Queue { int front, rear, size; unsigned capacity; int* array; }; // function to create a queue // of given capacity. // It initializes size of queue as 0 struct Queue* createQueue(unsigned capacity) { struct Queue* queue = (struct Queue*)malloc( sizeof(struct Queue)); queue->capacity = capacity; queue->front = queue->size = 0; // This is important, see the enqueue queue->rear = capacity - 1; queue->array = (int*)malloc( queue->capacity * sizeof(int)); return queue; } // Queue is full when size becomes // equal to the capacity int isFull(struct Queue* queue) { return (queue->size == queue->capacity); } // Queue is empty when size is 0 int isEmpty(struct Queue* queue) { return (queue->size == 0); } // Function to add an item to the queue. // It changes rear and size void enqueue(struct Queue* queue, int item) { if (isFull(queue)) return; queue->rear = (queue->rear + 1) % queue->capacity; queue->arrayrear> = item; queue->size = queue->size + 1; printf("%d enqueued to queue\n", item); } // Function to remove an item from queue. // It changes front and size int dequeue(struct Queue* queue) { if (isEmpty(queue)) return INT_MIN; int item = queue->arrayfront>; queue->front = (queue->front + 1) % queue->capacity; queue->size = queue->size - 1; return item; } // Function to get front of queue int front(struct Queue* queue) { if (isEmpty(queue)) return INT_MIN; return queue->arrayfront>; } // Function to get rear of queue int rear(struct Queue* queue) { if (isEmpty(queue)) return INT_MIN; return queue->arrayrear>; } // Driver program to test above functions./ int main() { struct Queue* queue = createQueue(1000); enqueue(queue, 10); enqueue(queue, 20); enqueue(queue, 30); enqueue(queue, 40); printf("%d dequeued from queue\n\n", dequeue(queue)); printf("Front item is %d\n", front(queue)); printf("Rear item is %d\n", rear(queue)); return 0; } JAVA

// Java program for array // implementation of queue // A class to represent a queue class Queue { int front, rear, size; int capacity; int array<>; public Queue(int capacity) { this.capacity = capacity; front = this.size = 0; rear = capacity - 1; array = new int; } // Queue is full when size becomes // equal to the capacity boolean isFull(Queue queue) { return (queue.size == queue.capacity); } // Queue is empty when size is 0 boolean isEmpty(Queue queue) { return (queue.size == 0); } // Method to add an item to the queue. // It changes rear and size void enqueue(int item) { if (isFull(this)) return; this.rear = (this.rear + 1) % this.capacity; this.array = item; this.size = this.size + 1; System.out.println(item + " enqueued to queue"); } // Method to remove an item from queue. // It changes front and size int dequeue() { if (isEmpty(this)) return Integer.MIN_VALUE; int item = this.array; this.front = (this.front + 1) % this.capacity; this.size = this.size - 1; return item; } // Method to get front of queue int front() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.array; } // Method to get rear of queue int rear() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.array; } } // Driver class public class Test { public static void main(String<> args) { Queue queue = new Queue(1000); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); queue.enqueue(40); System.out.println(queue.dequeue() + " dequeued from queue\n"); System.out.println("Front item is " + queue.front()); System.out.println("Rear item is " + queue.rear()); } } PYTHON3

# Python3 program for array implementation of queue # Class Queue to represent a queue class Queue: # __init__ function def __init__(self, capacity): self.front = self.size = 0 self.rear = capacity -1 self.Q = *capacity self.capacity = capacity # Queue is full when size becomes # equal to the capacity def isFull(self): return self.size == self.capacity # Queue is empty when size is 0 def isEmpty(self): return self.size == 0 # Function to add an item to the queue. # It changes rear and size def EnQueue(self, item): if self.isFull(): print("Full") return self.rear = (self.rear + 1) % (self.capacity) self.Q = item self.size = self.size + 1 print("% s enqueued to queue" % str(item)) # Function to remove an item from queue. # It changes front and size def DeQueue(self): if self.isEmpty(): print("Empty") return print("% s dequeued from queue" % str(self.Q)) self.front = (self.front + 1) % (self.capacity) self.size = self.size -1 # Function to get front of queue def que_front(self): if self.isEmpty(): print("Queue is empty") print("Front item is", self.Q) # Function to get rear of queue def que_rear(self): if self.isEmpty(): print("Queue is empty") print("Rear item is", self.Q) # Driver Code if __name__ == "__main__": queue = Queue(30) queue.EnQueue(10) queue.EnQueue(20) queue.EnQueue(30) queue.EnQueue(40) queue.DeQueue() queue.que_front() queue.que_rear() C#

// C# program for array implementation of queue using System; namespace GeeksForGeeks { // A class to represent a linearqueue class Queue { private int<> ele; private int front; private int rear; private int max; public Queue(int size) { ele = new int; front = 0; rear = -1; max = size; } // Function to add an item to the queue. // It changes rear and size public void enqueue(int item) { if (rear == max - 1) { Console.WriteLine("Queue Overflow"); return; } else { ele<++rear> = item; } } // Function to remove an item from queue. // It changes front and size public int dequeue() { if (front == rear + 1) { Console.WriteLine("Queue is Empty"); return -1; } else { Console.WriteLine(ele + " dequeued from queue"); int p = ele; Console.WriteLine(); Console.WriteLine("Front item is {0}", ele); Console.WriteLine("Rear item is {0} ", ele); return p; } } // Function to print queue. public void printQueue() { if (front == rear + 1) { Console.WriteLine("Queue is Empty"); return; } else { for (int i = front; i Kết quả in ra là:

10 enqueued to queue20 enqueued to queue30 enqueued to queue40 enqueued to queue10 dequeued from queueFront item is 20Rear item is 40

4. Phân tích độ phức tạp

1. Độ phức tạp về thời gian

Thao tác trên Queue Độ phức tạp về thời gian

Enque(Chèn thêm phần tử) O(1)

Deque(Xóa phần tử) O(1)

Front(Lấy ra phần tử đầu tiên của Queue) O(1)


Rear(Lấy ra phần tử cuối cùng của Queue) O(1)

2. Độ phức tạp về không gian: O(N)

N là kích thước của mảng để lưu trữ các phần tử.

* Ưu điểm của việc cài đặt Queue bằng mảng một chiều

– Dễ cài đặt

* Hạn chế của việc cài đặt Queue bằng mảng một chiều

– Mảng một chiều là kiểu cấu trúc dữ liệu tĩnh, có kích thước cố định không thể thay đổi.

– Nếu thực hiện một số lượng lớn các thao tác enqueue (chèn thêm phần tử mới) và dequeue (xóa phần tử) trên một Queue, tại một thời điểm nào đó chúng ta có thể sẽ không thể chèn thêm được các phần tử mới vào Queue, ngay cả khi Queue đang trống (có thể tránh được vấn đề này bằng cách sử dụng Circular Queue – Hàng đợi vòng tròn).