Queues
The queue and its first in, first out discipline: enqueue, dequeue, head, the circular array implementation, the double-ended queue, and telling when a situation calls for a queue rather than a stack.
- 28 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- Scenarios
- Understand
A few cards from the deck
Queue: what is it?
Show the answer
An ordered collection where items are added at one end and removed at the other: the oldest item present comes out first.
It is the line at a counter: you join behind the last arrival and are served once everyone ahead has left.
What does this program print?
```python
from collections import deque
q = deque()
q.append(3)
q.append(7)
a = q.popleft()
q.append(1)
b = q.popleft()
q.append(4)
print(a, b, q[0])`3 7 13 7 47 3 13 1 4
Show the answer
3 7 1The queue first holds 3, 7; the first
poplefttakes out 3. After 1 is added, the second takes out 7. What is left is 1, 4: the headq[0]is 1, the oldest item present.In a queue, you … at the rear and you … at the front.
Show the answer
In a queue, you enqueue at the rear and you dequeue at the front.
Enqueue adds an item behind all the others; dequeue removes and returns the head item. They never act on the same end.
FIFO (first in, first out): what is it?
Show the answer
A discipline where items leave in exactly the order they arrived.
It is the opposite of the stack (LIFO, last in first out): you leave from the side opposite the one where you enter.
A server receives requests faster than it can process them. It must hold them and serve them in the order they arrived. Which structure should it use?
- A stack, because the last request to arrive is also the most urgent to process
- An array sorted by processing time, the shortest served first
- A queue, which serves the oldest request first
- A set, which keeps each request once with no particular order
Show the answer
A queue, which serves the oldest request first
A queue acts as a buffer between a fast producer and a slow consumer, and keeps things fair: first come, first served. A stack would make the oldest requests wait forever.