Python programs / Data structures / Queue

Python Program to Implement a Queue

Beginner Data structures Time O(1) Space O(n)

A first-in, first-out print queue built on collections.deque: jobs join at the back, leave from the front, and peek shows the next one.

A queue lets items out in the order they came in: first in, first out (FIFO), like people waiting at a till. A printer works this way. Send it report.pdf, then photo.png, then notes.txt, and it prints the report first. New items join at the back, and the next one out is always the one at the front.

Python's collections.deque (a double-ended queue, said "deck") adds and removes items at either end in the same short time, which makes it the usual way to build a queue. The queue module's Queue class is meant for passing work between threads. This file is called queue_deque.py because a file named queue.py would hide that module from any program run beside it.

Program

from collections import deque


class Queue:
    """A first-in, first-out queue."""

    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        """Add item at the back."""
        self.items.append(item)

    def dequeue(self):
        """Remove and return the item at the front."""
        return self.items.popleft()

    def peek(self):
        """The item at the front, without removing it."""
        return self.items[0]


printer = Queue()
for job in ["report.pdf", "photo.png", "notes.txt"]:
    printer.enqueue(job)
print("Printing:", printer.dequeue())
print("Next up:", printer.peek())
print("Waiting:", list(printer.items))

Open in the editor Download queue_deque.py

Output

Printing: report.pdf
Next up: photo.png
Waiting: ['photo.png', 'notes.txt']

How it works

  1. deque comes from the collections module in the standard library.
  2. Each new Queue (classes and objects) starts with an empty deque, self.items. Its left end is the front of the queue and its right end the back.
  3. enqueue() adds an item at the back with append().
  4. dequeue() takes the item at the front off with popleft() and returns it.
  5. peek() returns the front item, items[0], but leaves it in the queue, so the program can see what comes next without taking it.
  6. The program makes a print queue and sends it three jobs, in order.
  7. It prints the first job sent, report.pdf, peeks at the next one and shows the two still waiting.
Call Returns Queue afterwards, front first
enqueue("report.pdf") report.pdf
enqueue("photo.png") report.pdf, photo.png
enqueue("notes.txt") report.pdf, photo.png, notes.txt
dequeue() report.pdf photo.png, notes.txt
peek() photo.png photo.png, notes.txt

Calling dequeue() or peek() on an empty queue raises an IndexError, as the deque has nothing to give.

Time and space complexity

TimeO(1)
Extra spaceO(n)
Operation Time
enqueue() O(1)
dequeue() O(1)
peek() O(1)

Each operation touches one end of the deque only, so it takes the same time whether the queue holds 3 jobs or 3 million: O(1). The queue keeps one entry per item, so n items take O(n) space.

A plain list works too, with pop(0) to take the front item, but that's O(n): a list keeps its items side by side in memory, so when the first one leaves, every other item moves one place along. A deque keeps its items in linked blocks and never has to move them.

Other ways to write it

With a deque and no class

In a short program the deque on its own is the queue: append() to enqueue, popleft() to dequeue and [0] to peek. The class only gives those operations their queue names.

from collections import deque

printer = deque(["report.pdf", "photo.png"])
printer.append("notes.txt")
print(printer.popleft(), printer[0], len(printer))

With a list

This reads the same, but pop(0) moves every item that's left, so it slows down as the queue grows. It's fine for a handful of items.

printer = ["report.pdf", "photo.png"]
printer.append("notes.txt")
print(printer.pop(0), printer)

Try it yourself

  • Call printer.dequeue() three more times. The last call raises IndexError, because the queue is empty.
  • Add an is_empty() method, and use it in a while loop that prints every job until none are left.
  • Add a __len__ method, so that len(printer) says how many jobs are waiting (special methods).
  • Add an urgent(item) method that puts a job at the front of the queue with appendleft().

More data structures programs

Share this program