Структура данных и алгоритмы - очередь
Очередь - это абстрактная структура данных, несколько похожая на стеки. В отличие от стеков, очередь открыта с обоих концов. Один конец всегда используется для вставки данных (постановка в очередь), а другой - для удаления данных (снятие очереди). Очередь следует методологии «первым пришел - первым обслужен», то есть элемент данных, сохраненный первым, будет доступен первым.

Реальным примером очереди может быть дорога с односторонним движением с односторонним движением, на которой транспортное средство въезжает первым, выезжает первым. Более реальные примеры можно увидеть в виде очередей в кассах и на автобусных остановках.
Представление очереди
Как мы теперь понимаем, в очереди мы получаем доступ к обоим концам по разным причинам. Следующая диаграмма, приведенная ниже, пытается объяснить представление очереди как структуру данных -

Как и в стеках, очередь также может быть реализована с использованием массивов, связанных списков, указателей и структур. Для простоты мы будем реализовывать очереди, используя одномерный массив.
Основные операции
Операции с очередями могут включать инициализацию или определение очереди, ее использование, а затем полное удаление из памяти. Здесь мы попытаемся понять основные операции, связанные с очередями -
enqueue () - добавить (сохранить) элемент в очередь.
dequeue () - удалить (получить доступ) элемент из очереди.
Еще несколько функций требуется, чтобы сделать вышеупомянутую работу очереди эффективной. Это -
peek () - получает элемент в начале очереди, не удаляя его.
isfull () - Проверяет, заполнена ли очередь.
isempty () - Проверяет, пуста ли очередь.
В очереди мы всегда удаляем данные (или обращаемся к ним), на которые указывает передний указатель, и, помещая (или сохраняя) данные в очередь, мы пользуемся задним указателем.
Давайте сначала узнаем о вспомогательных функциях очереди -
PEEK ()
Эта функция помогает видеть данные в начале очереди. Алгоритм функции peek () выглядит следующим образом:
Алгоритм
begin procedure peek return queue[front] end procedure
Реализация функции peek () на языке программирования C -
пример
int peek() { return queue[front]; }
полон()
Поскольку мы используем массив одного измерения для реализации очереди, мы просто проверяем наличие заднего указателя в MAXSIZE, чтобы определить, что очередь заполнена. Если мы будем поддерживать очередь в круговом связанном списке, алгоритм будет отличаться. Алгоритм функции isfull () -
Алгоритм
begin procedure isfull if rear equals to MAXSIZE return true else return false endif end procedure
Реализация функции isfull () на языке программирования C -
пример
bool isfull() { if(rear == MAXSIZE - 1) return true; else return false; }
пустой()
Алгоритм функции isempty () -
Алгоритм
begin procedure isempty if front is less than MIN OR front is greater than rear return true else return false endif end procedure
Если значение front меньше MIN или 0, это говорит о том, что очередь еще не инициализирована и, следовательно, пуста.
Вот программный код C -
пример
bool isempty() { if(front < 0 || front > rear) return true; else return false; }
Операция постановки в очередь
Очереди поддерживают два указателя данных, спереди и сзади . Поэтому его операции сравнительно сложны для реализации, чем операции со стеками.
Для постановки (вставки) данных в очередь необходимо выполнить следующие шаги:
Шаг 1 - Проверьте, заполнена ли очередь.
Шаг 2 - Если очередь заполнена, выведите ошибку переполнения и выйдите.
Шаг 3 - Если очередь не заполнена, увеличьте задний указатель, чтобы указать следующий пустой пробел.
Шаг 4 - Добавьте элемент данных в расположение очереди, куда указывает указатель.
Шаг 5 - верните успех.

Иногда мы также проверяем, инициализирована очередь или нет, для обработки любых непредвиденных ситуаций.
Алгоритм постановки в очередь
procedure enqueue(data) if queue is full return overflow endif rear ← rear + 1 queue[rear] ← data return true end procedure
Реализация enqueue () на языке программирования C -
пример
int enqueue(int data) if(isfull()) return 0; rear = rear + 1; queue[rear] = data; return 1; end procedure
Операция Dequeue
Доступ к данным из очереди представляет собой процесс двух задач - получить доступ к данным, куда указывает фронт, и удалить данные после доступа. Для выполнения операции удаления очереди предпринимаются следующие шаги:
Шаг 1 - Проверьте, пуста ли очередь.
Шаг 2 - Если очередь пуста, выдайте ошибку недостаточного значения и выйдите.
Шаг 3 - Если очередь не пуста, получите доступ к данным, куда указывает фронт .
Шаг 4 - Увеличьте передний указатель, чтобы он указывал на следующий доступный элемент данных.
Шаг 5 - Верните успех.

Алгоритм работы с дежурной
procedure dequeue if queue is empty return underflow end if data = queue[front] front ← front + 1 return true end procedure
Реализация dequeue () на языке программирования C -
пример
int dequeue() { if(isempty()) return 0; int data = queue[front]; front = front + 1; return data; }
Для полной программы Queue на языке программирования C, пожалуйста, нажмите здесь .