Queue in Python

Queue is a linear data structure that stores items in a First In First Out (FIFO) manner. The
item that is added first will be removed first. Queues are widely used in real-life scenarios,
like ticket booking, or CPU task scheduling, where first-come, first-served rule is followed.

Operations associated with queue are:

 Enqueue: Adds an item to the queue. If queue is full, it is said to be an Overflow

 Dequeue: Removes an item from the queue. If the queue is empty, it is said to be an
Underflow condition – Time Complexity : O(1)

 Front: Get front item from queue – Time Complexity : O(1)

 Rear: Get last item from queue – Time Complexity : O(1)

Implement a Queue

There are various ways to implement a queue in Python by following ways:

1. Implementation using list

Lists can be used as queues, but removing elements from front requires shifting all other
elements, making it O(n).

Example: Simulate a queue with a Python list.

queue = []

[Link]('a')

[Link]('b')
[Link]('c')

print("Initial queue:", queue)

print("Elements dequeued from queue:")

print([Link](0))

print([Link](0))

print([Link](0))

print("Queue after removing elements:", queue)

Output

Initial queue: ['a', 'b', 'c']

Elements dequeued from queue:

Queue after removing elements: []

Explanation: We added elements using append() and removed from the front using pop(0).
After removing all elements, queue is empty.

2. Implementation using [Link]

deque (double-ended queue) is preferred over a list for queues because both append() and
popleft() run in O(1) time.

Example: Queue using deque.

from collections import deque

q = deque()

[Link]('a')

[Link]('b')

[Link]('c')
print("Initial queue:", q)

print("Elements dequeued from the queue:")

print([Link]())

print([Link]())

print([Link]())

print("Queue after removing elements:", q)

Output

Initial queue: deque(['a', 'b', 'c'])

Elements dequeued from the queue:

Queue after removing elements: deque([])

Explanation: popleft() efficiently removes the first element without shifting, making deque
ideal for queues.

3. Implementation using [Link]

Python’s queue module provides a thread-safe FIFO queue. You can specify a maxsize. Key
Methods are:

 put(item) / put_nowait(item) – Add an element.

 get() / get_nowait() – Remove an element.

 empty() – Check if the queue is empty.

 full() – Check if the queue is full.

 qsize() – Get current size of the queue.

Example: Queue using [Link].

from queue import Queue

q = Queue(maxsize=3)
print("Initial size:", [Link]())

[Link]('a')

[Link]('b')

[Link]('c')

print("Is full:", [Link]())

print("Elements dequeued from the queue:")

print([Link]())

print([Link]())

print([Link]())

print("Is empty:", [Link]())

[Link](1)

print("Is empty:", [Link]())

print("Is full:", [Link]())

Output

Initial size: 0

Is full: True

Elements dequeued from the queue:

Is empty: True

Is empty: False

Is full: False
Queue Data Structure

Queue is a linear data structure that follows FIFO (First In First Out) Principle, so the first
element inserted is the first to be popped out.

FIFO Principle in Queue:

FIFO Principle states that the first element added to the Queue will be the first one to be
removed or processed. So, Queue is like a line of people waiting to purchase tickets, where
the first person in line is the first person served. (i.e. First Come First Serve).

Basic Terminologies of Queue

 Front: Position of the entry in a queue ready to be served, that is, the first entry that
will be removed from the queue, is called the front of the queue. It is also referred as
the head of the queue.

 Rear: Position of the last entry in the queue, that is, the one most recently added, is
called the rear of the queue. It is also referred as the tail of the queue.

 Size: Size refers to the current number of elements in the queue.

 Capacity: Capacity refers to the maximum number of elements the queue can hold.

Types of Queues

Queue data structure can be classified into 3 types:

1. Simple Queue

A simple queue follows the FIFO (First In, First Out) principle.

 Insertion is allowed only at the rear (back).

 Deletion is allowed only from the front.

 Can be implemented using a linked list or a circular array.

When an array is used, we often prefer a circular queue, which is mainly an efficient array
implementation of a simple queue. It efficiently utilizes memory by reusing the empty
spaces left after deletion, avoiding wastage that occurs in a normal linear array
implementation..

2. Double-Ended Queue (Deque)

In a deque, insertion and deletion can be performed from both ends.

A queue where each element is assigned a priority, and deletion always happens based on
priority (not just position).

Queue Operations

1. Enqueue: Adds an element to the end (rear) of the queue. If the queue is full, an
overflow error occurs.

2. Dequeue: Removes the element from the front of the queue. If the queue is empty,
an underflow error occurs.

3. Peek/Front: Returns the element at the front without removing it.

4. Size: Returns the number of elements in the queue.

5. isEmpty: Returns true if the queue is empty, otherwise false.

6. isFull: Returns true if the queue is full, otherwise false.

For detailed steps and more information on each operation, Read Basic Operations for
Queue in Data Structure.

Implementation of Queue

Queue can be implemented using following data structures:

 Simple Array implementation of Queue

 Efficient Array Implementation of Queue

 Implementation of Queue using Linked List

Queue using Array - Simple Implementation

A queue is a linear data structure that follows the FIFO (First In, First Out) principle. The first
element inserted is the first one to be removed.

Declaration of Queue Using Array:

A queue can be implemented using an array, and there are two main ways:

1. Infinite (or Dynamically Growable) Array Queue

2. Fixed-Size Array Queue

Infinite (or Dynamically Growable) Array Queue:

 Enqueue: Insert at the next available position at the end. No rear pointer is required.

 Dequeue: Remove the element at front and increment the front pointer.

The space before front is never reused, and unlike basic array implementations, we do not
shift elements after each dequeue. This ensures both enqueue and dequeue operations run
in O(1) time with a simple design.

Limitations:

 Wasted space: The elements before the front pointer are never reused, so memory
can be wasted if many elements are dequeued.

 Infinite array assumption: We assume the array is conceptually infinite. In practice,

Fixed-Size Array Queue

In this article, we will mainly discuss the queue implementation using a fixed-size array. In
such an array-based queue, we maintain:

 A fixed-size array arr[] to store the elements.

 A variable size to track the current number of elements in the queue.

 A variable capacity to represent the maximum number of elements the queue can
hold.

class myQueue:

def __init__(self, capacity):

# Maximum number of elements the queue can hold.

[Link] = capacity

# Array to store queue elements.

[Link] = [0] * capacity

# Current number of elements in the queue.

[Link] = 0
Operations on Queue

Enqueue (Insert):

 Add element at the end of the queue if space is available; otherwise, it results in an
Overflow condition.

 Time: O(1) , Space: O(1)

def enqueue(self, x):

if [Link] == [Link]:

print("Queue Overflow")

return

[Link][[Link]] = x

[Link] += 1

Dequeue:

 Remove element from the front of the queue; if the queue is empty, it results in an
Underflow condition.

 Time: O(n) (because of shifting) , Space : O(1)

def dequeue(self):

if [Link] == 0:

print("Queue Underflow")

return

for i in range(1, [Link]):

[Link][i-1] = [Link][i]

[Link] -= 1

getFront (Peek):

 Return first element if not empty, else -1.

 Time: O(1) , Space: O(1)

def getFront(self):

if [Link] == 0:
 print("Queue is empty")

return -1

return [Link][0]

getRear():

 Return last element if not empty, else -1.

 Time: O(1) , Space: O(1)

def getRear(self):

if [Link]():

print("Queue is empty!")

return -1

return [Link][[Link] - 1]

isEmpty():

 Checks whether the queue has any elements or not.

 Returns true if the queue is empty, otherwise false.

 Time: O(1) , Space: O(1)

def isEmpty(self):

return [Link] == 0

isFull():

 Checks whether the queue has reached its maximum capacity.

 Returns true if the queue is full, otherwise false.

 Time: O(1) , Space: O(1)

def isFull(self):

return [Link] == [Link]

Full Implementations of Queue using Array

class myQueue:

def __init__(self, capacity):

[Link] = capacity

# Array to store queue elements.

[Link] = [0] * capacity

# Current number of elements in the queue.

[Link] = 0

# Check if queue is empty

def isEmpty(self):

return [Link] == 0

# Check if queue is full

def isFull(self):

return [Link] == [Link]

# Enqueue

def enqueue(self, x):

if [Link]():

print("Queue is full!")

return

[Link][[Link]] = x

[Link] += 1

# Dequeue

def dequeue(self):

if [Link]():

print("Queue is empty!")

return
 for i in range(1, [Link]):

[Link][i - 1] = [Link][i]

[Link] -= 1

# Get front element

def getFront(self):

if [Link]():

print("Queue is empty!")

return -1

return [Link][0]

def getRear(self):

if [Link]():

print("Queue is empty!")

return -1

return [Link][[Link] - 1]

# Driver code

if __name__ == '__main__':

q = myQueue(3)

[Link](10)

[Link](20)

[Link](30)

print("Front:", [Link]())

[Link]()
 print("Front:", [Link]())

print("Rear:", [Link]())

[Link](40)

Output

Front: 10

Front: 20

Rear: 30

We can notice that the Dequeue operation is O(n) which is not acceptable. The enqueue and
dequeue both operations should have O(1) time complexity. That is why if we wish to
implement a queue using array (because of array advantages like cache friendliness and
random access), we do circular array implementation of queue.

Queue - Linked List Implementation

A Queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. The
element inserted first is the first one to be removed.

It can be implemented using a linked list, where each element of the queue is represented
as a node.

Declaration of Queue using Linked List

To implement a queue with a linked list, we maintain:

A Node structure/class that contains:

 data → to store the element.

 next → pointer/reference to the next node in the queue.

Two pointers/references:

 front → points to the first node (head of the queue).

 rear → points to the last node (tail of the queue).

class Node:
 def __init__(self, new_data):

[Link] = new_data

[Link] = None

class myQueue:

def __init__(self):

[Link] = None

[Link] = None

Operations on Queue using Linked List:

Enqueue Operation

The enqueue operation adds an element to the rear of the queue. Unlike array
implementation, there is no fixed capacity in linked list. Overflow occurs only when
memory is exhausted.

 A new node is created with the given value.

 If the queue is empty (front == null and rear == null), both front and rear are set to
this new node.

 Otherwise, the current rear’s next pointer is set to the new node.

 The rear pointer is updated to point to the new node.

def enqueue(self, new_data):

new_node = Node(new_data)

if [Link]():

[Link] = [Link] = new_node

else:

[Link] = new_node

[Link] = new_node

Time Complexity: O(1)

Dequeue Operation

The dequeue operation removes an element from the front of the queue.
  If the queue is empty (front == null), return underflow (queue is empty).

 Otherwise, store the current front node in a temporary pointer.

 Move the front pointer to the next node (front = [Link]).

 If the front becomes null, also set rear = null (queue becomes empty).

def dequeue(self):

if [Link]():

print("Queue Underflow")

return

temp = [Link]

[Link] = [Link]

if [Link] is None:

[Link] = None

Time Complexity: O(1)

isEmpty Operation

The isEmpty operation checks whether the queue has no elements.

 If the front pointer is NULL, it means the queue is empty → return true.

 Otherwise, the queue has elements → return false.

# Check if the queue is empty

def isEmpty(self):

return [Link] is None

Time Complexity: O(1)

Front Operation

The front() function returns the element at the front of the queue without removing it.

 If the queue is empty (front == NULL), print a message and return -1.
  Otherwise, return front->data (the value at the front).

# Return the front element

def getfront(self):

if [Link]():

print("Queue is empty")

return -1

return [Link]

Time Complexity: O(1)

Full Implementations of Queue Using Linked List

class Node:

def __init__(self, new_data):

[Link] = new_data

[Link] = None

class myQueue:

def __init__(self):

[Link] = None

[Link] = None

[Link] = 0

# Check if the queue is empty

def isEmpty(self):

return [Link] is None

# Add element to the queue

def enqueue(self, new_data):

new_node = Node(new_data)
 if [Link]():

[Link] = [Link] = new_node

else:

[Link] = new_node

[Link] = new_node

# increment size

[Link] += 1

# Remove element from the queue and return it

def dequeue(self):

if [Link]():

print("Queue Underflow")

return -1

removedData = [Link]

[Link] = [Link]

if [Link] is None:

[Link] = None

# decrement size

[Link] -= 1

return removedData

# Return the front element

def getfront(self):

if [Link]():

print("Queue is empty")

return -1
 return [Link]

# Return size in O(1)

def size(self):

return [Link]

if __name__ == "__main__":

q = myQueue()

[Link](10)

[Link](20)

print("Dequeue:", [Link]())

[Link](30)

print("Front:", [Link]())

print("Size:", [Link]())

Output

Dequeue: 10

Front: 20

Size: 2

Implementation of Circular Queue Using Array

A circular queue is a linear data structure that overcomes the limitations of a simple queue.
In a normal array implementation, dequeue() can be O(n) or we may waste space. Using a
circular array, both enqueue() both enqueue() and dequeue() can be done in O(1).

Declaration using Array:

 arr[] : array to store elements.

 capacity : maximum size of the queue.

 front : index of the front element.

 size : current number of elements in the queue.

class myQueue:

def __init__(self, cap):

# Maximum capacity of the queue

[Link] = cap

# Fixed-size list to store queue elements

[Link] = [0] * cap

# Index of the front element

[Link] = 0

# Current number of elements in the queue

[Link] = 0

Operations On Circular Queue:

enqueue(x) :

Purpose: Insert an element x at the rear of the circular queue.

 Check for full queue: If size == capacity, the queue is full print message or return.

 Compute rear index: rear = (front + size) % capacity ensures circular behavior.

 Insert element: arr[rear] = x.

 Update size: Increment size by 1.

 Time Complexity: O(1) Space Complexity: O(1) for the array

# Insert an element at the rear

if [Link] == [Link]:

print("Queue is full!")

return

rear = ([Link] + [Link]) % [Link]

[Link][rear] = x

[Link] += 1

dequeue() :

Purpose: Remove and return the front element from the circular queue.

 Check for empty queue: If size == 0, the queue is empty print message or return -1.

 Retrieve front element: res = arr[front].

 Move front forward: front = (front + 1) % capacity circular movement.

 Update size: Decrement size by 1.

 Return element: Return res.

 Time Complexity: O(1) Space Complexity: O(1)

# Remove an element from the front

def dequeue(self):

if [Link] == 0:

print("Queue is empty!")

return -1

res = [Link][[Link]]

[Link] = ([Link] + 1) % [Link]

[Link] -= 1

return res

getRear() :

Purpose: Return the element at the rear of the circular queue.

 Check for empty queue: If size == 0, the queue is empty → return -1.
  Compute rear index: rear = (front + size - 1) % capacity.

 Return element: Return arr[rear].

 Time Complexity: O(1) Space Complexity: O(1)

# Get the rear element

def getRear(self):

if [Link] == 0:

return -1

rear = ([Link] + [Link] - 1) % [Link]

return [Link][rear]

getFront() :

Purpose: Return the element at the front of the circular queue.

 Check for empty queue: If size == 0, the queue is empty → return -1.

 Return element: arr[front] is the front element.

 Time Complexity: O(1) Space Complexity: O(1)

# Get the front element

def getFront(self):

if [Link] == 0:

return -1

return [Link][[Link]]

Complete Implementation:

class myQueue:

def __init__(self, cap):

# fixed-size array

[Link] = [0]*cap

# index of front element

[Link] = 0

# current number of elements

[Link] = 0
 # maximum capacity

[Link] = cap

# Insert an element at the rear

def enqueue(self, x):

if [Link] == [Link]:

print("Queue is full!")

return

rear = ([Link] + [Link]) % [Link]

[Link][rear] = x

[Link] += 1

# Remove an element from the front

def dequeue(self):

if [Link] == 0:

print("Queue is empty!")

return -1

res = [Link][[Link]]

[Link] = ([Link] + 1) % [Link]

[Link] -= 1

return res

# Get the front element

def getFront(self):

if [Link] == 0:

return -1

return [Link][[Link]]
 # Get the rear element

def getRear(self):

if [Link] == 0:

return -1

rear = ([Link] + [Link] - 1) % [Link]

return [Link][rear]

if __name__ == "__main__":

q = myQueue(5)

[Link](10)

[Link](20)

[Link](30)

print([Link](), [Link]())

[Link]()

print([Link](), [Link]())

[Link](40)

print([Link](), [Link]())

Output

10 30

20 30

20 40