Do you think IIT Guwahati certified course can help you in your career?
Introduction
Welcome back, ninjas! Do you know the differences between simple queues and circular queues? If you do not know, then this article will give you complete knowledge regarding simple and circular queues.
The article covers the concept of queues and their types, along with the differences between Simple Queues and Circular queues. So let's start learning about it.
What is a Queue?
A queue is a data structure whose both ends are in use. The queue size increases when inserting data items from one end, and the size shrinks when the data items are removed from the other. Hence, the last element waits in the queue until all the elements coming before it are not removed. In daily life, you can see several examples of the queue, like people standing in line to buy movie tickets or ants walking in a queue. "First in, first out" is the FIFO structure of a queue. A queue follows the First in, first out (FIFO) structure.
To effectively manage a queue, the following functions are required:
clear():It removes all the entities from the queue and empties the whole queue.
isEmpty(): checks if the queue is empty or not.
enqueue(value): Adds the element 'value' to the one end of the queue.
dequeue(): It removes the first item from the queue.
peek(): It returns the first entity present inside the queue.
Applications of Queue
The various applications of the queue are as follows:
The idea of queues is used in designing all customer service centers, including those that handle train reservations.
In a computer system, CPU scheduling is the best example of a queue data structure. All the processes that need CPU for their execution are inserted inside the queue, and the request is fulfilled by taking the process present at the front of the queue.
Round robin scheduling technique is implemented using the queue.
Asynchronous data transfer uses queues. Here, "asynchronous" refers to a process in which two processes do not transfer data at the same rate. IO buffers, pipes, file IO, etc. are a few examples.
Circular queues are used in computer-controlled traffic light systems to regularly (at set intervals) turn on required lights individually.
Types of Queue
There are several queue kinds, and they can be categorized using a number of different factors. The following are some of the most typical queues:
Simple Queue
It is an introductory level queue where insertion occurs at the rear end and deletion at the front. It is the most common queue type which is experienced by you in daily life, like people standing at a bus stop. This may be implemented using linear arrays or linked lists in the computer system. In simple queue time complexity of enqueue(), dequeue(), and peek() is O(1) and space complexity for each operation is O(1).
The implementation of a Simple queue using a linked list in C language is shown below:
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
};
struct Node *f = NULL;
struct Node *r = NULL;
void linkedListTraversal(struct Node *ptr) //To traverse the linked list
{
printf("Printing the elements of this linked list\n");
while (ptr != NULL)
{
printf("Element: %d\n", ptr->data);
ptr = ptr->next;
}
}
void enqueue(int val) // To insert a value in queue
{
struct Node *n = (struct Node *) malloc(sizeof(struct Node));
if(n==NULL){
printf("Queue is Full");
}
else{
n->data = val;
n->next = NULL;
if(f==NULL){
f=r=n;
}
else{
r->next = n;
r=n;
}
}
}
int dequeue() // To delete a value from queue
{
int val = -1;
struct Node *ptr = f;
if(f==NULL){
printf("Queue is Empty\n");
}
else{
f = f->next;
val = ptr->data;
free(ptr);
}
return val;
}
int main()
{
printf("Dequeuing element %d\n", dequeue());
enqueue(34);
enqueue(4);
enqueue(7);
enqueue(17);
//Till now 4 values are inserted in the queue
printf("Dequeuing element %d\n", dequeue());
linkedListTraversal(f);
return 0;
}
Queue is Empty
Dequeuing element -1
Dequeuing element 34
Printing the elements of this linked list
Element: 4
Element: 7
Element: 17
The time complexity of various operations of a simple queue shown in the above code is;
enqueue: O(1)
dequeue: O(1)
peek: O(1)
linkedListTraversal: O(n)
Apart from that, the space complexity of a simple queue is O(n).
Circular Queue
The queue's linear structure always considers the items' forward motion. Every node in the circular queue connects to the next one, and finally, the last node connects to the first, forming a circular structure. It is also called a "Ring Buffer" because each end is connected.
Some major applications of a circular queue are; Memory management and CPU planning.
The linked list implementation of the circular queue in C language is given below:
#include <stdio.h>
#include <stdlib.h>
struct node
{
int val;
struct node *next;
};
struct node *front=NULL;
struct node *rear=NULL;
void display() // To print all the elements present inside queue
{
struct node *temp_node;
temp_node=front;
printf("\n The elements present in the Queue are : ");
if((front==NULL) && (rear==NULL))
{
printf("Queue is empty");
}
else
{
while(temp_node->next!=front)
{
printf("%d,", temp_node->val);
temp_node=temp_node->next;
}
printf("%d", temp_node->val);
}
}
void enqueue(int x) //To insert elements inside the circular queue
{
struct node *newnode;
newnode=(struct node *)malloc(sizeof(struct node));
newnode->val=x;
newnode->next=NULL;
if(rear==NULL)
{
front=rear=newnode;
rear->next=front;
}
else
{
rear->next=newnode;
rear=newnode;
rear->next=front;
}
}
int peek() //To find the front element of circular queue
{
if((front==NULL) &&(rear==NULL))
{
printf("\nQueue is empty");
}
else
{
printf("\nThe front element is %d", front->val);
}
}
void dequeue() //To delete an element from the queue
{
struct node *temp_node;
temp_node=front;
if((front==NULL)&&(rear==NULL))
{
printf("\nQueue is empty");
}
else if(front==rear)
{
front=rear=NULL;
printf("\n Element Deleted Successfully");
}
else
{
front=front->next;
rear->next=front;
printf("\n Element Deleted Successfully");
}
}
void main()
{
enqueue(57);
enqueue(70);
enqueue(93);
enqueue(13);
display();
peek();
dequeue();
}
Output:
The elements present in the Queue are: 57,70,93,13
The front element is 57
Element Deleted Successfully
The time complexity of various operations of a circular queue shown in the above code is:
enqueue: O(1)
dequeue: O(1)
peek: O(1)
linkedListTraversal: O(n)
In addition, a circular queue has O(n) space complexity.
Double-Ended Queue
Double-ended queues are the ones that have two pointers in every node's structure: next and prev. The next pointer points to the memory location of the next immediate node, while the prev pointer points to the node just preceding it.
The Double Ended queue or Deque has two types:
Deque with restrictions on input: It is a Deque with input restrictions that only enables insertion at one end of the list but allows deletion at both ends.
Deque with restrictions on output: It is a Deque that permits insertion at both ends of the list, but only one end is used for deletion.
Priority Queue
It is another variety of queues where the nodes are arranged according to priority. Each element is given a priority value. The sequence in which elements are removed and processed is determined by the following rules:
The element with the lowest priority would be deleted first from the queue.
Insertion takes place in the sequence in which the nodes arrive.
Some use cases of the Priority queue in computer systems are The Dijkstra shortest path algorithm, Data Compression Techniques, and Prim's Algorithm.
Difference Between Simple Queue and Circular Queue
S.No.
Simple Queue
Circular Queue
1
The data is stored in sequential order, one after the other.
The last item is connected to the first and thus forms a circle.
2
In a simple queue, the elements are inserted only at the rear position and removed from the front.
The elements can be inserted and deleted from any position in a circular queue.
3
If the rear approaches the end of the array, it could result in an overflow.
The rear prevents overflow by wrapping around the beginning of the array.
4
A simple queue is not much memory efficient because it can’t reuse the empty space produced due to dequeued elements.
A circular queue is more memory efficient because, in array implementation, it reuses the empty space produced due to dequeued elements.
5
It follows the FIFO principle while performing the tasks.
It follows no specific order for execution.
6
It is easier to access the peek value of the simple queue because the front of the queue is always fixed.
The circular queue makes it challenging to retrieve the peek value because the queue's front and back are not fixed.
7
Effective in applications where overflow is not a problem.
Suitable for situations where memory utilization efficiency is essential.
8
It is used in CPU Scheduling.
It is used in Computer Controlled Traffic Light Systems.
What is a real-life example to see the application of a circular queue?
In real life, a traffic light system is the best example of a circular queue. The red, green, and yellow colors are highlighted on the screen in cyclic order at fixed intervals.
Which is better for implementing a queue, an array, or a linked list?
It depends on the needs of a coder. Suppose you do not have a fixed number of elements to be inserted in the queue. Then linked list is the best option because it simply connects all the free memory blocks to store the data until there is any buffer overflow.
What is the time complexity of implementing a priority queue?
A priority queue is a special type of queue that stores items by giving them a priority. It uses a heap data Structure for the implementation. The time complexity of inserting an element is O(log n), deleting an element is O(log n), and finding the peek element is O(1).
What makes a queue different from a stack?
The main difference between the two types of data structures is that queue utilizes a FIFO (First In First Out) data structure while the stack uses a LIFO (Last In First Out) data structure.
Conclusion
This blog provides knowledge on several topics like what a queue is, applications of the queue, types of queues, and the difference between a simple queue and a circular queue in detail, along with some frequently asked questions related to it.
We hope that this article was beneficial to you. Coding Ninjas provides excellent material for gate preparation, so you can refer to the Queue Gate Questions list to get an idea of the questions about queues.
24+ registered 
