Queue

A Queue is a data structure in which we can add element only at one end, called the rear of the queue, and delete
element only at the other end, called the front of the queue.

There are two operations possible on the queue.

• Add an element to the queue.

• Delete an element from the queue.

To understand how the above operations work on a queue. See the example given below.
From the above image, we can see that when we add a new element in the queue, the variable R is increased by
1, and the new element is added at the new position of R. Similarly, when we delete an element from the queue,
the variable F is increased by 1.
The queue behaves like a first in first out manner. It means that the elements that are added first to the queue,
are removed first from the queue.
So a queue is also known as FIFO (First In First Out) data structure.

Array Implementation of Queue

Since a queue is a collection of the same type of elements, so we can implement the queue using an array.

In the above image, we can see an array named arr whose size is 5. We take two variables R and F, The
variable R stands for rear and the default value is -1. The variable F stands for front and the default value is 0.

Add Operation in Queue

For add operation in the queue first, we check if the value of R is equal to the value of size-1 then, we will
display a message Queue is full, else we will increase the value of R by 1 and add the element in the array at the
new location of R.
Example

if(R==size-1)
{
printf("Queue is full\n");
}
else
{
R=R+1;
arr[R]=new_item;
}

If we add three elements, say 12, 15 and 26 in the queue, then the queue will look like as shown in the image
below.

Delete Operation in Queue

For delete operation in the queue first, we check if the value of F is greater than the value of R then, we will
display a message Queue is empty, else we will display the deleted element on the screen and then increase
the value of F by 1.
Example
if(F>R)
{
printf("Queue is empty\n");
}
else
{
printf("Element Deleted = %d",arr[F]);
F=F+1;
}
If we delete the first elements 12 from the queue, then the queue will look like as shown in the image below.

Program of Queue using Array

#include <stdio.h>
#include <stdlib.h>

#define size 5
int main()
{
int arr[size],R=-1,F=0,ch,n,i;

for(;;) // An infinite loop

{
printf("1. Add\n");
printf("2. Delete\n");
printf("3. Display\n");
printf("4. Exit\n");
printf("Enter Choice: ");
scanf("%d",&ch);

switch(ch)
{
case 1:
if(R==size-1)
printf("Queue is full");
else
{
printf("Enter a number ");
scanf("%d",&n);
R++;
arr[R]=n;
}
break;

case 2:
if(F>R)
printf("Queue is empty");
else
{
printf("Number Deleted = %d",arr[F]);
F++;
}
break;

case 3:
if(F>R)
printf("Queue is empty");
else
{
for(i=F; i<=R; i++)
printf("%d ",arr[i]);
}
break;

case 4: exit(0);

default: printf("Wrong Choice");

}
}
return 0;
}
 Circular Queue
A Circular Queue is a data structure in which elements are stored in a circular manner. In Circular Queue, after
the last element, the first element occurs.

A Circular Queue is used to overcome the limitation we face in the array implementation of a Queue. The
problem is that when the rear reaches the end and if we delete some elements from the front and then try to
add a new element in the queue, it says "Queue is full", but still there are spaces available in the queue. See the
example given below.

In the above image, the queue is full because the rear R reached the end of the queue. We have deleted two
elements from the queue, so the front F is at index 2. We can see that there are spaces available in the queue,
but we can't add a new element because the rear can't go back to index 0.

Operation on Circular Queue

There are two operations possible on the circular queue.
• Add an element in the circular queue.
• Delete an element from the circular queue.
To understand how the above operations work on a circular queue. See the example given below.
From the above image, we can see that when we add a new element in the circular queue, the variable R is
increased by R=(R+1)%Size, and the new element is added at the new position of R and te is increased by 1.
Similarly, when we delete an element from the circular queue, the variable F is increased
by F=(F+1)%Size and te is decreased by 1.

Add Operation in Circular Queue

For add operation in the circular queue first, we check if the value of te is equal to the value of size then, we will
display a message Queue is full, else we will increase the value of R by R=(R+1)%Size and add the element in the
array at the new location of R and then increased the value of te by 1.

if(te==size)
{
printf("Queue is full\n");
}
 else
{
R=(R+1)%size;
arr[R]=new_item;
te=te+1;
}

Delete Operation in Circular Queue

For delete operation in the circular queue first, we check if the value of te is 0 then, we will display a
message Queue is empty, else we will display the deleted element on the screen and then increase the value
of F by F=(F+1)%Size and then decrease the value of te by 1.

if(te==0)
{
printf("Queue is empty\n");
}
else
{
printf("Element Deleted = %d",arr[F]);
F=(F+1)%size;
te=te-1;
}

Program of Circular Queue using Array

Below is the complete program of circular queue in C using an array having size 5.

#include <stdio.h>
#include <stdlib.h>

#define size 5

int main()
{

int arr[size],R=-1,F=0,te=0,ch,n,i,x;

for(;;) // An infinite loop

{
printf("1. Add\n");
printf("2. Delete\n");
printf("3. Display\n");
printf("4. Exit\n");

printf("Enter Choice: ");

scanf("%d",&ch);
 switch(ch)
{
case 1:
if(te==size)
printf("Queue is full");
else
{
printf("Enter a number ");
scanf("%d",&n);
R=(R+1)%size;
arr[R]=n;
te=te+1;
}
break;

case 2:
if(te==0)
printf("Queue is empty");
else
{
printf("Number Deleted = %d",arr[F]);
F=(F+1)%size;
te=te-1;
}
break;

case 3:
if(te==0)
printf("Queue is empty");
else
{
x=F;
for(i=1; i<=te; i++)
{
printf("%d ",arr[x]);
x=(x+1)%size;
}
}
break;

case 4:
exit(0);

default:
printf("Wrong Choice");
}
}
return 0;
}
 Singly Linked List

Singly Linked List is a linear and unidirectional data structure, where data is saved on the nodes, and each node
is connected via a link to its next node. Each node contains a data field and a link to the next node. Singly Linked
Lists can be traversed in only one direction.

Here’s a node structure of a Singly Linked List:

Node structure defined in C:

struct Node {
int data;
struct Node* next;
};

Operations of Singly Linked List

• Inserting at head
• Inserting at tail
• Inserting after a node
• Delete the head node
• Delete the tail node
• Search and Delete a node
• Traversing the Linked List

Here’s an example of a linked list with four nodes.

Insertion at the head of a Singly Linked List

To perform this operation, we need to follow two important conditions. They’re

1. If the list is empty, then the newly created node will be the head node, and the next node of the head will
be ”NULL”.
2. If the list is not empty, the new node will be the head node, and the next will point to the previous head
node.

Here’s the C code for inserting a node at the head of a linked list:

struct Node* insertAtHead(struct Node* head, int value) {

// Create a new node with the given value

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
 // If the list is empty, make the new node the head
if (head == NULL) {
newNode->next = NULL;
head= newNode;
return head;
}
else {
// Otherwise, insert the new node at the head
newNode->next = head;
head= newNode;
return head;
}
}

Insertion at the end of a Singly Linked List

Step 1) Traverse until the “next” node of the current node becomes null.
Step 2) Create a new node with the specified value.
Step 3) Assign the new node as the next node of the tail node.

C code for inserting a node at the tail of a singly list:

struct Node* insertAtEnd(struct Node* head, int value) {

// Create a new node with the given value

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;

// If the list is empty, make the new node the head

if (head == NULL) {
return newNode;
}
else {
// Traverse the list to the end
struct Node* current = head;
while (current->next != NULL) {
current = current->next;
}
 // Insert the new node at the end
current->next = newNode;
return head;
}
}

Insertion after a node in a Singly Linked List

Step 1) Traverse the next node until the value of the current node equals the search item.
Step 2) New node’s next pointer will be the current node’s next pointer.
Step 3) Current node’s next node will be the new node.

Here’s the C code for inserting a node after a node:

struct Node* insertAfter(struct Node* head, int value, int searchItem) {

// Create a new node with the given value

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;

// Traverse the list to find the node with the specified searchItem
struct Node* current = head;
while (current != NULL && current->data != searchItem) {
current = current->next;
}

// If the searchItem is not found, return the original list

if (current == NULL) {
return head;
}

// Insert the new node after the node with searchItem

newNode->next = current->next;
current->next = newNode;

return head;
}
Delete the head node of the singly linked list
Step 1) Assign the next node of the head node as the new head.
Step 2) Free the allocated memory by the previous head node.
Step 3) Return the new head node.

The C code for deleting the head node:

struct Node* deleteHead(struct Node* head) {

// If the list is empty, return NULL

if (head == NULL) {
return NULL;
}

// Store the current head in a temporary variable

struct Node* temp = head;

// Update the head to the next node

head = head->next;

// Free the memory of the original head

free(temp);

return head;
}
 After deleting the head

Delete the tail node of the singly linked list

Step 1) Traverse before the tail node. Save the current node.
Step 2) Free the memory of the next node of the current node.
Step 3) Set the next node of the current node as NULL.

Here’s the C code for deleting the tail node:

struct Node* deleteTail(struct Node* head) {

// If the list is empty or has only one element, free the head and return NULL
if (head == NULL || head->next == NULL) {
free(head);
return NULL;
}

// Traverse the list to the second-to-last node

struct Node* current = head;
while (current->next->next != NULL) {
current = current->next;
}

// Free the last node and update the next pointer of the second-to-last node
free(current->next);
current->next = NULL;

return head;
}
Search and delete a node from a singly linked list
Step 1) Traverse until the end of the linked list. Check if the current node is equal to the search node or not.
Step 2) If any node matches, store the node pointer to the current node.
Step 3) The “next” of the previous node will be the next node of the current node.
Step 4) Delete and free the memory of the current node.

C code for search and delete a node from a singly linked list:

struct Node* searchAndDelete(struct Node* head, int searchItem) {

// If the list is empty, return NULL

if (head == NULL) {
return NULL;
}

// Traverse the list to find the node with the specified searchItem
struct Node* current = head;
while (current->next != NULL && current->next->data != searchItem) {
current = current->next;
}

// If the searchItem is not found, return the original list

if (current->next == NULL) {
return head;
}

// Delete the node with the specified searchItem

struct Node* temp = current->next;
current->next = temp->next;
free(temp);

return head;
}
Traverse a singly linked list
Step 1) Traverse each node until we get null as the next node.
Step 2) Print the value of the current node.

C code for traversing a singly linked list:

void traverse(struct Node* head) {

// Traverse the list and print the values
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
Linked Stacks
Stack is a linear data structure which follows the property Last In First Out (LIFO). This means, the last
inserted element will be the first to be removed. Because of this nature, stack has only one end indicated
by variable Top. Top take care of the element present at the top of the stack. Two basic operations that
can be applied to stack are
1. Insertion, usually termed as Push and
2. Deletion, usually termed as Pop.

Two conditions are checked while push or pop operation on the linked list.
1. Overflow: the stack is full; element cannot be inserted
2. Underflow: the stack is empty; cannot remove an element

Linked list representation of the stack allows it to grow or shrink without any prior fixed limit due to the
dynamic nature of the linked list. Diagram shows how a stack data structure can be represented using
linked list.

This is the linked list representation of a stack having four elements. The top most element is at the
beginning of the list. Here, the top most element is 80. And the oldest element is at the end of the list.
Here, the oldest element is 50. The first element of the linked list here is represented by a pointer variable
Top.

Push Operation
Push operation is the insertion of an element at the top of the stack. In case of linked list to represent
the stack, the push operation can be performed by inserting an element at the beginning of the linked
list. Here is the C code depicting the push operation on stack where, the element Data is inserted into
the stack using linked list. A stack pointer variable Top points to the top most element or node of the
stack.

// Define a structure for the node

struct Node
{
int info; // Data of the node
struct Node* next; // Pointer to the next node
};

struct Node* top = NULL;

// Function to push a new element onto the stack
void push(int data)
{

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

 newNode->info = data;
newNode->next = top;
top = newNode;
}

Pop Operation

Pop operation is the deletion of an element from the stack that can be performed by deleting an element
at the beginning of the linked list. While performing pop operation, underflow condition must be checked.
Here, the underflow condition occurs when the stack is empty and we try to delete an element from the
stack. Here is an algorithm depicting the pop operation on stack, where, the first element or node pointed
by stack pointer variable Top is deleted.

// Function to pop an element from the stack

int pop()
{

if (top == NULL)
{
printf("Stack is Empty, Underflow Condition\n");
}

int data = top->info;

struct Node* temp = top;
top = top->next;

free(temp);
return data;
}
Linked Queues
Queue is a linear data structure which follows the property, First In first Out (FIFO) or First Come First
Serve (FCFS). The first inserted element will be the first to be removed. Queue has two ends, one is
Front and other is Rear. Front variable indicates the oldest element inserted into the queue and Rear
variable indicates the last element inserted into the queue.

Two basic operations that can be applied to queue are

1. Insertion operation, that takes place at Rear end
2. Deletion operation, that takes place at Front end.

Two conditions are checked while insertion or deletion operation on the linked list.
1. Overflow: the queue is full; element cannot be inserted
2. Underflow: the queue is empty; cannot remove an element

Linked list representation of the queue allows it to grow or shrink without any prior fixed limit due to the
dynamic nature of the linked list. Diagram shows how a queue data structure can be represented using
linked list.

Insertion Operation
The insertion of new element takes place at the rear end of the queue. Below is the diagram along with
algorithm for insertion of an element ‘e’ into the queue. The element ‘e’ is inserted at the Rear end of the
list.
// Define a structure for the node
struct Node
{
int info; // Data of the node
struct Node* next; // Pointer to the next node
};

struct Node* front = NULL;

struct Node* rear = NULL;

// Function to insert an element into the queue

void enqueue( int data)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->info = data;
newNode->next = NULL;

if (rear == NULL)
{
front = rear = newNode;
}
else
{
rear->next = newNode;
rear = newNode;
}

Deletion operation
Deletion of an element from the will be performed at the beginning of the linked list. While deleting an
element from the queue, underflow condition must be checked. Here, the underflow condition occurs
when the queue is empty and we try to delete an element from the queue. Here is the algorithm depicting
the deletion operation on queue. The element at the front end of the queue is deleted.
// Function to remove an element from the queue
int dequeue()
{
if (front == NULL)
{
printf("Queue is Empty\n");
}

int data = front->info;

struct Node* temp = *front;

if (front == rear)
{
front = rear = NULL;
}
else
{
front = front->next;
}

free(temp);

return data;
}