Queue in C
In C, a queue is essentially a linear data structure used to store and handle data components. The concept used in this First-In-First-Out (FIFO). The first element added to an array is the first element withdrawn from the array in queues.
Consider a scenario of booking a bus ticket or train ticket. The style of a C programming queue is followed here. The tickets are distributed on a first-come, first-served basis, which implies that the first person to arrive receives the tickets.
Both ends of the queue are open. One end is designated for data insertion and the other for data deletion. Enqueue is the process of addition of an element to a queue, whereas Dequeue is the process of deleting of an element from a queue.
enqueue() is the operation that specifies adding an element to the queue.
dequeue() is the operation that specifies deleting an element to the queue.
Features of Queue:
- A queue, like a stack, is an ordered collection of equivalent data types.
- FIFO (First - In- First - Out) is the main structure that describes a Queue.
- When a new element is added to the Queue, all elements added before the new element must be removed in order to remove the new element.
- The peek() function is often used to return the first element's value without dequeuing it.
Working of Queue:
1. Insertion of an Element:
- The linked list, an array or a stack can be used to implement a queue. Using an Array is the simplest approach to constructing a queue.
- The front and rear of the queue initially point to the first index of the array (the index of the array starts at 0).
- When we addition of elements to the queue happens, the rear index advances, always pointing to the spot where the following element will be inserted, while the front element remains at the initial index.
2. Deletion of an Element:
- There are two methods for removing an element from the Queue.
- The first method involves removing the element in front and then shifting all of the remaining elements in front one by one.
- In approach number two, we remove the element from the rear and move it to the front.
- When we remove the first element, we incur the overhead of moving the elements forward in one position.
- In the second method, there is no such overhead, but every time we move forward one position after removing the initial piece, the size of the Queue is reduced by one space.
3. Implementation of Queue:
In order to implement a Queue in a sequential representation we need the following.
- Array
- Two index variables front and rear
Where front contains index of front element.
And rear contains index of last element.
When queue is empty both the variables i.e., front and rear contains -1.
Initially, declare
#define MAX5 and q[MAX] which are queues.
- When a queue is empty, front=-1 and rear=-1.
- Full condition i.e., when a queue is full then rear==MAX-1.
- Empty condition i.e., no element is found then r==-1.
- Single element condition front==rear.
- To insert a new Element in a Queue increment rear i.e., r=r+1.
- To delete Single Element in a Queue then front=rear=-1.
- To delete an element from a queue when it has more than one element then increment front i.e., front=front+1.
Program to implement Queue:
#include <stdio.h> #define MAX 5 void insert(int); int del(); void display(); int q[MAX],front=-1,rare=-1; void main() { int x,ch; do { printf("Enter your choice\n1.Insert\n2.Delete\n3.Display\n4.Exit\n"); scanf("%d",&ch); switch(ch) { case 1: printf("Enter the element:"); scanf("%d",&x); insert(x); break; case 2: x=del(); if(x==-1) printf("Deletion is not possible"); else printf("Delete=%d",x); break; case 3: display(); break; } }while(ch<4); } // Inserting the elements into the QUEUE void insert(int x) { if(rare==MAX-1) { printf("Insertion is not possible"); } else { rare=rare+1; q[rare]=x; if(front==-1) front=0; } } // Deleting the elements fro QUEUE int del() { int x; if(rare==-1) { return -1; } else { x=q[front]; if(front==rare) { front=rare=-1; } else { front=front+1; } return x; } } // Displaying the elements present in the QUEUE void display() { int i; if(rare==-1) { printf("Queue is Empty"); } else { printf("Queue elements from front to rare : "); for(i=front;i<=rare;i++) printf("%d\t",q[i]); } }
OUTPUT: