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
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.
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.
- 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.
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.