Queues · Очереди
A queue is FIFO
- A queue is First In, First Out (FIFO).
- The first item you add is the first one to leave.
- Think of a line of people: the person at the front is served first.
Очередь работает по принципу FIFO
- Очередь работает по принципу First In, First Out (FIFO — первый вошел, первый вышел).
- Первый добавленный элемент является первым уходящим.
- Представьте очередь людей: человек в начале обслуживается первым.
enqueue and dequeue with a list
- We can build a queue from a Python list.
- enqueue =
queue.append(x)— add to the back. - dequeue =
queue.pop(0)— remove and return the front.
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 and empty
- Look at the front without removing it:
queue[0]. - A queue is empty when
len(queue) == 0. - Check it is not empty before you dequeue.
front и empty
- Посмотреть на начало без удаления:
queue[0]. - Очередь считается пустой, когда
len(queue) == 0. - Проверяйте, что она не пуста, перед тем как выполнять dequeue.
queue = [10, 20, 30]
print(queue[0]) # the front
print(len(queue) == 0) # is it empty?
A note on speed
pop(0)has to shift every other item forward by one place.- For a big queue that is slow, so it uses more time.
- Real systems use a circular buffer with front and rear pointers instead.
Примечание о скорости
pop(0)должен сдвинуть каждый другой элемент вперед на одно место.- Для большой очереди это медленно, поэтому требуется больше времени.
- Реальные системы используют циклический буфер с указателями начала и конца.
In Cambridge pseudocode
- The exam builds a queue from an array with a
frontand arearpointer.
В псевдокоде 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
Common mistakes
- A queue is first-in, first-out: join the back, leave from the front.
- Check it is not empty before you dequeue.
Распространенные ошибки
- Очередь работает по принципу first-in, first-out: присоединяйтесь к концу, уходите с начала.
- Проверяйте, что она не пуста, перед тем как выполнять dequeue.
Now you try
- Use a list as your queue (
appendto enqueue,pop(0)to dequeue). - Press Check answer to test your code.
Теперь попробуйте сами
- Используйте список в качестве очереди (
appendдля enqueue,pop(0)для dequeue). - Нажмите Check answer (Проверить ответ), чтобы протестировать свой код.
A queue is FIFO · Очередь работает по принципу FIFO
A queue adds at the back and removes at the front — first in, first out. · Очередь добавляет элементы сзади и удаляет спереди — первый вошёл, первый вышел.
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"].) · Начните с пустой очереди. Добавьте (enqueue) элементы "a", затем "b", затем "c". Затем выполните одну операцию удаления (dequeue), сохранив удалённое значение в переменную first. (Значение first должно быть равно ⟨"a"⟩, а очередь должна содержать ⟨["b", "c"]⟩.)
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Enqueue 1, 2, 3 onto a queue, then dequeue them all into result. Unlike a stack, a queue keeps the same order. (result should be [1, 2, 3].) · Добавьте (enqueue) элементы 1, 2, 3 в очередь, затем извлеките (dequeue) их все в список result. В отличие от стека, очередь сохраняет тот же самый порядок. (Результат в result должен быть равен ⟨[1, 2, 3]⟩.)
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Write serve(queue) that dequeues the front item: remove it from the list and return it. The caller's list should get shorter. · Напишите функцию serve(queue), которая удаляет (dequeue) передний элемент: убирает его из списка и возвращает. Список вызывающей части должен стать короче.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Write front(queue) that returns the front item without removing it, so the queue is unchanged. If the queue is empty, return None. · Напишите функцию front(queue), которая возвращает передний элемент без его удаления, чтобы очередь осталась неизменной. Если очередь пуста, верните значение None.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.