Data Structure Using C

Queue
National Institute of Science & Technology

• Queue is an abstract data structure, somewhat similar to Stacks,Unlike stacks, a queue is open at both
NIST UNIVERSITY

ends.
• One end is always used to insert data (enqueue) and the other is used to remove data (dequeue).
• Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first.
• The most fundamental operations in the queue ADT include: enqueue(), dequeue(), peek(), isFull(),
isEmpty(). These are all built-in operations to carry out data manipulation and to check the status of the
queue.
• Queue uses two pointers − front and rear. The front pointer accesses the data from the front end
(helping in enqueueing) while the rear pointer accesses data from the rear end (helping in dequeuing).

1 Prof. Swetanjali Maharana

Data Structure Using C
Basic Operations on Queue
National Institute of Science & Technology

1. Enqueue:
NIST UNIVERSITY

Algorithm:
1. START Step 1: IF REAR=MAX-1
PRINT “ Overflow”
2. Check if the queue is full.
GOTO Step 4
3. If the queue is full, produce overflow error and exit.
[END OF IF]
4. If the queue is not full, increment rear pointer to
Step 2: IF FRONT= -1 and REAR= -1
point the next empty space.
SET FRONT = REAR = 0
5. Add data element to the queue location, where the ELSE
rear is pointing.
SET REAR= REAR+1
6. return success. [END OF IF]
7. END Step 3: SET QUEUE[REAR]= VALUE
Step 4: END

2 Prof. Swetanjali Maharana

Data Structure Using C
Basic Operations on Queue
National Institute of Science & Technology

1. Dequeue:
NIST UNIVERSITY

Algorithm:
1. START
Step 1: IF FRONT= -1 or FRONT > REAR
2. Check if the queue is empty.
PRINT “ Underflow”
3. If the queue is empty, produce underflow error and
ELSE
exit.
SET VALUE = QUEUE[FRONT]
4. If the queue is not empty, access the data where
SET FRONT = FRONT + 1
front is pointing.
[ END OF IF]
5. Increment front pointer to point to the next available
Step 2: END
data element.
6. Return success.
7. END

3 Prof. Swetanjali Maharana

Data Structure Using C
Basic Operations on Queue
National Institute of Science & Technology

3. PEEK
NIST UNIVERSITY

Algorithm:
1. START
2. Return the element at the front of the queue
3. END Step 1: IF front == -1
Print "Queue is Empty“
Else
Return Queue[front]
Step 2: END

4 Prof. Swetanjali Maharana

Data Structure Using C
Basic Operations on Queue
National Institute of Science & Technology

4. isFull
NIST UNIVERSITY

Algorithm:
1. START
2. If the count of queue elements equals the queue size,
return true Step 1: If rear == MAX – 1
3. Otherwise, return false Return True // Queue is full
4. END Else
Return False // Queue is not full
Step 2: END OF IF

5 Prof. Swetanjali Maharana

Data Structure Using C
Basic Operations on Queue
National Institute of Science & Technology

5. isEmpty
NIST UNIVERSITY

Algorithm:
1. START
2. If the count of queue elements equals zero, return true
3. Otherwise, return false Step 1: If front == -1
4. END Return True // Queue is empty
Else
Return False // Queue is not empty
Step 2: END OF IF

6 Prof. Swetanjali Maharana

Data Structure Using C
Implementation of Queue using structure
National Institute of Science & Technology

#include <stdio.h>
NIST UNIVERSITY

void enqueue(int data)

#define MAX 5 {
struct Queue if (isFull())
{ {
int arr[MAX]; printf("Queue is full. Cannot insert data.\n");
int front, rear; return;
} q = {{0}, -1, -1}; }
int isEmpty() if (q.front == -1)
{ q.front = 0;
return (q.front == -1); q.arr[++q.rear] = data;
} printf("Inserted: %d\n", data);
int isFull() }
{
return (q.rear == MAX - 1);
}

7 Prof. Swetanjali Maharana

Data Structure Using C
Implementation of Queue using structure
National Institute of Science & Technology

int dequeue() void display() {

NIST UNIVERSITY

{ if (isEmpty()) {
if (isEmpty()) printf("Queue is empty.\n");
{ return;
printf("Queue is empty. Cannot dequeue.\n"); }
return -1; // Return a sentinel value printf("Queue elements: ");
} for (int i = q.front; i <= q.rear; i++) {
int data = q.arr[q.front++]; printf("%d ", q.arr[i]);
if (q.front > q.rear) }
{ printf("\n");
q.front = q.rear = -1; }
}
return data;
}

8 Prof. Swetanjali Maharana

Data Structure Using C
Implementation of Queue using structure
National Institute of Science & Technology

int main() Output:

NIST UNIVERSITY

{ Inserted: 10
enqueue(10); Inserted: 20
enqueue(20); Inserted: 30
enqueue(30); Inserted: 40
enqueue(40); Inserted: 50
enqueue(50); Queue is full. Cannot insert data.
enqueue(60); Queue elements: 10 20 30 40 50
display(); Removed: 10
printf("Removed: %d\n", dequeue()); Removed: 20
printf("Removed: %d\n", dequeue()); Queue elements: 30 40 50
display();
return 0;
}

9 Prof. Swetanjali Maharana

Data Structure Using C
Type of Queue
National Institute of Science & Technology

1. Simple Queue or Linear Queue

NIST UNIVERSITY

2. Circular Queue
3. Double Ended Queue (or Deque)

1. Linear Queue
In Linear Queue, an insertion takes place from one end while the deletion occurs from another end. The
end at which the insertion takes place is known as the rear end, and the end at which the deletion takes
place is known as front end. It strictly follows the FIFO rule.

10 Prof. Swetanjali Maharana

Data Structure Using C
Type of Queue
National Institute of Science & Technology

The major drawback of using a linear Queue is that insertion is done only from the rear end. If the first
NIST UNIVERSITY

three elements are deleted from the Queue, we cannot insert more elements even though the space is
available in a Linear Queue. In this case, the linear Queue shows the overflow condition as the rear is
pointing to the last element of the Queue.

2. Circular Queue
In Circular Queue, all the nodes are represented as circular. It is similar to the linear Queue except that the
last element of the queue is connected to the first element. It is also known as Ring Buffer, as all the ends
are connected to another end.

11 Prof. Swetanjali Maharana

Data Structure Using C
Type of Queue
National Institute of Science & Technology

The drawback that occurs in a linear queue is overcome by using the circular queue. If the empty space
NIST UNIVERSITY

is available in a circular queue, the new element can be added in an empty space by simply
incrementing the value of rear. The main advantage of using the circular queue is better memory
utilization.

12 Prof. Swetanjali Maharana

Data Structure Using C
Basic Operations on Circular Queue
National Institute of Science & Technology

1. Enqueue:
NIST UNIVERSITY

Algorithm to insert an element in a circular queue

1. First, we will check whether the Queue is full or not.
2. Initially the front and rear are set to -1. When we insert the first element in a Queue, front and rear
both are set to 0.
3. When we insert a new element, the rear gets incremented, i.e., rear=rear+1.

There are two scenarios in which queue is not full:

1. If rear != max - 1, then rear will be incremented to mod(maxsize) and the new value will be inserted
at the rear end of the queue.
2. If front != 0 and rear = max - 1, it means that queue is not full, then set the value of rear to 0 and
insert the new element there.

13 Prof. Swetanjali Maharana

Data Structure Using C
Basic Operations on Circular Queue
National Institute of Science & Technology
NIST UNIVERSITY

Algorithm to insert an element in a circular queue

Step 1: IF (REAR+1)%MAX = FRONT
Write " OVERFLOW "
There are two cases in which the element Goto step 4
cannot be inserted: [End OF IF]
1. When front ==0 && rear = max-1, which Step 2: IF FRONT = -1 and REAR = -1
means that front is at the first position SET FRONT = REAR = 0
of the Queue and rear is at the last ELSE IF REAR = MAX - 1 and FRONT ! = 0
position of the Queue. SET REAR = 0
2. front== rear + 1; ELSE
SET REAR = (REAR + 1) % MAX
[END OF IF]
Step 3: SET QUEUE[REAR] = VAL
Step 4: EXIT

14 Prof. Swetanjali Maharana

Data Structure Using C
Basic Operations on Circular Queue
National Institute of Science & Technology

Step 1: IF FRONT = -1
1. Dequeue:
NIST UNIVERSITY

Write " UNDERFLOW "

Goto Step 4
Algorithm:
[END of IF]
1. First, we check whether the Queue is empty or
Step 2: SET VAL = QUEUE[FRONT]
not. If the queue is empty, we cannot perform
Step 3: IF FRONT = REAR
the dequeue operation.
SET FRONT = REAR = -1
2. When the element is deleted, the value of front
ELSE
gets decremented by 1.
IF FRONT = MAX -1
3. If there is only one element left which is to be
SET FRONT = 0
deleted, then the front and rear are reset to -1.
ELSE
SET FRONT = FRONT + 1
[END of IF]
[END OF IF]
Step 4: EXIT

15 Prof. Swetanjali Maharana

Data Structure Using C
Basic Operations on Circular Queue
National Institute of Science & Technology
NIST UNIVERSITY

16 Prof. Swetanjali Maharana

Data Structure Using C
Basic Operations on Circular Queue
National Institute of Science & Technology
NIST UNIVERSITY

17 Prof. Swetanjali Maharana

Data Structure Using C
Implementation of Circular Queue using Array
National Institute of Science & Technology

#include <stdio.h> printf("Queue is overflow..");

NIST UNIVERSITY

# define max 6 }
int queue[max]; // array declaration else {
int front=-1; rear=(rear+1)%max; // rear is incremented
int rear=-1; queue[rear]=element; // assigning a value to the
void enqueue(int element) queue at the rear position.
{ }
if(front==-1 && rear==-1) }
{ int dequeue()
front=0; {
rear=0; if((front==-1) && (rear==-1)) // condition to check
queue[rear]=element; queue is empty
} {
else if((rear+1)%max==front) printf("\nQueue is underflow..");
{ }

18 Prof. Swetanjali Maharana

Data Structure Using C
Implementation of Circular Queue using Array
National Institute of Science & Technology

else if(front==rear)
NIST UNIVERSITY

{ if(front==-1 && rear==-1)

printf("\nThe dequeued element is %d", queue[front]); {
front=-1; printf("\n Queue is empty..");
rear=-1; }
} else
else {
{ printf("\nElements in a Queue are :");
printf("\nThe dequeued element is %d", queue[front]); while(i<=rear)
front=(front+1)%max; {
} printf("%d,", queue[i]);
} i=(i+1)%max;
void display() }
{ }
int i=front; }

19 Prof. Swetanjali Maharana

Data Structure Using C
Implementation of Circular Queue using Array
National Institute of Science & Technology

int main() case 1:

NIST UNIVERSITY

{ printf("Enter the element which is to be

int choice=1,x; inserted");
while(choice<4 && choice!=0) scanf("%d", &x);
{ enqueue(x);
printf("\n Press 1: Insert an element"); break;
printf("\nPress 2: Delete an element"); case 2:
printf("\nPress 3: Display the element"); dequeue();
printf("\nEnter your choice"); break;
scanf("%d", &choice); case 3:
display();
switch(choice) }}
{ return 0;
}

20 Prof. Swetanjali Maharana

Data Structure Using C
Implementation of Circular Queue using Array
National Institute of Science & Technology

Output: Enter your choice: 3

NIST UNIVERSITY

Press 1: Insert an element Elements in the queue: 10 20 30

Press 2: Delete an element Enter your choice: 2
Press 3: Display the queue The dequeued element is 10
Press 0: Exit Enter your choice: 3
Enter your choice: 1 Elements in the queue: 20 30
Enter the element to insert: 10 Enter your choice: 0
Inserted: 10 Exiting program...
Enter your choice: 1
Enter the element to insert: 20
Inserted: 20
Enter your choice: 1
Enter the element to insert: 30
Inserted: 30

21 Prof. Swetanjali Maharana

Data Structure Using C
Type of Queue
National Institute of Science & Technology

3. Double Ended Queue :

NIST UNIVERSITY

The deque stands for Double Ended Queue. Deque is a linear data structure where the insertion
and deletion operations are performed from both ends. We can say that deque is a generalized
version of the queue.
Though the insertion and deletion in a deque can be performed on both ends, it does not follow
the FIFO rule. The representation of a deque is given as follows -

22 Prof. Swetanjali Maharana

Data Structure Using C
Double Ended Queue
National Institute of Science & Technology

Types of deque
NIST UNIVERSITY

There are two types of deque -

o Input restricted queue
o Output restricted queue
Input restricted Queue
In input restricted queue, insertion operation can be performed at only one end, while deletion
can be performed from both ends.

23 Prof. Swetanjali Maharana

Data Structure Using C
Double Ended Queue
National Institute of Science & Technology

Output restricted Queue

NIST UNIVERSITY

In output restricted queue, deletion operation can be performed at only one end, while insertion
can be performed from both ends.

24 Prof. Swetanjali Maharana

Data Structure Using C
Double Ended Queue
National Institute of Science & Technology

Operations performed on deque

NIST UNIVERSITY

There are the following operations that can be applied on a deque -

1) Insertion at front
2) Insertion at rear
3) Deletion at front
4) Deletion at rear
We can also perform peek operations in the deque along with the operations listed above. Through peek
operation, we can get the deque's front and rear elements of the deque. So, in addition to the above
operations, following operations are also supported in deque –
• Get the front item from the deque
• Get the rear item from the deque
• Check whether the deque is full or not
• Checks whether the deque is empty or not

25 Prof. Swetanjali Maharana

Data Structure Using C
Double Ended Queue
National Institute of Science & Technology

1) Insertion at the front end

NIST UNIVERSITY

In this operation, the element is inserted from the front end

of the queue. Before implementing the operation, we first
have to check whether the queue is full or not. If the queue is
not full, then the element can be inserted from the front end
by using the below conditions –

• If the queue is empty, both rear and front are initialized

with 0. Now, both will point to the first element.
• Otherwise, check the position of the front if the front is
less than 1 (front < 1), then reinitialize it by front = n - 1,
i.e., the last index of the array.

26 Prof. Swetanjali Maharana

Data Structure Using C
Type of Queue
National Institute of Science & Technology

2) Insertion at the rear end

NIST UNIVERSITY

In this operation, the element is inserted from the rear

end of the queue. Before implementing the operation,
we first have to check again whether the queue is full or
not. If the queue is not full, then the element can be
inserted from the rear end by using the below
conditions -
• If the queue is empty, both rear and front are
initialized with 0. Now, both will point to the first
element.
• Otherwise, increment the rear by 1. If the rear is at
last index (or size - 1), then instead of increasing it by
1, we have to make it equal to 0.

27 Prof. Swetanjali Maharana

Data Structure Using C
Double Ended Queue
National Institute of Science & Technology

3) Deletion at the front end

NIST UNIVERSITY

In this operation, the element is deleted from the front end

of the queue. Before implementing the operation, we first
have to check whether the queue is empty or not.
If the queue is empty, i.e., front = -1, it is the underflow
condition, and we cannot perform the deletion. If the
queue is not full, then the element can be inserted from the
front end by using the below conditions -
If the deque has only one element, set rear = -1 and front =
-1.
Else if front is at end (that means front = size - 1), set front =
0.
Else increment the front by 1, (i.e., front = front + 1).

28 Prof. Swetanjali Maharana

Data Structure Using C
Double Ended Queue
National Institute of Science & Technology

4) Deletion at the rear end

NIST UNIVERSITY

In this operation, the element is deleted from the

rear end of the queue. Before implementing the
operation, we first have to check whether the queue
is empty or not.
If the queue is empty, i.e., front = -1, it is the
underflow condition, and we cannot perform the
deletion.
If the deque has only one element, set rear = -1 and
front = -1.
If rear = 0 (rear is at front), then set rear = n - 1.
Else, decrement the rear by 1 (or, rear = rear -1).

29 Prof. Swetanjali Maharana

Data Structure Using C
Double Ended Queue
National Institute of Science & Technology
NIST UNIVERSITY

Check empty
This operation is performed to check whether the deque is empty or not. If front = -1, it
means that the deque is empty.
Check full
This operation is performed to check whether the deque is full or not. If front = rear + 1, or
front = 0 and rear = n - 1 it means that the deque is full.
The time complexity of all of the above operations of the deque is O(1), i.e., constant.

30 Prof. Swetanjali Maharana

Data Structure Using C
Implementation of Double Ended Queue using Structure
National Institute of Science & Technology

#include <stdio.h> // Insert element at the front

NIST UNIVERSITY

#define MAX 5 void insertFront(int data) {

struct Deque if (isFull()) {
{ printf("Deque is full. Cannot insert %d at front.\n",
int arr[MAX]; data);
int front, rear; return;
} dq = {{0}, -1, -1}; }
if (isEmpty()) {
int isEmpty() { dq.front = dq.rear = 0;
return (dq.front == -1); } else {
} dq.front = (dq.front - 1 + MAX) % MAX;
int isFull() { }
return ((dq.rear + 1) % MAX == dq.front); dq.arr[dq.front] = data;
} printf("Inserted %d at front.\n", data);
}

31 Prof. Swetanjali Maharana

Data Structure Using C
Implementation of Double Ended Queue using Structure
National Institute of Science & Technology

// Insert element at the rear // Delete element from the front

NIST UNIVERSITY

void insertRear(int data) { void deleteFront() {

if (isFull()) { if (isEmpty()) {
printf("Deque is full. Cannot insert %d at rear.\n", printf("Deque is empty. Cannot delete from front.\n");
data); return;
return; }
} printf("Deleted %d from front.\n", dq.arr[dq.front]);
if (isEmpty()) { if (dq.front == dq.rear) {
dq.front = dq.rear = 0; dq.front = dq.rear = -1;
} else { } else {
dq.rear = (dq.rear + 1) % MAX; dq.front = (dq.front + 1) % MAX;
} }
dq.arr[dq.rear] = data; }
printf("Inserted %d at rear.\n", data);
}

32 Prof. Swetanjali Maharana

Data Structure Using C
Implementation of Double Ended Queue using Structure
National Institute of Science & Technology

// Delete element from the rear void display() {

NIST UNIVERSITY

void deleteRear() { if (isEmpty()) {

if (isEmpty()) { printf("Deque is empty.\n");
printf("Deque is empty. Cannot delete from rear.\n"); return;
return; }
} printf("Deque elements: ");
printf("Deleted %d from rear.\n", dq.arr[dq.rear]); int i = dq.front;
if (dq.front == dq.rear) { while (1) {
dq.front = dq.rear = -1; printf("%d ", dq.arr[i]);
} else { if (i == dq.rear) break;
dq.rear = (dq.rear - 1 + MAX) % MAX; i = (i + 1) % MAX;
} }
} printf("\n");
}

33 Prof. Swetanjali Maharana

Data Structure Using C
Implementation of Double Ended Queue using Structure
National Institute of Science & Technology

int main() { case 2:

NIST UNIVERSITY

int choice, data; printf("Enter value: ");

while (1) { scanf("%d", &data);
printf("\n1. Insert at Front\n2. Insert at Rear\n3. insertRear(data);
Delete from Front\n4. Delete from Rear\n5. Display\n6. break;
Exit\n"); case 3:
printf("Enter choice: "); deleteFront();
scanf("%d", &choice); break;
switch (choice) { case 4:
case 1: deleteRear();
printf("Enter value: "); break;
scanf("%d", &data); case 5:
insertFront(data); display();
break; break;

34 Prof. Swetanjali Maharana

Data Structure Using C
Implementation of Double Ended Queue using Structure
National Institute of Science & Technology

Enter choice: 2
case 6: printf("Exiting...\n");
NIST UNIVERSITY

Enter value: 20
return 0;
Inserted 20 at rear.
default:
Enter choice: 1
printf("Invalid choice! Try again.\n");
Enter value: 5
} } }
Inserted 5 at front.
Output:
Enter choice: 5
1. Insert at Front
Deque elements: 5 10 20
2. Insert at Rear
Enter choice: 3
3. Delete from Front
Deleted 5 from front.
4. Delete from Rear
Enter choice: 4
5. Display
Deleted 20 from rear.
6. Exit
Enter choice: 5
Enter choice: 2
Deque elements: 10
Enter value: 10
Enter choice: 6
Inserted 10 at rear.

35 Prof. Swetanjali Maharana