Очереди
Очередь работает по принципу FIFO
- Очередь работает по принципу First In, First Out (FIFO — первый вошел, первый вышел).
- Первый добавленный элемент является первым уходящим.
- Представьте очередь людей: человек в начале обслуживается первым.
enqueue и dequeue со списком
- Мы можем создать очередь на основе списка Python.
- enqueue =
queue.append(x)— добавить в конец очереди. - dequeue =
queue.pop(0)— удалить и вернуть начало очереди.
queue = []
queue.append("first")
queue.append("second")
print(queue.pop(0))
print(queue)
front и empty
- Посмотреть на начало без удаления:
queue[0]. - Очередь считается пустой, когда
len(queue) == 0. - Проверяйте, что она не пуста, перед тем как выполнять dequeue.
queue = [10, 20, 30]
print(queue[0]) # the front
print(len(queue) == 0) # is it empty?
Примечание о скорости
pop(0)должен сдвинуть каждый другой элемент вперед на одно место.- Для большой очереди это медленно, поэтому требуется больше времени.
- Реальные системы используют циклический буфер с указателями начала и конца.
В псевдокоде Cambridge
- На экзаменте очередь строится на массиве с указателем
frontи указателемrear.
DECLARE queue : ARRAY[1:10] OF INTEGER
DECLARE front, rear : INTEGER
front ← 1
rear ← 0 // empty
// enqueue value
rear ← rear + 1
queue[rear] ← value
// dequeue into value
value ← queue[front]
front ← front + 1
Распространенные ошибки
- Очередь работает по принципу first-in, first-out: присоединяйтесь к концу, уходите с начала.
- Проверяйте, что она не пуста, перед тем как выполнять dequeue.
Теперь попробуйте сами
- Используйте список в качестве очереди (
appendдля enqueue,pop(0)для dequeue). - Нажмите Check answer (Проверить ответ), чтобы протестировать свой код.
A queue is FIFO
A queue adds at the back and removes at the front — first in, first out.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Start with an empty queue. Enqueue "a", then "b", then "c". Then dequeue once, storing the removed value in first. (first should be "a" and the queue should be ["b", "c"].)
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Enqueue 1, 2, 3 onto a queue, then dequeue them all into result. Unlike a stack, a queue keeps the тем же самым order. (result should be [1, 2, 3].)
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Write serve(queue) that dequeues the front item: remove it from the list and возврат (return) it. The caller's list should get shorter.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Write front(queue) that отдачи the front item without removing it, so the queue is unchanged. If the queue is empty, return None.
Нажмите Запустить, чтобы увидеть результат здесь.