Очередь — это абстрактная структура данных, несколько похожая на стеки. В отличие от стеков, очередь открыта с обоих концов. Один конец всегда используется для вставки данных (постановка в очередь), а другой — для удаления данных (снятие очереди). Очередь следует методологии «первым пришел — первым обслужен», то есть элемент данных, сохраненный первым, будет доступен первым.
Реальным примером очереди может быть дорога с односторонним движением с односторонним движением, на которой транспортное средство въезжает первым, выезжает первым. Более реальные примеры можно увидеть в виде очередей в кассах и автобусных остановках.
Представление очереди
Как мы теперь понимаем, в очереди мы получаем доступ к обоим концам по разным причинам. Следующая диаграмма, приведенная ниже, пытается объяснить представление очереди как структуру данных —
Как и в стеках, очередь также может быть реализована с использованием массивов, связанных списков, указателей и структур. Для простоты мы будем реализовывать очереди, используя одномерный массив.
Основные операции
Операции с очередями могут включать в себя инициализацию или определение очереди, ее использование, а затем полное удаление из памяти. Здесь мы попытаемся понять основные операции, связанные с очередями —
-
enqueue () — добавить (сохранить) элемент в очередь.
-
dequeue () — удалить (получить доступ) элемент из очереди.
enqueue () — добавить (сохранить) элемент в очередь.
dequeue () — удалить (получить доступ) элемент из очереди.
Еще несколько функций требуется, чтобы сделать вышеупомянутую работу очереди эффективной. Это —
-
peek () — получает элемент в начале очереди, не удаляя его.
-
isfull () — Проверяет, заполнена ли очередь.
-
isempty () — Проверяет, пуста ли очередь.
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 — верните успех.
Шаг 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 — Верните успех.
Шаг 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, пожалуйста, нажмите здесь .