Implementation of Queue using Python

Understanding Queue Implementation in Python

A queue is a linear data structure that follows the First In, First Out (FIFO) principle — the element added first is the one removed first. In Python, you can implement a queue using the built-in list data type. The list provides all the operations needed to simulate a queue, though you must decide which end of the list represents the front and which represents the rear.

For a queue implemented with a list, you fix one end as the front and the opposite end as the rear. In the standard approach used here, index [0] is the front (where elements are removed) and the last index [n-1] is the rear (where new elements are added). This choice is consistent throughout the implementation.

Functions to Define for a Queue

To create a working queue structure, you define the following user-defined functions. The naming follows general queue conventions, but you can choose any valid function name.

Creating the Queue

Start by assigning an empty list to a variable, say myQueue:

myQueue = list()

This initialises an empty queue.

Enqueue — Inserting an Element

The enqueue function adds a new element at the rear of the queue. It takes two parameters: the queue name and the element to insert. Since append() always adds an element at the end of a list, it naturally places the element at the rear.

def enqueue(myQueue, element):
    myQueue.append(element)

isEmpty — Checking if the Queue is Empty

This function checks whether the queue has any elements. It uses len() to find the length of the list and returns True if the length is zero, False otherwise.

def isEmpty(myQueue):
    if len(myQueue) == 0:
        return True
    else:
        return False

Dequeue — Removing an Element from the Front

The dequeue function removes and returns the element at the front of the queue. It first checks if the queue is empty (using isEmpty). If not empty, it uses pop(0) to remove the element at index [0] — the front. If the queue is empty, it prints a message and returns nothing (implicitly None).

def dequeue(myQueue):
    if not (isEmpty(myQueue)):
        return myQueue.pop(0)
    else:
        print("Queue is empty")

Size — Getting the Number of Elements

The size function returns the current number of elements in the queue using len().

def size(myQueue):
    return len(myQueue)

Peek — Reading the Front Element Without Removing It

The peek function returns the value at the front of the queue (index [0]) without deleting it. If the queue is empty, it prints a message and returns None.

def peek(myQueue):
    if isEmpty(myQueue):
        print('Queue is empty')
        return None
    else:
        return myQueue[0]

A Real-World Example: Bank Cash Counter Queue

The textbook illustrates queue operations using a bank scenario. People form a queue at a cash counter. The events happen in this order:

1. Two friends arrive together and join the queue — enqueue is performed twice.
2. The first person is served and leaves — dequeue is performed. The cashier calls "Next" to serve the new front person.
3. The cashier wants to know how many people are waiting — size is checked.
4. Three more people walk in and join the queue — enqueue is performed three times.
5. Another person is served and leaves — dequeue is performed. Cashier calls "Next".
6. The next three people are served one after another — dequeue is performed three times.
7. The cashier calls "Next" and finds no one left — an underflow situation (empty queue) occurs.

Complete Program for the Bank Scenario

The textbook provides Program 4-1, which implements the above scenario step by step. Here is the code exactly as given:

myQueue = list()  # each person to be assigned a code as P1, P2, P3,...

element = input("enter person’s code to enter in queue :")
enqueue(myQueue, element)

element = input("enter person’s code for insertion in queue :")
enqueue(myQueue, element)

print("person removed from queue is:", dequeue(myQueue))
print("Number of people in the queue is :", size(myQueue))

element = input("enter person’s code to enter in queue :")
enqueue(myQueue, element)

element = input("enter person’s code to enter in queue :")
enqueue(myQueue, element)

element = input("enter person’s code to enter in queue :")
enqueue(myQueue, element)

print("Now we are going to remove remaining people from the queue")
while not isEmpty(myQueue):
    print("person removed from queue is ", dequeue(myQueue))

Output of the program:

enter person’s code to enter in queue :P1
enter person’s code to enter in queue :P2
person removed from the queue is :p1
number of people in the queue is :1
enter person’s code to enter in queue :P3
enter person’s code to enter in queue :P4
enter person’s code to enter in queue :P5
Now we are going to remove remaining people from the queue
person removed from the queue is :p2
person removed from the queue is :p3
person removed from the queue is :p4
person removed from the queue is :p5
Queue is empty