Вы, должно быть, уже слышали о queue. Когда вы подаете заявку на курс во время периода добавления/удаления в колледже, вы ставитесь в очередь (лист ожидания), если квота заполнена. Затем учащиеся, которые приходят первыми, попадают на курс, когда некоторые учащиеся решают покинуть класс. Этот сценарий ясно показывает структуру Queue. Очередь — это структура данных linear & dynamic с логикой FIFO (первым пришел — первым обслужен) или LILO (последний пришел — последним вышел). Очередь имеет различные приложения, такие как планирование задач ЦП, принтер или алгоритм BFS (поиск в ширину) и т. д.
Операции с очередью
enqueue()//push
— поместить в конец очередиdequeue()//pop
- вытолкнуть начало очередиcount()
- подсчитать количество элементовisEmpty()isFull()
Анализ временной сложности
Поскольку мы продолжаем поддерживать передние и задние указатели, все эти операции занимают O(1) время.
Передняя и задняя инициализируются как -1, что означает, что в очереди ничего нет. При первом добавлении установите для них обоих значение 0. После этого для операции постановки в очередь увеличьте значение на 1, если только очередь не заполнена. Здесь обратите внимание, что мы имеем дело с круговой очередью, поэтому, когда задняя часть достигает последней позиции массива, вам нужно rear = (rear+1)%size. Это относится и к операции удаления из очереди.
Для операции count() это может быть немного сложно. Посмотрите на изображение ниже. Когда спереди≤сзади, size = rear-front+1 и для спереди›сзади, size = rear+queue size-front+1.
