🎓 A1Learner
🔍

DSA Queues

A queue is a line of values that leave in the order they arrived. The first value added is the first value removed.

Joining and leaving a line

Enqueue adds a value at the back. Dequeue removes the value at the front.

from collections import deque

line = deque(["Ana", "Bo"])
line.append("Cy")
print(line.popleft())
print(list(line))

The hidden cost of list.pop(0)

The pop removes one value and moves the rest. The code counts the moving values before the pop.

values = [10, 20, 30, 40]
shifts = len(values) - 1
front = values.pop(0)
print("removed:", front)
print("values shifted:", shifts)
print(values)

Peeking at the front

Peeking reads the front value. The line keeps all its values.

from collections import deque

line = deque(["Ana", "Bo", "Cy"])
print(line[0])
print(list(line))

Example

from collections import deque


class ListQueue:
    def __init__(self):
        self.items = []
        self.shifts = 0

    def enqueue(self, value):
        self.items.append(value)

    def dequeue(self):
        self.shifts += len(self.items) - 1
        return self.items.pop(0)


class DequeQueue:
    def __init__(self):
        self.items = deque()
        self.shifts = 0

    def enqueue(self, value):
        self.items.append(value)

    def dequeue(self):
        return self.items.popleft()


def run_workload(queue):
    served = []
    for value in [1, 2, 3, 4, 5, 6]:
        queue.enqueue(value)
    for _ in range(3):
        served.append(queue.dequeue())
    queue.enqueue(7)
    queue.enqueue(8)
    while len(queue.items) > 0:
        served.append(queue.dequeue())
    return served


list_queue = ListQueue()
deque_queue = DequeQueue()
print("list queue served:", run_workload(list_queue))
print("list queue shifts:", list_queue.shifts)
print("deque queue served:", run_workload(deque_queue))
print("deque queue shifts:", deque_queue.shifts)

Key points

  • Queue: a line of values that leave in the order they arrived
  • Enqueue: adding a value at the back of the queue
  • Dequeue: removing the value at the front of the queue
  • Use collections.deque for a queue that serves from the front often
  • list.pop(0) moves every remaining value one place toward the front

In this example, both queues take the same workload. Six values join, three leave, two more join, and the rest leave. The list queue counts len(items) - 1 shifts before each pop(0). Those counts add to 22 shifts. The deque queue serves the same values in the same order. Its popleft shifts nothing, so its count stays at zero.

Note

A list is built for work at its end, while a deque is built for work at its front

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A help desk serves tickets in arrival order, and thousands of tickets leave from the front each day. Which tool fits the front removals best?