На этом шаге мы дадим общую характеристику очереди.
Отметим, что очередь - динамическая структура данных, так как с течением времени длина очереди (количество входящих в нее звеньев) изменяется. Например, все мы знакомы с очередью людей у кассы в магазине самообслуживания или очередью автомобилей у бензозаправочной станции. Вновь прибывшие становятся в один конец очереди и покидают ее после оплаты покупок или заправки с другого.
Другой, возможно более уместный, пример очереди может быть обнаружен в вычислительной системе с разделением времени, с которой одновременно работает несколько пользователей. Поскольку такая система обычно имеет единственный центральный процессор и одну основную память, то эти ресурсы должны разделяться среди пользователей путем выделения короткого интервала времени на выполнение программы одного пользователя, за которым следует выполнение программы другого пользователя и так далее до тех пор, пока не будет вновь выполняться программа первого пользователя. Программы пользователей, ожидающие своего выполнения, образуют очередь ожидания. Управление такой очередью необязательно должно основываться на принципе "первым пришел" - "первым вышел", а можно использовать некоторую сложную приоритетную схему, учитывающую такие факторы, как используемый компилятор, требуемое время выполнения, желаемое число строк, выводимых на печать и так далее.
На следующем шаге мы рассмотрим формирование очереди.
