Queue and Deque

At a ticket window the person who arrived first is served first, and newcomers join at the back. A queue is the data structure built on that rule, and it is the natural model wherever requests must be handled in the order they arrive — print jobs waiting for a printer, requests reaching a web server, calls waiting at a help desk. This chapter defines the queue and its operations, implements it with a Python list, and then introduces the deque, a queue that allows additions and removals at both ends and can therefore behave as a stack or as a queue. Questions here are mostly traces: follow the front and the rear through each operation.

What a Queue Is: First In, First Out

A queue is an ordered linear list in which elements are added at one end, the REAR (also called the tail), and removed from the other end, the FRONT (also called the head). The element that has waited longest is always removed first, so a queue follows the FIFO principle — First In, First Out. Adding an element at the rear is ENQUEUE; removing the element at the front is DEQUEUE. Dequeuing from an empty queue is underflow; enqueuing into a queue that has a fixed capacity and is full is overflow.

Stack and queue side by side
FeatureStackQueue
PrincipleLIFOFIFO
Ends usedone end (TOP) for both operationsREAR to add, FRONT to remove
Add / removePUSH / POPENQUEUE / DEQUEUE
Everyday modelpile of platesline at a ticket window
  • In daily life: a waiting list for train tickets, vehicles at a toll plaza, customers waiting at a call centre.
  • In computing: print jobs sent to one shared printer, requests arriving at a web server, and an operating system scheduling the jobs waiting for the processor.

A Queue in Python

With a Python list, the book keeps the front at index 0 and the rear at the end. Enqueue is myQueue.append(element); dequeue is myQueue.pop(0), which removes and returns the first element; peek returns myQueue[0] without removing it; isEmpty tests len(myQueue) == 0 and size returns len(myQueue). As with a stack, dequeue and peek must check isEmpty first.

A short trace — this prints [20, 30, 15], because the element dequeued from the front is 10 and 10 + 5 joins at the rear:
q = []
q.append(10)
q.append(20)
q.append(30)
x = q.pop(0)
q.append(x + 5)
print(q)

⚠️ pop() is a stack, pop(0) is a queue
On the same list, pop() removes the last element (LIFO) and pop(0) removes the first (FIFO). Code-output questions hinge on which one is written, so read the brackets before tracing.

The Deque: a Double-Ended Queue

A deque (pronounced "deck", short for double-ended queue) is an ordered linear list in which elements can be added and removed at both ends. It therefore generalises both earlier structures: used with insertion and deletion at the same end it behaves as a stack, and with insertion at one end and deletion at the other it behaves as a queue. Its operations are insertFront, insertRear, deletionFront and deletionRear, with getFront and getRear to read either end. With a Python list: insertFront is insert(0, x), insertRear is append(x), deletionFront is pop(0) and deletionRear is pop().

Tracing a deque — after these lines the list is ['D', 'A', 'C']:
d = []
d.append("A")
d.insert(0, "B")
d.append("C")
d.pop(0)
d.insert(0, "D")
Step by step: [A] → [B, A] → [B, A, C] → [A, C] (B removed from the front) → [D, A, C].

Checking a palindrome with a deque. Insert every character of the word at the rear. Then, while more than one character remains, remove one from the front and one from the rear and compare them; any mismatch means the word is not a palindrome. "madam" and "level" pass; "lever" fails at the first comparison, l against r. Other uses the book names include letting a person who briefly left a queue rejoin at its front, and keeping a limited browsing history or undo list, where the oldest entry is dropped from one end as new ones arrive at the other.

Key takeaways

  • A queue adds at the REAR and removes from the FRONT, so it is FIFO; the operations are ENQUEUE and DEQUEUE.
  • Dequeuing an empty queue is underflow; enqueuing a full fixed-size queue is overflow.
  • With a Python list, enqueue is append(x), dequeue is pop(0), and the front is myQueue[0].
  • Queues model print jobs, web-server requests and job scheduling — anything served in order of arrival.
  • A deque allows insertion and deletion at both ends: same end gives a stack, opposite ends a queue.
  • A palindrome is checked by filling a deque and comparing characters removed from the front and the rear.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

  1. What is the output of the following code?
    q = []
    q.append(10)
    q.append(20)
    q.append(30)
    x = q.pop(0)
    q.append(x + 5)
    print(q)

    1. [10, 20, 35]
    2. [20, 30, 15]
    3. [15, 20, 30]
    4. [20, 30, 35]
    Show answer

    Answer: B — `[20, 30, 15]`

    pop(0) removes the element at the front, 10, so the list becomes [20, 30]; 10 + 5 = 15 is then appended at the rear, giving [20, 30, 15]. [10, 20, 35] treats pop(0) as pop(), removing 30 from the rear as a stack would. [15, 20, 30] puts the new element at the front, and [20, 30, 35] adds 5 to the wrong element.

  2. Which statement correctly describes a queue?

    1. Elements are added and removed at the same end, called the top
    2. Elements may be added or removed at any position in the list
    3. Elements are always removed in increasing order of their values
    4. Elements are added at the rear and removed from the front
    Show answer

    Answer: D — Elements are added at the rear and removed from the front

    A queue uses two ends — new elements join at the rear and the oldest leaves from the front — which is what makes it first in, first out. Adding and removing at a single top describes a stack. Removal at any position would make it an ordinary list, and removal by value describes a priority ordering, not the arrival order a queue keeps.

  3. A list d is used as a deque. What does print(d) show after these statements?
    d = []
    d.append("A")
    d.insert(0, "B")
    d.append("C")
    d.pop(0)
    d.insert(0, "D")

    1. ['D', 'B', 'A']
    2. ['D', 'A', 'C']
    3. ['B', 'A', 'D']
    4. ['A', 'C', 'D']
    Show answer

    Answer: B — `['D', 'A', 'C']`

    Trace it: [A], then B inserted at the front gives [B, A], C appended gives [B, A, C], pop(0) removes B from the front leaving [A, C], and D inserted at the front gives [D, A, C]. The answer ending in B and A treats pop(0) as removing C from the rear. Putting D at the end confuses insert(0, x), which adds at the front, with append, which adds at the rear.

  4. Starting with an empty queue, 4, 7 and 2 are enqueued in that order; then one dequeue is done, 9 is enqueued, and another dequeue is done. Which element is now at the front?

    1. 7
    2. 9
    3. 2
    4. 4
    Show answer

    Answer: C — 2

    The queue is [4, 7, 2]; the first dequeue removes 4, giving [7, 2]; 9 joins at the rear, [7, 2, 9]; the second dequeue removes 7, leaving [2, 9], so 2 is at the front. 9 is the rear, the answer if the queue is mistaken for a stack. 7 is the front before the second dequeue, and 4 left the queue first of all.

  5. Several users send documents to one shared printer, and the documents must be printed in the order they were sent. Which data structure fits this best?

    1. Queue
    2. Stack
    3. Dictionary keyed on document size
    4. A list sorted alphabetically by document name
    Show answer

    Answer: A — Queue

    Printing in the order of arrival is first in, first out, which is exactly a queue: each new job joins at the rear and the printer takes the job at the front. A stack would print the most recently sent document first, so whoever sent first would wait longest. Ordering by size or by name ignores the arrival order the question demands.

  6. A deque is used so that every insertion and every deletion happens at the front end only. How does it then behave?

    1. As a queue, because the front is where a queue removes elements
    2. As a sorted list, because the front always holds the smallest element
    3. As a stack, because the last element inserted is the first removed
    4. It cannot work, because a deque must use both of its ends
    Show answer

    Answer: C — As a stack, because the last element inserted is the first removed

    When additions and removals share one end, the element added last is always the one removed next — LIFO, a stack, whichever end is chosen. The queue option fixes on the word "front", but a queue needs insertion at the opposite end. A deque permits both ends without requiring both, and nothing in it keeps elements sorted.

  7. Assertion (A): When a Python list implements a queue as in the textbook, dequeue is written as myQueue.pop(0). Reason (R): The front of the queue is kept at index 0 of the list.

    1. Both A and R are true, and R is the correct explanation of A
    2. Both A and R are true, but R is not the correct explanation of A
    3. A is true, but R is false
    4. A is false, but R is true
    Show answer

    Answer: A — Both A and R are true, and R is the correct explanation of A

    Enqueue appends at the end of the list, so the rear is the end and the front — the oldest element — sits at index 0; dequeue must remove from there, which pop(0) does. R is therefore the very reason A is written that way. Calling R "not the explanation" misses that the choice of index 0 for the front is what decides which pop is used.

  8. What does the following code print?
    def is_pal(word):
    dq = []
    for ch in word:
    dq.append(ch)
    while len(dq) > 1:
    if dq.pop(0) != dq.pop():
    return False
    return True
    print(is_pal("level"), is_pal("lever"))

    1. True True
    2. False False
    3. False True
    4. True False
    Show answer

    Answer: D — True False

    For "level", the front and rear pairs are l–l and then e–e, and the single middle v ends the loop, so True. For "lever", the first pair removed is l from the front and r from the rear; they differ and the function returns False at once. True True would follow only if the comparison ignored the last letter, and the reversed pair confuses which word reads the same both ways.