Queues



Queue is defined as an ordered collection of items from which, the items mat be deleted at one end called FRONT end and into which the items may be inserted at the other end called REAR end
Follows LILO or FIFO

Queues as broadly classified into four types:
  1. Linear
  2. Circular
  3. Priority
    1. Ascending
    2. Descending
  4. Double ended
    1. Input-restricted
    2. Output-restricted
It can be implemented with abstract functions like :
  1. Insertion
  2. Deletion
  3. Isempty
  4. Isfull
  5. Display

It also has conditions such as overflow for when the queue is full and
underflow for when the queue is empty

Below is an implementation of queues using arrays 
    

#include<stdio.h>

#define MAX 3

// this code is not upto the mark , but does a little work [doesn't handle all edge cases]
int q[MAX],front=0,rear=-1;

void display(){
printf("\nUpdated list: ");
for(int i=front;i<= rear;i++){
printf("%d ",q[i]);
}
}

void insert(){
char ch;
do{
if(rear==MAX-1){
printf("\nOverflow condition!");
return;
}
printf("\nEnter the element to be inserted: ");
int item;
scanf("%d",&item);
q[++rear]=item;// array bounds aren't checked at runtime!
// therefore you can keep inserting more than MAX elements
// but it might crash later on
printf("\nElement is successfully inserted!");
printf("\nDo you want to insert more?[y/n]: ");
scanf(" %c",&ch);
}while(ch=='y');
display();
}


void delete(){
char ch;
do{
if(rear==front-1){
printf("\nUnderflow condition!");
return;
}
front++;
printf("\nElement deleted!");
printf("\nDo you want to delete another element?[y/n]");
scanf(" %c",&ch);
}while(ch=='y');
display();
}

int main(){
insert();
delete();
display();
}


Now coming for the circular Queue.
It is where you can keep inserting elements even after reaching the end - If there is space available in the list
That is when there is atleast some space available [even a single element of space] within the range of size of queue, insert method can function 
    

#include<stdio.h>

#define MAX 3

int q[MAX],front=-1,rear=1;

void display(){
if(front=-1){
printf("Empty");
}else if(front<=rear){
for(int i=front;i<=rear;i++){
printf("%d ",q[i]);
}
}
else{
for(int i=front;i<MAX;i++){
printf("%d ",q[i]);
}
for(int i=0;i<=rear;i++){
printf("%d ",q[i]);
}
}
}

void insert(){
int item;
if((front==0 && rear==MAX-1) || rear == front-1){
printf("\nOverflow Condition!");
return;
}
rear=((rear+1)%MAX);
printf("\nEnter the element to insert");
q[rear]=item;
display();
}

void delete(){
if(front=-1){
printf("\nUnderflow Condition!");
}
printf("\nDeleted element is: %d",q[front]);
if(front==rear){
front=rear=-1;
}else{
front=((front+1)%MAX);
}
display();
}

int main(){
char ch;
printf("\nImplemting Circular Queue!");
while(1){
printf("\nEnter choice\n1.Insert\t2.Delete\t3.Display\t4.Exit");
scanf(" %c",&ch);
switch(ch){
case'1':insert();break;
case'2':delete();break;
case'3':display();break;
case'4':return 0;
default:printf("\nInvalid Option!");
}
}
}

Applications

  1. Simulation of real life problems
  2. Time-sharing systems
  3. OS [circular]
  4. Read/Write to disk [circular]
  5. Real-time apps for buffering I/O requests [circular]
  6. nw comm systems
Next