In this section of the tutorial, we will discuss the use of Queue in Data Structure and some important Queue Operations as well as its implementation in programs that will be used thoroughly in this Data Structure tutorial.
Now, let’s move on further to the introduction of Queue in Data Structure.
What is Queue in Data Structure?
A Queue is a linear list where the data can be inserted at one end, i.e. rear, and the data can be deleted from the other end, i.e. front.
- The limitations of Queue makes the data processed through the queue in the same order in which they are inputted.
- The Queue follows the first-in-first-out(FIFO) structure in the data structure.
- A queue somewhat resembles a line. In fact in day to day life, if we form a line of people one after another, it is a form a queue.
- Here, the above diagram shows the representation of queue.
- One queue is of people and the other is of computer memory.
- In both the queue the people and the data enter from the rear and pass through the body of queue until they all arrive at the queue front.
- From the front of queue, they leave the queue from there.
Queue Operations
There are four main queue operations that are mostly implemented frequently in data structure problems. They are enqueue, dequeue, queue front, and queue rear.
Enqueue
Enqueue performs queue insert operation in data structure.
- When we enter the data in the queue, the newly entered element becomes the rear of the queue.
- Enqueue, however, has one limitation where it runs out of memory for the data.
- If there is not enough memory for a new element in the queue, there is an overflow condition of the queue.
Dequeue
Dequeue performs the queue delete operation in a queue.
- Dequeue deletes a data element from the front of the queue.
- The data that is at the front of the queue is removed and returned to the user.
- In situations where there is no data in the queue, the queue is in an underflow state.
Queue Front
Queue front is used to retrieve the data that is at the front of the queue.
- Queue front returns the data at the front of the queue to the user without changing any of the contents of the queue.
- In situations when there is no data in the queue where we can implement queue front, then the queue is in an underflow condition.
Queue Rear
Queue rear is used to retrieve the data at the rear of the queue.
- Queue rear retrieves the data element present at the rear end of the queue.
- In situations when there is no data in the queue where we can implement queue rear, then the queue is said to be in an underflow state.
Queue Linked List Implementation
We can implement a Queue using a linked list. The actual implementation maybe different from what we learn here depending upon the nature of the program.
We need two basic structures while implementing queue, i.e. a queue head structure, and a data node structure.
Queue Head
The queue contains two pointers and a count part in it. These fields are located inside the queue head structure.
- We can have a look at the above diagram to understand the queue head structure.
- Queue head can also have other attributes as well such as the maximum number of items present in the queue.
- These types of attributes can be stored in the queue head structure if such data are relevant to an application.
Queue Data Node
The queue data node part of the queue contains the user data and a link set to point to the next node, if any.
- We can have a look at the above diagram to understand the queue data node structure.
- Nodes of a queue are stored in the dynamic memory of the computer.
- Nodes are inserted and deleted as per the user requirement.
Queue Algorithms
These are some basic algorithms to perform the Queue Operations in Data Structure. Although, any other operation can also be carried out and added to the data structure.
Empty Queue
This operation is used to check whether a queue is empty or full.
Empty Queue Algorithm
Algorithm Empty_Queue (queue)
1 if (queue count equal 0)
1 return true
2 else
1 return false
end Empty_Queue
- Empty queue operation returns true to the user in situations where the queue is empty.
- Otherwise, it returns false to the user in situations where the queue contains any data in it.
- In this way, we can test whether the queue is empty and we can also easily check the queue count using this operation.
Full Queue
Similarly as the stack, this operation is also used in the programming concept of data hiding.
For some languages it can be difficult to implement this operation.
Full Queue Algorithm
Algorithm Full_Queue (queue)
1 if (memory not available)
1 return true
2 else
1 return false
3 end if
end Full_Queue
- Here, the algorithm checks to see if a queue is full or not.
- The queue is said to be full if memory cannot be allocated for another node.
- queue is a metadata structure here.
- And after the algorithm finishes, it returns true if the queue is full and false if it is not full.
Destroy Queue
This operation deletes or destroys all the data that is present in the queue.
Destroy Queue Algorithm
Algorithm Destroy_Queue (queue)
1 if (queue not empty)
1 loop (queue not empty)
1 delete front node
2 end loop
2 end if
3 delete head structure
end Destroy_Queue
- Here, the above algorithm deletes all the data present in queue.
- queue is a metadata structure here.
- After the algorithm finishes, all the data elements are deleted from the queue.
Program example to demonstrate the implementation of Queue Operations
Code:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *front;
struct node *rear;
void insert_node();
void delete_node();
void print_list();
void main ()
{
int n;
while(n != 4)
{
printf("\nEnter 1 to insert an element\nEnter 2 to delete an element\nEnter 3 to print the queue\nEnter 4 to exit.\n");
printf("\nEnter a number corrosponding to the operations: ");
scanf("%d",& n);
switch(n)
{
case 1:
insert_node();
break;
case 2:
delete_node();
break;
case 3:
print_list();
break;
case 4:
exit(0);
break;
default:
printf("\nEnter a valid number.\n");
}
}
}
void insert_node()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOverflow State\n");
return;
}
else
{
printf("\nEnter a value.\n");
scanf("%d",&item);
ptr -> data = item;
if(front == NULL)
{
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
else
{
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
}
}
}
void delete_node ()
{
struct node *ptr;
if(front == NULL)
{
printf("\nUnderflow State\n");
return;
}
else
{
ptr = front;
front = front -> next;
free(ptr);
}
}
void print_list()
{
struct node *ptr;
ptr = front;
if(front == NULL)
{
printf("\nQueue emptied successfully.\n");
}
else
{ printf("\nQueue elements are:\n");
while(ptr != NULL)
{
printf("\n%d\n",ptr -> data);
ptr = ptr -> next;
}
}
}
In the next section of the tutorial, we will discuss the use of Tree in Data Structure which includes Binary Tree, Binary Search Tree, AVL Tree, B Tree and B+ Tree and some important tree operations as well as its implementation in programs that will be used thoroughly in this Data Structure tutorial.
