队列是 FIFO
- 队列(queue)是先进先出(FIFO,First In, First Out)。
- 你最先放进去的元素,会最先离开。
- 想象排队的人:站在最前面的人最先被服务。
用列表实现 enqueue 和 dequeue
- 我们可以用一个 Python 列表来构建队列。
- enqueue(入队)=
queue.append(x)—— 加到队尾。 - dequeue(出队)=
queue.pop(0)—— 移除并返回队首。
queue = []
queue.append("first")
queue.append("second")
print(queue.pop(0))
print(queue)
队首与判空
- 查看队首而不移除它:
queue[0]。 - 当
len(queue) == 0时,队列是空的。 - 出队之前要先检查它不是空的。
queue = [10, 20, 30]
print(queue[0]) # the front
print(len(queue) == 0) # is it empty?
关于速度的说明
pop(0)必须把其余每个元素都向前移动一位。- 对很大的队列来说这很慢,会用掉更多时间。
- 真实系统改用带 front 和 rear 指针的环形缓冲区(circular buffer)。
用剑桥伪代码表示
- 考试用一个数组加上
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
常见错误
- 队列是先进先出:从后面加入,从前面离开。
- 出队之前要先检查它不是空的。
现在轮到你
- 把列表当作你的队列(用
append入队,用pop(0)出队)。 - 按检查答案来测试你的代码。
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 出队 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 回报 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.
点击“运行”查看此处输出。