Data Structures and Algorithms Using Python

Another important data structure is queue. Queues are also exhaustively used in various situations in computer science. In this chapter we will discuss the operations related to queues; how a queue is represented in memory, both array and linked representation of queues, different types of queues and various applications of queues.

9.1 Definitions and Concept

A queue is a linear data structure in which insertion and deletion operations take place at two different ends. The insertion operation is commonly known as ENQUEUE and the deletion operation is known as DEQUEUE. These two operations take place at two different ends. The end at which elements are inserted is known as the rear end and the other end at which elements are deleted from the queue is known as the front end. Elements are inserted through the rear end and removed through the front end following the First-In-First-Out (FIFO) order, i.e. in the order the elements entered the queue they will leave the queue maintaining the same order. In real life we are very familiar with queues. We can see several queues in our surroundings. For example, passengers standing in front of a railway ticket booking counter. The passenger who stands at the first position gets the ticket first and when a new passenger comes, he joins the queue at the end. The same can be seen when passengers wait at a bus stop, people standing in front of a ticket counter in a cinema hall, luggage moving through conveyor belt, cars passing through single lane in a one-way road, etc.

9.2 Operations Associated with Queues

The basic operations related to a queue are as follows:

• • Enqueue: Insert an element into a queue.

• • Dequeue: Retrieve an element from a queue.

Apart from these basic two operations, to use a queue efficiently we need to add the following functionalities:

• • Peek: Get the front element of a queue without removing it.

• • Isempty: To check whether a queue is empty or not.

• • Isfull: To check whether a queue is full or not.

All these operations execute with the time complexity O(1).

Like in stack, the peek operation is required to check the front element of the queue without removing it. And if a queue is full, the enqueue operation cannot be done on the queue. Similarly, dequeue and peek operations cannot be performed on an empty queue.