Визуализация, проектирование и анализ структуры данных очереди

Знать структуру данных Queue и ее операции.

Вы знаете, как работает система бронирования билетов? Ответ прост, в основном, он использует внутреннюю структуру данных очереди для постановки пользователей в очередь для бронирования билетов. В этой статье мы увидим структуру данных очереди и ее операции.

Я уже рассмотрел все алгоритмы сортировки и поиска. Вы можете найти их здесь.

Queue  – это Linear Data Structure, который следует определенному порядку выполнения операций.

Заказ First In First Out (FIFO). Примером очереди является билетная касса, где человек, который пришел первым, получает билет первым, а последний стоящий человек получает билет последним.

Мы можем выполнять следующие операции с очередью:

• Добавление элемента в end/rear очереди называется Enqueue.
• Удалить элемент из front очереди с именем Dequeue.

Операции с очередью:

В основном с очередью можно выполнять две операции:

1. Enqueue: Добавление элемента в конец или конец очереди.
2. Dequeue: Удаление элемента из начала очереди.

Есть несколько других операций, которые используются для реализации очереди:

1. IsEmpty: Проверьте, пуста ли очередь.
2. IsFull: Проверьте, заполнена ли очередь.
3. Peek: получить значение переднего элемента очереди, не удаляя его.

Давайте посмотрим, как работает очередь:

Для реализации Queue используются двухуказатели FRONT и REAR .

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

Обратите внимание, что изначально для FRONT и REAR задано значение -1.

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

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

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

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

Визуализация очереди:

Реализация очереди:

Вывод:

The Queue is Empty!!!
The element 10 added.
---------Queue content is : -----------
10 0 0 
---------------------------------------
The element 20 added.
---------Queue content is : -----------
10 20 0 
---------------------------------------
The element 30 added.
---------Queue content is : -----------
10 20 30 
---------------------------------------
The Queue is Full!!!
The item 10 removed.
---------Queue content is : -----------
0 20 30 
---------------------------------------
The item 20 removed.
---------Queue content is : -----------
0 0 30 
---------------------------------------
The item 30 removed.
---------Queue content is : -----------
0 0 0 
---------------------------------------
The Queue is Empty!!!

Анализ временной сложности:

Обе операции enQueue и deQueue выполняются в одном операторе. Эти операции занимают постоянное количество времени. Следовательно, временная сложность этих операций будет O(1).

Приложения:

• Очереди используются в алгоритмах планирования заданий/дисков в операционных системах.
• Операционная система использует очереди для (поставления в очередь сообщений, запросов ввода-вывода, движений мыши и т. д.).

Спасибо, что прочитали эту статью. Я надеюсь, что вы нашли эту статью полезной. Если да, то хлопните в ладоши, и вы можете прочитать другие статьи о структурах данных и алгоритмах, перечисленные ниже.