Trong hướng dẫn này, bạn sẽ tìm hiểu hàng đợi là gì. Ngoài ra, bạn sẽ tìm thấy việc triển khai hàng đợi trong C, C ++, Java và Python.
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ư việc xếp hàng mua vé bên ngoài sảnh rạp chiếu phim, nơi người đầu tiên vào hàng là người đầu tiên nhận được vé.
Hàng đợi tuân theo quy tắc Nhập trước Xuất trước (FIFO) - mục đi vào trước là mục xuất hiện trước.
FIFO đại diện cho hàng đợi
Trong hình trên, vì 1 được giữ trong hàng đợi trước 2 nên nó cũng là cái đầu tiên bị 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 bằng bất kỳ ngôn ngữ lập trình nào như C, C ++, Java, Python hoặc C #, nhưng đặc điểm kỹ thuật là khá giống nhau.
Các hoạt động cơ bản của hàng đợi
Hàng đợi là một đối tượng (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 hàng đợi
- IsEmpty : Kiểm tra xem hàng đợi có trống không
- IsFull : Kiểm tra xem hàng đợi đã đầy chưa
- Peek : Nhận giá trị phía trước của hàng đợi mà không cần xóa nó
Làm việc của hàng đợi
Các hoạt động hàng đợi hoạt động như sau:
- hai con trỏ FRONT và REAR
- TRƯỚC 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
Hoạt động Enqueue
- kiểm tra xem hàng đợi đã đầy chưa
- đối với phần tử đầu tiên, hãy đặ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
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
- cho phần tử cuối cùng, đặt lại các giá trị của FRONT và REAR thành -1
Hoạt động đặt hàng và xếp hàng
Triển khai hàng đợi bằng Python, Java, C và C ++
Chúng tôi 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 tôi sử dụng danh sách.
Python Java C C ++ # Queue implementation in Python class Queue: def __init__(self): self.queue = () # Add an element def enqueue(self, item): self.queue.append(item) # Remove an element def dequeue(self): if len(self.queue) < 1: return None return self.queue.pop(0) # Display the queue def display(self): print(self.queue) def size(self): return len(self.queue) q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.display() q.dequeue() print("After removing an element") q.display()
// Queue implementation in Java public class Queue ( int SIZE = 5; int items() = new int(SIZE); int front, rear; Queue() ( front = -1; rear = -1; ) boolean isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) boolean isEmpty() ( if (front == -1) return true; else return false; ) 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("Front index-> " + front); System.out.println("Items -> "); for (i = front; i " + 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(); // Now we have just 4 elements q.display(); ) )
// Queue implementation in C #include #define SIZE 5 void enQueue(int); void deQueue(); void display(); int items(SIZE), front = -1, rear = -1; 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("Queue is Full!!"); else ( if (front == -1) front = 0; rear++; items(rear) = value; printf("Inserted -> %d", value); ) ) void deQueue() ( if (front == -1) printf("Queue is Empty!!"); else ( printf("Deleted : %d", items(front)); front++; if (front> rear) front = rear = -1; ) ) // Function to print the queue void display() ( if (rear == -1) printf("Queue is Empty!!!"); else ( int i; printf("Queue elements are:"); for (i = front; i <= rear; i++) printf("%d ", items(i)); ) printf(""); )
// Queue implementation in C++ #include #define SIZE 5 using namespace std; class Queue ( private: int items(SIZE), front, rear; public: Queue() ( front = -1; rear = -1; ) bool isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) bool isEmpty() ( if (front == -1) return true; else return false; ) 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" <= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) cout << endl < " << 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; cout << endl < "; for (i = front; i <= rear; i++) cout << items(i) << " "; cout << endl < " << 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; )
Hạn chế của hàng đợi
Như bạn có thể thấy trong hình dưới đây, sau một chút sắp xếp và xếp thứ tự, kích thước của hàng đợi đã được giảm xuống.
Giới hạn 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 đặt lại (khi tất cả các phần tử đã được xếp lại hàng).
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ử thừa trong các không gian trống (0 và 1), chúng ta có thể tận dụng các không gian trống. Điều này được thực hiện bởi một hàng đợi đã sửa đổi được gọi là hàng đợi vòng tròn.
Phân tích độ phức tạp
Độ phức tạp của các hoạt động xếp hàng và xếp hàng trong hàng đợi sử dụng một mảng là O(1).
Ứng dụng của hàng đợi
- Lập lịch CPU, Lập lịch đĩa
- Khi dữ liệu được truyền không đồng bộ giữa hai tiến trình, hàng đợi được sử dụng để đồng bộ hóa. Ví dụ: Bộ đệm IO, đường ống, tệp IO, v.v.
- Xử lý ngắt trong hệ thống thời gian thực.
- Hệ thống điện thoại Call Center sử dụng Hàng đợi để giữ những người đang gọi cho họ theo thứ tự.
Bài đọc được đề xuất
- Các loại hàng đợi
- Hàng đợi vòng tròn
- Cấu trúc dữ liệu Deque
- Hàng đợi ưu tiên
