CAMELLIA INSTITUTE OF TECHNOLOGY & MANAGEMENT

SUBJECT : Data Structure & Algorithm(OE-EE501A)

Topic : Queue
Queue
■ A queue is a linear data structure that is open at both ends and the operations are performed
in First In First Out (FIFO) order.
■ We define a queue to be a list in which all additions to the list are made at one end, and all
deletions from the list are made at the other end. The element which is first pushed into the
order, the delete operation is first performed on that.
FIFO Principle of Queue:
■ A Queue is like a line waiting to purchase tickets, where the first person in line is the first
person served. (i.e. First come first serve).
■ 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(sometimes, head of the queue),
similarly, the position of the last entry in the queue, that is, the one most recently added, is
called the rear (or the tail) of the queue. See the below figure.
Characteristics of Queue:
Arrival process
■ Queue can handle multiple data.
■ We can access both ends. Customer’s
■ They are fast and flexible. Behaviour

Service Process

Characteristics of
queuing system
Queue Discipline

Nos of Servers

System Capacity
Queue Representation:
Array Representation of Queue:
■ Like stacks, Queues can also be represented in an array: In this representation, the Queue is
implemented using the array. Variables used in this case are
■ Queue: the name of the array storing queue elements.
■ Front: the index where the first element is stored in the array representing the queue.
■ Rear: the index where the last element is stored in an array representing the queue
Array representation of queue: C & C++
// Creating an empty queue // Creating an empty queue

// A structure to represent a queue // A structure to represent a queue

struct Queue { class Queue {
int front, rear, size; public:
unsigned capacity; int front, rear, size;
int* array; unsigned cap;
}; int* arr;
};
// function to create a queue of given capacity
// It initializes size of queue as 0 // Function to create a queue of given capacity
struct Queue* createQueue(unsigned capacity) // It initializes size of queue as 0
{ Queue* createQueue(unsigned cap)
struct Queue* queue {
= (struct Queue*)malloc(sizeof(struct Queue* queue = new Queue();
Queue)); queue->cap = cap;
queue->capacity = capacity; queue->front = queue->size = 0;
queue->front = queue->size = 0;
queue->rear = capacity - 1; queue->rear = cap - 1;
queue->array queue->arr = new int[(queue->cap *
= (int*)malloc(queue->capacity * sizeof(int))];
sizeof(int)); return queue;
return queue; }
}
 Array representation of queue: Java & Python3
{

// A structure to represent a queue # Creating an empty queue

static class Queue {
int front, rear, size; # A structure to represent a queue
int cap;
int arr[];
} class Queue:
# constructor
// Function to create a queue of given def __init__(self, cap):
capacity self.cap = cap
// It initializes size of queue as 0 self.front = 0
Queue createQueue(int cap) self.size = 0
{ self.rear = cap - 1
Queue queue = new Queue(); self.arr = [0] * cap
queue.cap = cap;
queue.front = 0; # Function to create a queue of given capacity
queue.size = 0; # It initializes size of queue as 0
def createQueue(self):
queue.rear = cap - 1; return Queue(self.cap)
queue.arr = new
int[queue.cap];
return queue;
}
Queue Representation:
Linked List Representation of Queue:
■ A queue can also be represented using following entities:
■ Linked-lists,
■ Pointers, and
■ Structures.
Types of Queue:
There are different types of queues:
■ Input Restricted Queue: This is a simple queue. In this type of queue, the input can be
taken from only one end but deletion can be done from any of the ends.
■ Output Restricted Queue: This is also a simple queue. In this type of queue, the input can
be taken from both ends but deletion can be done from only one end.
■ Circular Queue: This is a special type of queue where the last position is connected back
to the first position. Here also the operations are performed in FIFO order.
■ Double-Ended Queue (Dequeue): In a double-ended queue the insertion and deletion
operations, both can be performed from both ends.
■ Priority Queue: A priority queue is a special queue where the elements are accessed based
on the priority assigned to them.
Basic Operations for Queue in Data Structure:

Some of the basic operations for Queue in Data Structure are:

■ Enqueue() – Adds (or stores) an element to the end of the queue..
■ Dequeue() – Removal of elements from the queue.
■ Peek() or front()- Acquires the data element available at the front node of the queue
without deleting it.
■ rear() – This operation returns the element at the rear end without removing it.
■ isFull() – Validates if the queue is full.
■ isNull() – Checks if the queue is empty.
Enqueue():
■ Enqueue() operation in Queue adds (or stores) an element to the end of the queue.
The following steps should be taken to enqueue (insert) data into a queue:
■ Step 1: Check if the queue is full.
■ Step 2: If the queue is full, return overflow error and exit.
■ Step 3: If the queue is not full, increment the rear pointer to point to the next empty space.
■ Step 4: Add the data element to the queue location, where the rear is pointing.
■ Step 5: return success.
Implementation of Enqueue: C & C++

// Function to add an item to the queue. void queueEnqueue(int data)

// It changes rear and size {
void enqueue(struct Queue* queue, int item) // Check queue is full or not
{ if (capacity == rear) {
if (isFull(queue)) printf("\nQueue is full\
return; n");
queue->rear = (queue->rear + 1) % queue- return;
>capacity; }
queue->array[queue->rear] = item;
queue->size = queue->size + 1; // Insert element at the rear
printf("%d enqueued to queue\n", item); else {
} queue[rear] = data;
rear++;
}
return;
}
Dequeue():
Removes (or access) the first element from the queue.
The following steps are taken to perform the dequeue operation:
■ Step 1: Check if the queue is empty.
■ Step 2: If the queue is empty, return the underflow error and exit.
■ Step 3: If the queue is not empty, access the data where the front is pointing.
■ Step 4: Increment the front pointer to point to the next available data element.
■ Step 5: The Return success.
Implementation of dequeue: C & C++

// Function to remove an item from queue. void queueDequeue()

// It changes front and size {
int dequeue(struct Queue* queue) // If queue is empty
{ if (front == rear) {
if (isEmpty(queue)) { printf("\nQueue is
printf("\nQueue is empty\n"); empty\n");
return; return;
} }
int item = queue->array[queue->front];
queue->front = (queue->front + 1) % // Shift all the elements from
queue->capacity; index 2
queue->size = queue->size - 1; // till rear to the left by one
return item; else {
} for (int i = 0; i < rear -
1; i++) {
queue[i] =
queue[i + 1];
}

// decrement rear
rear--;
}
front(): C & C++
// Function to get front of queue // Function to get front of queue
int front(struct Queue* queue) int front(Queue* queue)
{ {
if (isempty(queue)) if (isempty(queue))
return INT_MIN; return INT_MIN;
return queue->arr[queue- return queue->arr[queue->front];
>front]; }
}

front(): JAVA & Python3

// Function to get front of queue # Function to get front of queue

int front(Queue queue) def que_front(self):
{ if self.isempty():
if (isempty(queue)) return "Queue
return is empty"
Integer.MIN_VALUE; return self.Q[self.front]
return queue.arr[queue.front];
}
rear() C & C++

int rear(struct Queue* front) int rear(queue<int>& myQueue)

{ {
if (front == NULL) { queue<int> tempQueue =
printf("Queue is empty.\n"); myQueue;
return -1;
} while (tempQueue.size() > 1) {
tempQueue.pop();
while (front->next != NULL) { }
front = front->next;
} return tempQueue.front();
}
return front->data;
}
rear() JAVA & Python3

public static int rear(Queue<Integer> myQueue) def rear(queue):

{ if queue.empty():
if (myQueue.isEmpty()) { print("Queue is
System.out.println("Queue is empty.")
empty."); return None
return -1;
} rear_element = None
while not queue.empty():
int rearElement = -1; rear_element =
while (!myQueue.isEmpty()) { queue.get()
rearElement = myQueue.poll();
} return rear_element

return rearElement;
}
isEmpty() : C & C++
// This function will check whether
// Queue is empty when size is 0 // the queue is empty or not:
bool isEmpty(struct Queue* queue) bool isEmpty()
{ {
return (queue->size == 0); if (front == -1)
} return true;
else
return false;
}

isEmpty() : JAVA & Python3

// This function will check whether # Queue is empty when size is 0

// the queue is empty or not: def isEmpty(self):
boolean isEmpty() return self.size == 0
{ # This code is contributed by Susobhan
if (front == -1) Akhuli
return true;
else
return false;
}
isFull() : C & C++
// Queue is full when size becomes // This function will check
// equal to the capacity // whether the queue is full or not.
bool isFull(struct Queue* queue) bool isFull()
{ {
return (queue->size == queue- if (front == 0 && rear ==
>capacity); MAX_SIZE - 1) {
} return true;
}
return false;
}
isFull() : JAVA & Python3
// This function will check # Queue is full when size becomes
// whether the queue is full or not. # equal to the capacity
boolean isFull()
{
if (front == 0 && rear == def isFull(self):
MAX_SIZE - 1) { return self.size == self.capacity
return true;
}
return false;
}
Implementation of Queue:
Queue can be implemented using following data structures:
■ Implementation of Queue using Structure in C/C++
■ Implementation of Queue using Arrays
■ Implementation of Queue using Linked List
Applications of Queue:
Application of queue is common. In a computer system, there may be queues of tasks waiting
for the printer, for access to disk storage, or even in a time-sharing system, for use of the CPU.
Within a single program, there may be multiple requests to be kept in a queue, or one task may
create other tasks, which must be done in turn by keeping them in a queue.
■ It has a single resource and multiple consumers.
■ It synchronizes between slow and fast devices.
■ In a network, a queue is used in devices such as a router/switch and mail queue.
■ Variations: dequeue, priority queue and double-ended priority queue.