Циклическая очередь — это расширение базовой очереди, которую мы обсуждали ранее. Циклическая очередь также называют “кольцевой буфер”.
Что такое циклическая очередь в C ++?
Циклическая очередь — это линейная структура данных, которая используется для хранения элементов данных. Она выполняет операции, следуя подходу FIFO (первый вход, первый выход), и последняя позиция в очереди соединяется обратно с первой позицией, образуя круг или кольцо.
Циклическая очередь в C++
На следующей схеме показана циклическая очередь:
На приведенной выше схеме показана циклическая структура данных размером 10. Первые шесть элементов уже находятся в очереди, и мы видим, что первая позиция и последняя позиция соединены. Благодаря такому расположению пространство не тратится впустую, как это происходит в линейной очереди.
В линейной очереди после заполнения очереди мы удаляем элементы с другого конца, и статус очереди по-прежнему отображается как заполненный, и мы не можем вставить больше элементов.
В циклической очереди, когда очередь заполнена, и когда мы удаляем элементы спереди, поскольку последняя и первая позиции соединены, мы можем вставить элементы сзади, которые были освобождены путем удаления элемента.
Далее мы расскажем об основных операциях циклической очереди.
Основные операции
Некоторые из основных операций циклической очереди заключаются в следующем:
Front: возвращает начальную позицию в циклической очереди.
Rear: возвращает заднюю позицию в циклической очереди.
Enqueue: enqueue (значение) используется для вставки элемента в циклическую очередь. Элемент всегда вставляется в конец очереди.
Нам нужно выполнить следующую последовательность шагов, чтобы вставить новый элемент в циклическую очередь:
- Проверить, заполнена ли циклическая очередь: test ((rear == SIZE-1 && front == 0) || (rear == front-1)) , где ‘SIZE’ — это размер циклической очереди.
- Если циклическая очередь заполнена, то отображается сообщение “Очередь заполнена” (Queue is full). Если очередь не заполнена, проверить, является ли (rear == SIZE – 1 && front != 0). Если это верно, то установите rear=0 и вставьте элемент.
Dequeue: Функция удаления из очереди (Dequeue) используется для удаления элемента из очереди. В циклической очереди элемент всегда удаляется из внешнего интерфейса. Ниже приведена последовательность операций удаления из очереди в циклической очереди:
- Проверить, пуста ли циклическая очередь: проверить, если (front==-1).
- Если она пуста, отобразить сообщение “Очередь пуста”(Queue is empty). Если очередь не пуста, выполнить шаг 3.
- Проверить, если (front==rear). Если это верно, то установить front=rear= -1, еще проверить, если (front==size-1), если это верно, то установить front=0 и вернуть элемент.
Демонстрация
В этой части статьи мы подробно рассмотрим добавление / удаление элементов в циклической очереди.
Рассмотрим следующую циклическую очередь из 5 элементов, как показано ниже:
Далее мы вставляем элемент 1 в очередь:
Далее мы вставляем элемент со значением 3:
Когда мы вставим элементы для заполнения очереди, представление будет таким, как показано ниже:
Теперь мы удаляем два элемента, т.е. элемент 1 и элемент 3, из очереди, как показано ниже:
Затем мы вставляем или ставим в очередь элемент 11 в циклическую очередь, как показано ниже:
Теперь вставим элемент 13 в циклическую очередь. Очередь будет выглядеть так, как показано ниже:
Видно, что в циклической очереди мы перемещаем или вставляем элементы по кругу. Следовательно, мы можем использовать все пространство очереди, пока оно не заполнится.
Реализация
Давайте реализуем циклическую очередь с помощью C++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
#include<iostream> using namespace std; class Queue { public: // Инициализировать переднюю и заднюю части int rear, front; // Циклическая очередь int size; int *circular_queue; Queue(int sz) { front = rear = -1; size = sz; circular_queue = new int[sz]; } void enQueue(int elem); int deQueue(); void displayQueue(); }; /* Функция для создания циклической очереди */ void Queue::enQueue(int elem) { if ((front == 0 && rear == size-1) || (rear == (front-1)%(size-1))) { cout<<"\nQueue is Full"; return; } else if (front == -1) { /* Вставить первый элемент */ front = rear = 0; circular_queue[rear] = elem; } else if (rear == size-1 && front != 0) { rear = 0; circular_queue[rear] = elem; } else { rear++; circular_queue[rear] = elem; } } // Функция для удаления элемента из циклической очереди int Queue::deQueue() { if (front == -1) { cout<<"\nQueue is Empty"; return -1; } int data = circular_queue[front]; circular_queue[front] = -1; if (front == rear) { front = -1; rear = -1; } else if (front == size-1) front = 0; else front++; return data; } //отображение элементов циклической очереди void Queue::displayQueue() { if (front == -1) { cout<<"\nQueue is Empty"<<endl; return; } cout<<"\nCircular Queue elements: "; if (rear >= front) { for (int i = front; i <= rear; i++) cout<<circular_queue[i]<<" "; } Else { for (int i = front; i < size; i++) cout<<circular_queue[i]<<" "; for (int i = 0; i <= rear; i++) cout<<circular_queue[i]<<" "; } } //основная программа int main() { Queue pq(5); // Вставка элементов в циклическую очередь pq.enQueue(2); pq.enQueue(4); pq.enQueue(6); pq.enQueue(8); // Элементы отображения, присутствующие в циклической очереди pq.displayQueue(); // Удаление элементов из циклической очереди cout<<"\nElement Dequeued = "<<pq.deQueue(); cout<<"\nElement Dequeued = "<<pq.deQueue(); pq.displayQueue(); pq.enQueue(10); pq.enQueue(12); pq.enQueue(14); pq.displayQueue(); pq.enQueue(10); return 0; } |
Вывод данных:
| Circular Queue elements: 2 4 6 8 Element Dequeued = 2 Element Dequeued = 4 Circular Queue elements: 6 8 Circular Queue elements: 6 8 10 12 14 Queue is Full |
Выше показан результат операций циклической очереди. Сначала мы добавляем элементы, а затем удаляем два элемента из очереди. Далее мы вставляем или помещаем в очередь еще три элемента в циклическую очередь. Мы видим, что в отличие от линейной очереди, элементы добавляются в конце очереди.
Реализация связного списка
Теперь давайте обсудим реализацию циклической очереди в виде связного списка. Обратите внимание, что мы используем структуру для представления каждого узла. Операции такие же, как обсуждалось ранее, за исключением того, что в этом случае мы должны выполнять их в отношении узлов связного списка.
Выводные данные показывают циклическую очередь после операции постановки в очередь, удаления из очереди, а также после второй операции постановки в очередь:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
#include<iostream> using namespace std; struct Node { int data; struct Node* link; }; struct PQueue { struct Node *front, *rear; }; /* эта функция выполняет операцию постановки в очередь для циклической очереди */ void enQueue(PQueue *pq,int elem) { struct Node *temp = new Node; temp->data = elem; if (pq->front == NULL) pq->front = temp; else pq->rear->link = temp; pq->rear = temp; pq->rear->link = pq->front; } // Эта функция выполняет операцию удаления из очереди для циклической очереди int deQueue(PQueue *pq) { if (pq->front == NULL) { cout<<"Queue is empty!!"; return -1; } int elem; // элемент, подлежащий удалению из очереди // элемент является последним удаляемым узлом if (pq->front == pq->rear) { elem = pq->front->data; free(pq->front); pq->front = NULL; pq->rear = NULL; } else //более одного узла { struct Node *temp = pq->front; elem = temp->data; pq->front = pq->front->link; pq->rear->link= pq->front; free(temp); } return elem ; } //отображение элементов циклической очереди void displayQueue(struct PQueue *pq) { struct Node *temp = pq->front; while (temp->link != pq->front) { cout<<temp->data<<" "; temp = temp->link; } cout<<temp->data; } //основная программа int main() { // Создать циклическую и инициализировать front и rear PQueue *pq = new PQueue; pq->front = pq->rear = NULL; // Вставка/постановка элементов в циклическую очередь enQueue(pq, 1); enQueue(pq, 3); enQueue(pq, 5); cout<<"\nCircular Queue elements after enqueue operation: "; // Отображение элементов в циклической очереди displayQueue(pq); // Удаление/снятие элементов из циклической очереди cout<<"\nDequeued Item: "<<deQueue(pq); cout<<"\nDequeued Item: "<<deQueue(pq); cout<<"\nCircular Queue elements after two dequeue operation: "; // Оставшиеся элементы в циклической очереди после снятия с очереди displayQueue(pq); enQueue(pq, 7); enQueue(pq, 9); cout<<"\nCircular Queue elements after two enqueue operations: "; displayQueue(pq); return 0; } |
Вывод данных:
| Circular Queue elements after enqueue operation: 1 3 5 Dequeued Item: 1 Dequeued Item: 3 Circular Queue elements after two dequeue operation: 5 Circular Queue elements after two enqueue operations: 5 7 9 |
Следующая реализация — это программа на Java для демонстрации циклической очереди с использованием связного списка:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
import java.util.* ; class Main { // Структура узла static class Node { int data; Node link; } static class CQueue { Node front, rear; } // Операция постановки в очередь для циклической очереди static void enQueue(CQueue cq, int value) { Node temp = new Node(); temp .data = value; if (cq .front == null) cq .front = temp; else cq .rear .link = temp; cq .rear = temp; cq .rear .link = cq .front; } // Операция удаления из очереди для циклической очереди static int deQueue(CQueue cq) { if (cq .front == null) { System.out.printf ("Queue is empty!!"); return Integer.MIN_VALUE; } int value; // Значение, подлежащее удалению из очереди // последний узел, подлежащий удалению if (cq.front == cq.rear) { value = cq.front.data; cq.front = null; cq.rear = null; } else { // Существует более одного узла Node temp = cq.front; value = temp.data; cq.front = cq.front.link; cq.rear.link= cq.front; } return value ; } // отображение элементов циклической очереди static void displayQueue( CQueue cq) { Node temp = cq.front; while (temp.link != cq.front) { System.out.printf("%d ", temp.data); temp = temp.link; } System.out.printf("%d", temp.data); } /* основная программа */ public static void main(String args[]) { // Создать очередь и инициализировать front и rear CQueue cq = new CQueue(); cq.front = cq.rear = null; // Вставка/постановка элементов в циклическую очередь enQueue(cq, 2); enQueue(cq, 4); enQueue(cq, 6); System.out.print("\nCircular Queue elements after Enqueue Operation:"); // Отображение элементов в циклической очереди displayQueue(cq); // Удаление/снятие с очереди элементов из циклической очереди System.out.printf("\nDequeued Item = %d", deQueue(cq)); System.out.printf("\nDequeued Item = %d", deQueue(cq)); System.out.print("\nCircular Queue elements after Dequeue Operation:"); displayQueue(cq); enQueue(cq, 8); enQueue(cq, 10); System.out.print("\nCircular Queue elements after second Enqueue Operation:"); displayQueue(cq); } } |
Вывод данных:
| Circular Queue elements after Enqueue Operation: 2 4 6 Dequeued Item = 2 Dequeued Item = 4 Circular Queue element aft Dequeue Operation: 6 Circular Queue elements after second Enqueue Operation: 6 8 10 |
Выводные данные приведенной выше программы аналогичны предыдущей программе.
Применение
Давайте обсудим некоторые применения циклической очереди:
- Планирование процессора: процесс операционной системы, который требует, чтобы произошло какое-либо событие или завершились некоторые другие процессы для выполнения, часто поддерживающихся в циклической очереди, так что они выполняются один за другим, когда выполняются все условия или когда происходят все события.
- Управление памятью: использование обычных очередей приводит к потере места в памяти. Использование циклической очереди для управления памятью полезно для оптимального использования памяти.
- Система светофоров с компьютерным управлением: компьютеризированные сигналы светофора часто добавляются в круговую очередь, чтобы они повторялись по истечении заданного интервала времени.
Итог
Циклические очереди устраняют основной недостаток базовой очереди, в которой мы не можем вставлять элементы, когда задний указатель находится в конце очереди, даже когда мы удаляем элементы и пространство освобождается. В циклической очереди элементы расположены по кругу, так что пространство вообще не тратится впустую.
Мы также рассмотрели основные операции циклической очереди. Циклические очереди в основном полезны для целей планирования и приложений, таких как системы светофоров, где сигналы светятся по очереди.
В нашей следующей статье мы расскажем о двухсторонней очереди, которая называется “deque”.
С Уважением, МониторБанк