Worksheets › Class 12 › Queue › Cheat sheet
Class 12 Queue: cheat sheet
CBSE Computer Science. A queue is FIFO: enqueue at the rear and dequeue from the front of a Python list; a deque works at both ends. Underflow, and choosing a stack, queue or deque.
Key ideas
- FIFO, first in first out: items join at the rear and leave from the front, in the order they joined.
- With a list, enqueue is append(x) and dequeue is pop(0); dequeuing an empty queue is underflow.
- The front item is q[0] and the rear item q[-1]; len(q) gives the size.
- A deque (double-ended queue) allows adding and removing at both ends: insert(0, x) and pop(0) at the front, append(x) and pop() at the rear.
- Used only with append() and pop(), a deque behaves as a stack; with append() and pop(0), as a queue.
- A word is a palindrome if the letters popped from the two ends of a deque match every time.
Remember
| Enqueue and dequeue | q = [] q.append(5) q.append(8) print(q.pop(0)) # 5 print(q) # [8] |
| Reaching the front | the k-th item enqueued is at the front after k − 1 dequeues |
| Deque ends | front: insert(0, x) and pop(0); rear: append(x) and pop() |
| Which structure | ticket line, print jobs, CPU tasks: queue; undo, back button, brackets: stack; both ends: deque |
Watch out
- Using pop() to dequeue: it takes the rear item, as a stack does.
- Thinking insert(0, x) adds at the rear: it adds at the front.
- Forgetting the underflow check when the queue is empty.
Worked example
What does this print? d = [47, 46] d.insert(0, 95) d.insert(0, 91) d.insert(0, 99) d.pop() d.append(87) print(d)
Working: append() adds at the rear, insert(0, x) at the front; pop() removes from the rear, pop(0) from the front
Answer: [99, 91, 95, 47, 87]
Practise Queue
Revise with this page, then practise: every Queue sheet in the app is new, with an answer key and working.
Coming soon for Android and iPhone.