## DSA Tutorial

DSA HOME DSA Intro DSA Simple Algorithm

## Arrays

DSA Arrays DSA Bubble Sort DSA Selection Sort DSA Insertion Sort DSA Quick Sort DSA Counting Sort DSA Radix Sort DSA Merge Sort DSA Linear Search DSA Binary Search

## Stacks & Queues

DSA Stacks DSA Queues

## Hash Tables

DSA Hash Tables DSA Hash Sets DSA Hash Maps

## Trees

DSA Trees DSA Binary Trees DSA Pre-order Traversal DSA In-order Traversal DSA Post-order Traversal DSA Array Implementation DSA Binary Search Trees DSA AVL Trees

## Graphs

DSA Graphs Graphs Implementation DSA Graphs Traversal DSA Cycle Detection

## Shortest Path

DSA Shortest Path DSA Dijkstra's DSA Bellman-Ford

## Minimum Spanning Tree

Minimum Spanning Tree DSA Prim's DSA Kruskal's

## Maximum Flow

DSA Maximum Flow DSA Ford-Fulkerson DSA Edmonds-Karp

## Time Complexity

Introduction Bubble Sort Selection Sort Insertion Sort Quick Sort Counting Sort Radix Sort Merge Sort Linear Search Binary Search

## DSA Reference

DSA Euclidean Algorithm DSA Huffman Coding DSA The Traveling Salesman DSA 0/1 Knapsack DSA Memoization DSA Tabulation DSA Dynamic Programming DSA Greedy Algorithms

## DSA Examples

DSA Examples DSA Exercises DSA Quiz DSA Certificate

# DSA Queues

## Queues

A queue is a data structure that can hold many elements.

{{ x.dieNmbr }}

{{ resultText }}: {{ currVal }}

Think of a queue as people standing in line in a supermarket.

The first person to stand in line is also the first who can pay and leave the supermarket. This way of organizing elements is called FIFO: First In First Out.

Basic operations we can do on a queue are:

• Enqueue: Adds a new element to the queue.
• Dequeue: Removes and returns the first (front) element from the queue.
• Peek: Returns the first element in the queue.
• isEmpty: Checks if the queue is empty.
• Size: Finds the number of elements in the queue.

Experiment with these basic operations in the queue animation above.

Queues can be implemented by using arrays or linked lists.

Queues can be used to implement job scheduling for an office printer, order processing for e-tickets, or to create algorithms for breadth-first search in graphs.

Queues are often mentioned together with Stacks, which is a similar data structure described on the previous page.

## Queue Implementation using Arrays

To better understand the benefits with using arrays or linked lists to implement queues, you should check out this page that explains how arrays and linked lists are stored in memory.

This is how it looks like when we use an array as a queue:

[
{{ x.dieNmbr }}
,
]

{{ resultText }}: {{ currVal }}

Reasons to implement queues using arrays:

• Memory Efficient: Array elements do not hold the next elements address like linked list nodes do.
• Easier to implement and understand: Using arrays to implement queues require less code than using linked lists, and for this reason it is typically easier to understand as well.

Reasons for not using arrays to implement queues:

• Fixed size: An array occupies a fixed part of the memory. This means that it could take up more memory than needed, or if the array fills up, it cannot hold more elements. And resizing an array can be costly.
• Shifting cost: Dequeue causes the first element in a queue to be removed, and the other elements must be shifted to take the removed elements' place. This is inefficient and can cause problems, especially if the queue is long.
• Alternatives: Some programming languages have built-in data structures optimized for queue operations that are better than using arrays.

Note: When using arrays in Python for this tutorial, we are really using the Python 'list' data type, but for the scope of this tutorial the 'list' data type can be used in the same way as an array. Learn more about Python lists here.

Since Python lists has good support for functionality needed to implement queues, we start with creating a queue and do queue operations with just a few lines:

### Example

Python:

``````queue = []

# Enqueue
queue.append('A')
queue.append('B')
queue.append('C')
print("Queue: ", queue)

# Dequeue
element = queue.pop(0)
print("Dequeue: ", element)

# Peek
frontElement = queue[0]
print("Peek: ", frontElement)

# isEmpty
isEmpty = not bool(queue)
print("isEmpty: ", isEmpty)

# Size
print("Size: ", len(queue))``````
Run Example »

But to explicitly create a data structure for queues, with basic operations, we should create a queue class instead. This way of creating queues in Python is also more similar to how queues can be created in other programming languages like C and Java.

### Example

Python:

``````class Queue:
def __init__(self):
self.queue = []

def enqueue(self, element):
self.queue.append(element)

def dequeue(self):
if self.isEmpty():
return "Queue is empty"
return self.queue.pop(0)

def peek(self):
if self.isEmpty():
return "Queue is empty"
return self.queue[0]

def isEmpty(self):
return len(self.queue) == 0

def size(self):
return len(self.queue)

# Create a queue
myQueue = Queue()

myQueue.enqueue('A')
myQueue.enqueue('B')
myQueue.enqueue('C')
print("Queue: ", myQueue.queue)

print("Dequeue: ", myQueue.dequeue())

print("Peek: ", myQueue.peek())

print("isEmpty: ", myQueue.isEmpty())

print("Size: ", myQueue.size())``````
Run Example »

## Queue Implementation using Linked Lists

Reasons for using linked lists to implement queues:

• Dynamic size: The queue can grow and shrink dynamically, unlike with arrays.
• No shifting: The front element of the queue can be removed (enqueue) without having to shift other elements in the memory.

Reasons for not using linked lists to implement queues:

• Extra memory: Each queue element must contain the address to the next element (the next linked list node).
• Readability: The code might be harder to read and write for some because it is longer and more complex.

This is how a queue can be implemented using a linked list.

### Example

Python:

``````class Node:
def __init__(self, data):
self.data = data
self.next = None

class Queue:
def __init__(self):
self.front = None
self.rear = None
self.length = 0

def enqueue(self, element):
new_node = Node(element)
if self.rear is None:
self.front = self.rear = new_node
self.length += 1
return
self.rear.next = new_node
self.rear = new_node
self.length += 1

def dequeue(self):
if self.isEmpty():
return "Queue is empty"
temp = self.front
self.front = temp.next
self.length -= 1
if self.front is None:
self.rear = None
return temp.data

def peek(self):
if self.isEmpty():
return "Queue is empty"
return self.front.data

def isEmpty(self):
return self.length == 0

def size(self):
return self.length

def printQueue(self):
temp = self.front
while temp:
print(temp.data, end=" ")
temp = temp.next
print()

# Create a queue
myQueue = Queue()

myQueue.enqueue('A')
myQueue.enqueue('B')
myQueue.enqueue('C')
print("Queue: ", end="")
myQueue.printQueue()

print("Dequeue: ", myQueue.dequeue())

print("Peek: ", myQueue.peek())

print("isEmpty: ", myQueue.isEmpty())

print("Size: ", myQueue.size())``````
Run Example »

## Exercise:

The Array below is used as a Queue data structure:

`[5,11,8,3]`

Which indexes and values are affected by the endueue and dedueue operations?

```enqueue(7):
value 7 is placed on
index  in the array.

dequeue():
value  is taken
out of the queue.
```

Start the Exercise

×

## Contact Sales

If you want to use W3Schools services as an educational institution, team or enterprise, send us an e-mail:
sales@w3schools.com