Очередь — это базовая структура данных, такая же, как и стек. В отличие от стека, который использует подход LIFO, очередь (queue) использует подход FIFO (первый вход, первый выход). При таком подходе первый элемент, добавляемый в очередь, является первым элементом, удаляемым из очереди. Как и стек, очередь также является линейной структурой данных.
В реальной аналогии мы можем представить себе автобусную очередь, где пассажиры ждут автобуса в очереди. Первый пассажир в очереди входит в автобус первым, поскольку этот пассажир оказывается тем, кто пришел на остановку первым.
В терминах программного обеспечения очередь можно рассматривать как набор или коллекцию элементов, как показано ниже. Элементы расположены линейно:
На схеме есть два указателя, то есть “передний” и “задний” очереди. Когда очередь пуста, то обоим указателям присваивается значение -1.
Указатель «rear» (задний) — это место, откуда элементы вставляются в очередь. Операция добавления / вставки элементов в очередь называется “постановкой в очередь” (enqueue).
Указатель «front» (передний) — это место, откуда элементы удаляются из очереди. Операция по удалению / удалению элементов из очереди называется “удалением из очереди” (dequeue).
Когда значение заднего указателя равно size-1, мы говорим, что очередь заполнена. Когда начальное значение равно нулю, очередь пуста.
Основные операции
Структура данных очереди включает в себя следующие операции:
- EnQueue: добавляет элемент в очередь. Добавление элемента в очередь всегда выполняется в конце очереди.
- DeQueue: удаляет элемент из очереди. Элемент всегда удаляется из очереди в начале очереди.
- isEmpty: проверяет, пуста ли очередь.
- isFull: проверяет, заполнена ли очередь.
- peek: возвращает элемент в начало очереди, не удаляя его.
Постановка в очередь
В этом процессе выполняются следующие шаги:
- Проверить, заполнена ли очередь.
- Если заполнена, выдать ошибку переполнения и завершить работу.
- В противном случае увеличить значение ‘rear’.
- Добавить элемент в местоположение, указанное ‘rear’.
- Выполнено успешно.
Удаление из очереди
Операция удаления из очереди состоит из следующих шагов:
- Проверить, пуста ли очередь.
- Если пуста, отобразить ошибку переполнения и завершить работу.
- В противном случае элемент доступа указывается с помощью ‘front’ .
- Увеличить «начало», чтобы указать на следующие доступные данные.
- Выполнено успешно.
Далее мы продемонстрируем операции вставки и удаления в очереди.
Демонстрация
Это пустая очередь, и, таким образом, мы имеем задний указатель и пустую очередь, равную -1.
Далее мы добавляем 1 в очередь, и в результате задний указатель перемещается вперед на одно местоположение:
На следующей схеме мы добавляем элемент 2 в очередь, перемещая задний указатель вперед на еще одно местоположение (приращение):
На следующей схеме мы добавляем элемент 3 и перемещаем задний указатель на 1:
На этом этапе задний указатель имеет значение 2, в то время как передний указатель находится на нулевом местоположении.
Далее мы удаляем элемент, на который указывает передний указатель. Поскольку передний указатель равен 0, удаляемый элемент равен 1.
Таким образом, первый элемент, введенный в очередь, т.е. 1, оказывается первым элементом, удаленным из очереди. В результате, после первого удаления из очереди, передний указатель теперь будет перемещен вперед на следующее местоположение, которое равно 1.
Реализация массива для очереди
Давайте реализуем структуру данных очереди, используя 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 |
#include <iostream> #define MAX_SIZE 5 using namespace std; class Queue { private: int myqueue[MAX_SIZE], front, rear; public: Queue(){ front = -1; rear = -1; } boolisFull(){ if(front == 0 && rear == MAX_SIZE - 1){ return true; } return false; } boolisEmpty(){ if(front == -1) return true; else return false; } void enQueue(int value){ if(isFull()){ cout << endl<< "Queue is full!!"; } else { if(front == -1) front = 0; rear++; myqueue[rear] = value; cout << value << " "; } } int deQueue(){ int value; if(isEmpty()){ cout << "Queue is empty!!" << endl; return(-1); } else { value = myqueue[front]; if(front >= rear){ //only one element in queue front = -1; rear = -1; } else { front++; } cout << endl << "Deleted => " << value << " from myqueue"; return(value); } } /* Функция для отображения элементов очереди */ void displayQueue() { int i; if(isEmpty()) { cout << endl << "Queue is Empty!!" << endl; } else { cout << endl << "Front = " << front; cout << endl << "Queue elements : "; for(i=front; i<=rear; i++) cout << myqueue[i] << "\t"; cout << endl << "Rear = " << rear << endl; } } }; int main() { Queue myq; myq.deQueue(); //deQueue cout<<"Queue created:"<<endl; myq.enQueue(10); myq.enQueue(20); myq.enQueue(30); myq.enQueue(40); myq.enQueue(50); //enqueue 60 => queue is full myq.enQueue(60); myq.displayQueue(); //deQueue =>удаляет 10 myq.deQueue(); //queue после dequeue myq.displayQueue(); return 0; } |
Вывод данных:
| Queue is empty!! Queue created: 10 20 30 40 50 Queue is full!! Front = 0 Queue elements : 10 20 30 40 50 Rear = 4 Deleted => 10 from myqueue Front = 1 Queue elements: 20 30 40 50 Rear = 4 |
Приведенная выше реализация показывает очередь, представленную в виде массива. Мы указываем max_size для массива, также определяем операции постановки в очередь и удаления из очереди, а также операции isFull и isEmpty.
Ниже приведена реализация на 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 |
// Класс, представляющий очередь class Queue { int front, rear, size; int max_size; int myqueue[]; public Queue(int max_size) { this.max_size = max_size; front = this.size = 0; rear = max_size - 1; myqueue = new int[this.max_size]; } //если размер = max_size, очередь заполнена boolean isFull(Queue queue) { return (queue.size == queue.max_size); } // размер = 0, очередь пуста boolean isEmpty(Queue queue) { return (queue.size == 0); } // постановка в очередь - добавление элемента в очередь void enqueue( int item) { if (isFull(this)) return; this.rear = (this.rear + 1)%this.max_size; this.myqueue[this.rear] = item; this.size = this.size + 1; System.out.print(item + " " ); } // dequeue - удаление элемента из очереди int dequeue() { if (isEmpty(this)) return Integer.MIN_VALUE; int item = this.myqueue[this.front]; this.front = (this.front + 1)%this.max_size; this.size = this.size - 1; return item; } // перемещение в начало очереди int front() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue[this.front]; } // перемещение в конец очереди int rear() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue[this.rear]; } } // основной класс class Main { public static void main(String[] args) { Queue queue = new Queue(1000); System.out.println("Queue created as:"); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); queue.enqueue(40); System.out.println("\nElement " + queue.dequeue() + " dequeued from queue\n"); System.out.println("Front item is " + queue.front()); System.out.println("Rear item is " + queue.rear()); } } |
Вывод данных:
| Queue created as: 10 20 30 40 Element 10 dequeued from queue Front item is 20 Rear item is 40 |
Приведенная выше реализация аналогична реализации на C++.
Далее давайте реализуем очередь на 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 |
#include <iostream> using namespace std; struct node { int data; struct node *next; }; struct node* front = NULL; struct node* rear = NULL; struct node* temp; void Insert(int val) { if (rear == NULL) { rear = new node; rear->next = NULL; rear->data = val; front = rear; } else { temp=new node; rear->next = temp; temp->data = val; temp->next = NULL; rear = temp; } } void Delete() { temp = front; if (front == NULL) { cout<<"Queue is empty!!"<<endl; } else if (temp->next != NULL) { temp = temp->next; cout<<"Element deleted from queue is : "<<front->data<<endl; free(front); front = temp; } else { cout<<"Element deleted from queue is : "<<front->data<<endl; free(front); front = NULL; rear = NULL; } } void Display() { temp = front; if ((front == NULL) && (rear == NULL)) { cout<<"Queue is empty"<<endl; return; } while (temp != NULL) { cout<<temp->data<<" "; temp = temp->next; } cout<<endl; } int main() { cout<<"Queue Created:"<<endl; Insert(10); Insert(20); Insert(30); Insert(40); Insert(50); Display(); Delete(); cout<<"Queue after one deletion: "<<endl; Display(); return 0; } |
Вывод данных:
| Queue Created: 10 20 30 40 50 Element deleted from queue is: 10 Queue after one deletion: 20 30 40 50 |
Стек или очередь
Стеки и очереди являются вторичными структурами данных, которые могут использоваться для хранения данных. Они могут быть запрограммированы с использованием первичных структур данных, таких как массивы и связанные списки. Подробно рассмотрев обе структуры данных, пришло время обсудить основные различия между этими двумя структурами данных.
| Стек | Очередь |
| Использует подход LIFO (последний вход, первый выход). | Использует подход FIFO (первый вход, первый выход). |
| Элементы добавляются или удаляются только с одного конца, называемого «Вершиной стека». | Элементы добавляются из “rear” конца очереди и удаляются из “front» части очереди. |
| Основными операциями для стека являются “push” и “pop”. | Основными операциями для очереди являются “enqueue” и “dequeue”. |
| Мы можем выполнять все операции со стеком, поддерживая только один указатель для доступа к вершине стека. | В очередях нам нужно поддерживать два указателя: один для доступа к началу очереди, а второй для доступа к задней части очереди. |
| Стек в основном используется для решения рекурсивных задач. | Очереди используются для решения проблем, связанных с упорядоченной обработкой. |
Применение queue (очереди)
Давайте обсудим различные применения структуры данных очереди:
- Структура данных очереди используется в различных процессорах и дисковых расписаниях. Есть несколько задач, требующих процессора или диска одновременно. Время процессора или диска запланировано для каждой задачи с использованием очереди.
- Очередь также может использоваться для буферизации печати, при которой количество заданий печати помещается в очередь.
- Обработка прерываний в системах реального времени выполняется с использованием структуры данных очереди. Прерывания обрабатываются в порядке их поступления.
- Поиск по ширине, при котором обходятся соседние узлы дерева перед переходом на следующий уровень, использует очередь для реализации.
- Телефонные системы центров обработки вызовов используют очереди для удержания вызовов до тех пор, пока на них не ответят представители службы.
В общем, можно сказать, что структура данных очереди используется всякий раз, когда мы требуем, чтобы ресурсы или элементы обслуживались в порядке их поступления.
Итог
Очередь — это структура данных FIFO (первый вход, первый выход), которая в основном используется в ресурсах, где требуется планирование. Очередь имеет два указателя сзади и спереди на двух концах, и они используются для вставки элемента и удаления элемента в / из очереди соответственно.
В нашей следующей статье мы поговорим о структуре данных приоритетной очереди в C++.
С Уважением, МониторБанк