Cấu trúc dữ liệu hàng đợi tròn

Trong hướng dẫn này, bạn sẽ tìm hiểu hàng đợi tròn là gì. Ngoài ra, bạn sẽ tìm thấy việc triển khai hàng đợi vòng tròn trong C, C ++, Java và Python.

Hàng đợi tròn tránh lãng phí không gian trong việc triển khai hàng đợi thông thường bằng cách sử dụng mảng.

Giới hạn của Hàng đợi thông thường

Như bạn có thể thấy trong hình trên, 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.

Chỉ mục 0 và 1 chỉ có thể được sử dụng sau khi hàng đợi được đặt lại khi tất cả các phần tử đã được xếp lại hàng.

Cách hoạt động của hàng đợi vòng tròn

Hàng đợi tròn hoạt động theo quy trình tăng vòng tròn, tức là khi chúng ta cố gắng tăng con trỏ và chúng ta đến cuối hàng đợi, chúng ta bắt đầu từ đầu hàng đợi.

Ở đây, sự gia tăng vòng tròn được thực hiện bằng phép chia modulo với kích thước hàng đợi. Đó là,

 nếu REAR + 1 == 5 (tràn!), REAR = (REAR + 1)% 5 = 0 (bắt đầu hàng đợi)
Biểu diễn hàng đợi tròn

Hoạt động hàng đợi vòng tròn

Hàng đợi vòng tròn 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 các 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

1. Hoạt động Enqueue

  • kiểm tra xem hàng đợi đã đầy chưa
  • cho phần tử đầu tiên, đặt giá trị của FRONT thành 0
  • tăng chỉ số REAR theo vòng tròn lên 1 (tức là nếu phía sau về cuối, tiếp theo nó sẽ ở đầu hàng đợi)
  • thêm phần tử mới vào vị trí được trỏ tới bởi REAR

2. 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 theo vòng tròn 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

Tuy nhiên, việc kiểm tra hàng đợi đầy đủ có một trường hợp bổ sung mới:

  • Trường hợp 1: FRONT = 0 && REAR == SIZE - 1
  • Trường hợp 2: FRONT = REAR + 1

Trường hợp thứ hai xảy ra khi REAR bắt đầu từ 0 do tăng theo vòng tròn và khi giá trị của nó chỉ nhỏ hơn 1 so với FRONT, hàng đợi đã đầy.

Hoạt động Enque và Deque

Triển khai hàng đợi vòng tròn trong Python, Java, C và C ++

Việc triển khai hàng đợi phổ biến nhất là sử dụng mảng, nhưng nó cũng có thể được triển khai bằng cách sử dụng danh sách.

Python Java C C + 
 # Circular Queue implementation in Python class MyCircularQueue(): def __init__(self, k): self.k = k self.queue = (None) * k self.head = self.tail = -1 # Insert an element into the circular queue def enqueue(self, data): if ((self.tail + 1) % self.k == self.head): print("The circular queue is full") elif (self.head == -1): self.head = 0 self.tail = 0 self.queue(self.tail) = data else: self.tail = (self.tail + 1) % self.k self.queue(self.tail) = data # Delete an element from the circular queue def dequeue(self): if (self.head == -1): print("The circular queue is empty") elif (self.head == self.tail): temp = self.queue(self.head) self.head = -1 self.tail = -1 return temp else: temp = self.queue(self.head) self.head = (self.head + 1) % self.k return temp def printCQueue(self): if(self.head == -1): print("No element in the circular queue") elif (self.tail>= self.head): for i in range(self.head, self.tail + 1): print(self.queue(i), end=" ") print() else: for i in range(self.head, self.k): print(self.queue(i), end=" ") for i in range(0, self.tail + 1): print(self.queue(i), end=" ") print() # Your MyCircularQueue object will be instantiated and called as such: obj = MyCircularQueue(5) obj.enqueue(1) obj.enqueue(2) obj.enqueue(3) obj.enqueue(4) obj.enqueue(5) print("Initial queue") obj.printCQueue() obj.dequeue() print("After removing an element from the queue") obj.printCQueue() 
 // Circular Queue implementation in Java public class CQueue ( int SIZE = 5; // Size of Circular Queue int front, rear; int items() = new int(SIZE); CQueue() ( front = -1; rear = -1; ) // Check if the queue is full boolean isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) if (front == rear + 1) ( return true; ) return false; ) // Check if the queue is empty boolean isEmpty() ( if (front == -1) return true; else return false; ) // Adding an element void enQueue(int element) ( if (isFull()) ( System.out.println("Queue is full"); ) else ( if (front == -1) front = 0; rear = (rear + 1) % SIZE; items(rear) = element; System.out.println("Inserted " + element); ) ) // Removing an 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 = (front + 1) % SIZE; ) return (element); ) ) void display() ( /* Function to display status of Circular Queue */ int i; if (isEmpty()) ( System.out.println("Empty Queue"); ) else ( System.out.println("Front -> " + front); System.out.println("Items -> "); for (i = front; i != rear; i = (i + 1) % SIZE) System.out.print(items(i) + " "); System.out.println(items(i)); System.out.println("Rear -> " + rear); ) ) public static void main(String() args) ( CQueue q = new CQueue(); // Fails because front = -1 q.deQueue(); q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // Fails to enqueue because front == 0 && rear == SIZE - 1 q.enQueue(6); q.display(); int elem = q.deQueue(); if (elem != -1) ( System.out.println("Deleted Element is " + elem); ) q.display(); q.enQueue(7); q.display(); // Fails to enqueue because front == rear + 1 q.enQueue(8); ) )
 // Circular Queue implementation in C #include #define SIZE 5 int items(SIZE); int front = -1, rear = -1; // Check if the queue is full int isFull() ( if ((front == rear + 1) || (front == 0 && rear == SIZE - 1)) return 1; return 0; ) // Check if the queue is empty int isEmpty() ( if (front == -1) return 1; return 0; ) // Adding an element void enQueue(int element) ( if (isFull()) printf(" Queue is full!! "); else ( if (front == -1) front = 0; rear = (rear + 1) % SIZE; items(rear) = element; printf(" Inserted -> %d", element); ) ) // Removing an element int deQueue() ( int element; if (isEmpty()) ( printf(" 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 dequeing it. ? else ( front = (front + 1) % SIZE; ) printf(" Deleted element -> %d ", element); return (element); ) ) // Display the queue void display() ( int i; if (isEmpty()) printf(" Empty Queue"); else ( printf(" Front -> %d ", front); printf(" Items -> "); for (i = front; i != rear; i = (i + 1) % SIZE) ( printf("%d ", items(i)); ) printf("%d ", items(i)); printf(" Rear -> %d ", rear); ) ) int main() ( // Fails because front = -1 deQueue(); enQueue(1); enQueue(2); enQueue(3); enQueue(4); enQueue(5); // Fails to enqueue because front == 0 && rear == SIZE - 1 enQueue(6); display(); deQueue(); display(); enQueue(7); display(); // Fails to enqueue because front == rear + 1 enQueue(8); return 0; )
 // Circular Queue implementation in C++ #include #define SIZE 5 /* Size of Circular Queue */ using namespace std; class Queue ( private: int items(SIZE), front, rear; public: Queue() ( front = -1; rear = -1; ) // Check if the queue is full bool isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) if (front == rear + 1) ( return true; ) return false; ) // Check if the queue is empty bool isEmpty() ( if (front == -1) return true; else return false; ) // Adding an element void enQueue(int element) ( if (isFull()) ( cout << "Queue is full"; ) else ( if (front == -1) front = 0; rear = (rear + 1) % SIZE; items(rear) = element; cout << endl << "Inserted " << element << endl; ) ) // Removing an element 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 = (front + 1) % SIZE; ) return (element); ) ) void display() ( // Function to display status of Circular Queue int i; if (isEmpty()) ( cout << endl << "Empty Queue" << endl; ) else ( cout < " << front; cout << endl < "; for (i = front; i != rear; i = (i + 1) % SIZE) cout << items(i); cout << items(i); cout << endl < " << rear; ) ) ); int main() ( Queue q; // Fails because front = -1 q.deQueue(); q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // Fails to enqueue because front == 0 && rear == SIZE - 1 q.enQueue(6); q.display(); int elem = q.deQueue(); if (elem != -1) cout << endl << "Deleted Element is " << elem; q.display(); q.enQueue(7); q.display(); // Fails to enqueue because front == rear + 1 q.enQueue(8); return 0; )

Phân tích độ phức tạp của hàng đợi tròn

Độ phức tạp của các hoạt động xếp hàng và xếp hàng của một hàng đợi tròn là O (1) cho (triển khai mảng).

Các ứng dụng của Hàng đợi Vòng tròn

  • Lập lịch CPU
  • Quản lý bộ nhớ
  • Quản lý giao thông

thú vị bài viết...