Hàng đợi là một cấu trúc dữ liệu hữu ích trong lập trình. Nó tương tự như hàng đợi mua vé bên ngoài rạp chiếu phim, nơi người đầu tiên vào hàng đợi là người đầu tiên lấy được vé.
Hàng đợi tuân theo quy tắc First In First Out (FIFO) - mục nào vào trước thì mục đó ra trước.
Biểu diễn FIFO của hàng đợi
Trong hình ảnh trên, vì 1 được giữ trong hàng đợi trước 2, nên nó cũng là mục đầu tiên được xóa khỏi hàng đợi. Nó tuân theo quy tắc FIFO.
Theo thuật ngữ lập trình, việc đưa các mục vào hàng đợi được gọi là enqueue, và việc xóa các mục khỏi hàng đợi được gọi là dequeue.
Chúng ta có thể triển khai hàng đợi trong bất kỳ ngôn ngữ lập trình nào như C, C++, Java, Python hoặc C#, nhưng thông số kỹ thuật thì khá giống nhau.
2.2.1.Các hoạt động cơ bản của hàng đợi
Hàng đợi là một đối tượng (một cấu trúc dữ liệu trừu tượng - ADT) cho phép các hoạt động sau:
Enqueue:Thêm một phần tử vào cuối hàng đợi
Dequeue: Xóa một phần tử khỏi đầu hàng đợi
IsEmpty: Kiểm tra xem hàng đợi có trống không
IsFull: Kiểm tra xem hàng đợi có đầy không
Peek: Lấy giá trị ở đầu hàng đợi mà không xóa nó
2.2.2. Hoạt động của hàng đợi
Các hoạt động của hàng đợi hoạt động như sau:
Hai con trỏ FRONT và REAR
FRONT theo dõi phần tử đầu tiên của hàng đợi
REAR theo dõi phần tử cuối cùng của hàng đợi
ban đầu, đặt giá trị của FRONT và REAR thành -1
2.2.3.Hoạt động xếp hàng
kiểm tra xem hàng đợi có đầy không
đối với phần tử đầu tiên, đặt giá trị của FRONT thành 0
tăng chỉ số REAR lên 1
thêm phần tử mới vào vị trí được trỏ tới bởi REAR
2.2.4.Hoạt động Dequeue
kiểm tra xem hàng đợi có trống không
trả về giá trị được trỏ bởi FRONT
tăng chỉ số FRONT lên 1
đối với phần tử cuối cùng, đặt lại giá trị của FRONT và REAR thành -1
Các hoạt động Enqueue và Dequeue
2.2.5.Triển khai hàng đợi trong Python, Java, C và C++
Chúng ta thường sử dụng mảng để triển khai hàng đợi trong Java và C/++. Trong trường hợp của Python, chúng ta sử dụng danh sách.
#Python
# Queue implementation in Python
class Queue():
def __init__(self, k): self.k = k self.queue = [None] * k self.head = self.tail = -1
# Insert an element into the queue def enqueue(self, data):
if (self.tail == self.k - 1): print("The queue is full\n")
def printQueue(self): if(self.head == -1): print("No element in the queue")
else: for i in range(self.head, self.tail + 1): print(self.queue[i], end=" ") print()
# Your Queue object will be instantiated and called as such: obj = Queue(5) obj.enqueue(1) obj.enqueue(2) obj.enqueue(3) obj.enqueue(4) obj.enqueue(5) print("Initial queue") obj.printQueue()
obj.dequeue() print("After removing an element from the queue") obj.printQueue()
#Java
// Queue implementation in Java
public class Queue { int SIZE = 5; int items[] = new int[SIZE]; int front, rear;
void enQueue(int element) { if (isFull()) { System.out.println("Queue is full"); } else { if (front == -1) front = 0; rear++; items[rear] = element; System.out.println("Inserted " + element); } }
int deQueue() { int element; if (isEmpty()) { System.out.println("Queue is empty"); return (-1); } else { element = items[front]; if (front >= rear) { front = -1; rear = -1; } /* Q has only one element, so we reset the queue after deleting it. */ else { front++; } System.out.println("Deleted -> " + element); return (element); } }
void display() { /* Function to display elements of Queue */ int i; if (isEmpty()) { System.out.println("Empty Queue"); } else { System.out.println("\nFront index-> " + front); System.out.println("Items -> "); for (i = front; i <= rear; i++) System.out.print(items[i] + " ");
System.out.println("\nRear index-> " + rear); } }
public static void main(String[] args) { Queue q = new Queue();
// deQueue is not possible on empty queue q.deQueue();
// enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5);
// 6th element can't be added to because the queue is full q.enQueue(6);
q.display();
// deQueue removes element entered first i.e. 1 q.deQueue();
int main() { //deQueue is not possible on empty queue deQueue();
//enQueue 5 elements enQueue(1); enQueue(2); enQueue(3); enQueue(4); enQueue(5);
// 6th element can't be added to because the queue is full enQueue(6);
display();
//deQueue removes element entered first i.e. 1 deQueue();
//Now we have just 4 elements display();
return 0; }
void enQueue(int value) { if (rear == SIZE - 1) printf("\nQueue is Full!!"); else { if (front == -1) front = 0; rear++; items[rear] = value; printf("\nInserted -> %d", value); } }
void deQueue() { if (front == -1) printf("\nQueue is Empty!!"); else { printf("\nDeleted : %d", items[front]); front++; if (front > rear) front = rear = -1; } }
// Function to print the queue void display() { if (rear == -1) printf("\nQueue is Empty!!!"); else { int i; printf("\nQueue elements are:\n"); for (i = front; i <= rear; i++) printf("%d ", items[i]); } printf("\n"); }
#C++
// Queue implementation in C++
#include <iostream> #define SIZE 5
using namespace std;
class Queue { private: int items[SIZE], front, rear;
void enQueue(int element) { if (isFull()) { cout << "Queue is full"; } else { if (front == -1) front = 0; rear++; items[rear] = element; cout << endl << "Inserted " << element << endl; } }
int deQueue() { int element; if (isEmpty()) { cout << "Queue is empty" << endl; return (-1); } else { element = items[front]; if (front >= rear) { front = -1; rear = -1; } /* Q has only one element, so we reset the queue after deleting it. */ else { front++; } cout << endl << "Deleted -> " << element << endl; return (element); } }
void display() { /* Function to display elements of Queue */ int i; if (isEmpty()) { cout << endl << "Empty Queue" << endl; } else { cout << endl << "Front index-> " << front; cout << endl << "Items -> "; for (i = front; i <= rear; i++) cout << items[i] << " "; cout << endl << "Rear index-> " << rear << endl; } } };
int main() { Queue q;
//deQueue is not possible on empty queue q.deQueue();
//enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5);
// 6th element can't be added to because the queue is full q.enQueue(6);
q.display();
//deQueue removes element entered first i.e. 1 q.deQueue();
//Now we have just 4 elements q.display();
return 0; }
2.2.6.Giới hạn của hàng đợi
Như bạn có thể thấy trong hình ảnh bên dưới, sau một chút thêm vào và loại bỏ hàng đợi, kích thước của hàng đợi đã được giảm bớt.
Giới hạn của hàng đợi
Và chúng ta chỉ có thể thêm các chỉ mục 0 và 1 khi hàng đợi được thiết lập lại (khi tất cả các phần tử đã được loại khỏi hàng đợi).
Sau khi REAR đạt đến chỉ mục cuối cùng, nếu chúng ta có thể lưu trữ các phần tử bổ sung trong các khoảng trống (0 và 1), chúng ta có thể sử dụng các khoảng trống. Điều này được thực hiện bằng một hàng đợi đã sửa đổi được gọi là hàng đợi vòng tròn.
2.2.7.Phân tích độ phức tạp
Độ phức tạp của các thao tác enqueue và dequeue trong hàng đợi sử dụng một mảng là O(1). Nếu bạn sử dụng pop(N) trong mã python, thì độ phức tạp có thể là O(n) tùy thuộc vào vị trí của mục cần được bật lên.
2.2.8.Ứng dụng của hàng đợi
Lên lịch CPU, Lên lịch đĩa
Khi dữ liệu được truyền không đồng bộ giữa hai quy trình. Hàng đợi được sử dụng để đồng bộ hóa. Ví dụ: Bộ đệm IO, đường ống, IO tệp, v.v.
Xử lý các ngắt trong hệ thống thời gian thực.
Hệ thống điện thoại của Trung tâm cuộc gọi sử dụng Hàng đợi để giữ cho những người gọi đến họ theo thứ tự.
ĐỌC THÊM VỀ Cấu trúc dữ liệu và thuật toán -CHƯƠNG II CẤU TRÚC DỮ LIỆU tại đây :
Biểu diễn FIFO của hàng đợi
