Циклическая структура данных очереди

Содержание

Как работает круговая очередь
Циклические операции с очередями
Реализации круговой очереди в Python, Java, C и C ++
Анализ сложности циклической очереди
Приложения круговой очереди

В этом руководстве вы узнаете, что такое круговая очередь. Также вы найдете реализацию циклической очереди в C, C ++, Java и Python.

Циклическая очередь позволяет избежать потери места в обычной реализации очереди с использованием массивов.

Ограничение обычной очереди

Как вы можете видеть на изображении выше, после некоторого постановки и удаления из очереди размер очереди был уменьшен.

Индексы 0 и 1 могут использоваться только после сброса очереди, когда все элементы удалены из очереди.

Как работает круговая очередь

Циклическая очередь работает по принципу циклического увеличения, т.е. когда мы пытаемся увеличить указатель и достигаем конца очереди, мы начинаем с начала очереди.

Здесь циклическое приращение выполняется делением по модулю с размером очереди. Это,

 если REAR + 1 == 5 (переполнение!), REAR = (REAR + 1)% 5 = 0 (начало очереди)

Круговое представление очереди

Циклические операции с очередями

Круговая очередь работает следующим образом:

два указателя FRONT и REAR
FRONT отслеживает первый элемент очереди
REAR отслеживает последние элементы очереди
изначально установите значение FRONT и REAR на -1

1. Операция постановки в очередь

проверьте, заполнена ли очередь
для первого элемента установите значение FRONT на 0
циклически увеличивайте индекс REAR на 1 (т.е. если задняя часть достигает конца, она будет в начале очереди)
добавить новый элемент в позицию, указанную REAR

2. Операция удаления из очереди

проверьте, пуста ли очередь
вернуть значение, указанное FRONT
по кругу увеличивайте индекс FRONT на 1
для последнего элемента сбросьте значения FRONT и REAR на -1

Однако при проверке полной очереди появился новый дополнительный случай:

Случай 1: FRONT = 0 && REAR == SIZE - 1
Случай 2: FRONT = REAR + 1

Второй случай происходит, когда REAR начинается с 0 из-за циклического приращения и когда его значение всего на 1 меньше, чем FRONT, очередь заполнена.

Операции Enque и Deque

Реализации круговой очереди в Python, Java, C и C ++

Наиболее распространенная реализация очереди использует массивы, но ее также можно реализовать с помощью списков.

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; )