Queue Data Structure

A queue is a data structure that stores items in a first in first out (FIFO) order.

An example of a queue is a line at a store register.

Let's say 3 people are waiting in line. The first person that entered the line is Bob. Then two others entered the line.

The next person up to pay at the register is Bob since he has been in the line the longest.

Queue main operations

A queue has 2 main functions:

Enqueue - Add an item to the queue
Dequeue - Remove the next item from the queue - the first item, or the one that has been in the queue the longest.

Queue Big O Overview

Operation	Time
Enqueue	O(1)
Dequeue	O(1)

Queue Implementation in Python

Under the hood, a queue is represented by a linked list.

The queue's enqueue operation simply adds a node to the end of the linked list.

The queue's dequeue operation retrieves and removes the head of the linked list, or the first item in the list, which has been in the queue the longest.

Since items can be added and removed from the queue in constant time, Python's dynamic array is a great way to represent a queue.

queue = []

queue.append('yellow')
queue.append('red')
queue.append('rose')
queue.append('green')

print('next item in the queue: ', queue[0])

print('queue in its first in first out order: ')

while queue:
    print('item: ', queue.pop(0))

1queue = []
2
3queue.append('yellow')
4queue.append('red')
5queue.append('rose')
6queue.append('green')
7
8print('next item in the queue: ', queue[0])
9
10print('queue in its first in first out order: ')
11
12while queue:
13    print('item: ', queue.pop(0))
14

A deque, or a double-ended queue, is a data structure that supports insertion and removal from both sides of the queue in constant O(1) time.

In Python, we can also use the collections.deque() library to model a queue, which gives us those constant time operations.

import collections

queue = collections.deque()

queue.append('ethereum')
queue.append('bitcoin')
queue.append('solana')
queue.append('dogecoin')

print('next item in the queue: ', queue[0])

print('queue in its first in first out order: ')

while queue:
    print('item: ', queue.popleft())

1import collections
2
3queue = collections.deque()
4
5queue.append('ethereum')
6queue.append('bitcoin')
7queue.append('solana')
8queue.append('dogecoin')
9
10print('next item in the queue: ', queue[0])
11
12print('queue in its first in first out order: ')
13
14while queue:
15    print('item: ', queue.popleft())
16

Queue Pros

Enqueue, or adding items to the queue, takes constant time.
Similarly, dequeue, or removing the next item from the queue, takes constant time.
Good for use cases such as tracking tasks to do in priority order, such as a todo list, or a background job.

Queue Cons

The main con with queue is that it's not useful for iterating through items, as linked lists aren't cache friendly, which means nodes won't necessarily be placed next to eachother in memory.

It's better to just use a regular array, or dynamic array, if your data structure will primarily be accessed iteratively.

5 Essential Stacks & Queues Coding Interview Problems

Master Stacks & Queues by trying the coding challenges below.

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.