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
- 队列(queue)是先进先出(FIFO,First In, First Out)。
- 你最先放进去的元素,会最先离开。
- 想象排队的人:站在最前面的人最先被服务。
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.
队首与判空
- 查看队首而不移除它:
queue[0]。 - 当
len(queue) == 0时,队列是空的。 - 出队之前要先检查它不是空的。
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)必须把其余每个元素都向前移动一位。- 对很大的队列来说这很慢,会用掉更多时间。
- 真实系统改用带 front 和 rear 指针的环形缓冲区(circular buffer)。
In Cambridge pseudocode
- The exam builds a queue from an array with a
frontand arearpointer.
用剑桥伪代码表示
- 考试用一个数组加上
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.
常见错误
- 队列是先进先出:从后面加入,从前面离开。
- 出队之前先检查它不是空的。
Now you try
- Use a list as your queue (
appendto enqueue,pop(0)to dequeue). - Press Check answer to test your code.
现在轮到你
- 把列表当作你的队列(用
append入队,用pop(0)出队)。 - 按检查答案来测试你的代码。
A queue is 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"].) · 从一个空队列开始。依次入队 "a"、"b"、"c"。然后出队一次,把移除的值存进 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].) · 把 1、2、3 入队,然后全部出队到 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),把队首元素出队:从列表中移除它并返回它。调用者的列表会因此变短。
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. · 点击“运行”查看此处输出。