LINEAR DATA STRUCTURE : QUEUES.

 LEARNING OBJECTIVE: 

A queue is an important data structure that is extensively used in computer applications. In this blog, we will study the operations that can be performed on a queue. The article will also illustrate different types of queues like multiple queues, double-ended queues, circular queues, and priority queues. The article also lists some real-world applications of queues.

INTRODUCTION:

Let us explain the concept of queues using the analogies given below

  • People moving on an escalator. The people who got on the escalator first will be the first ones to step out of it.
  • People waiting for the bus. the first person standing in the line will be the first one to get on the bus.
In all these examples, we see that element at the first position is served first. The same is the case with queue data structure a queue is a FIFO(First-In-First-Out) data structure in which the element that is inserted first is the first one to be taken out. The element in a queue is added at one end called the REAR  and removed from the other end called the FRONT.
Queues are implemented either using arrays or linked lists.

ARRAY REPRESENTATION OF QUEUES

                          
savage coder


Queues can be easily represented using linear arrays.

Algorithm to insert an element into the queue :

STEP 1: IF REAR = MAX-1                                      
                   Write OVERFLOW                                   
                    Go to step 4                                                              
               [End of IF]                                                                    
STEP 2: IF FRONT = -1 and REAR = -1                                     
                   SET FRONT = REAR = 0                                          
              ELSE                                                                                
                   SET REAR = REAR+1                                                 
                [End of IF]                                                      
STEP 3: SET QUEUE [REAR] = NUM                       
STEP 4: EXIT                                                                              

 In step 1, we first check the overflow conditions
 In step 2, we check queue is empty, In case the queue is empty, then both FRONT and
 REAR is set to zero so that the new value can be stored in the 0th place.If the queue already  has some values then REAR is increment so that it points to the next location in the array
 In step 3, the value is stored in the queue at the location pointed by REAR

Algorithm to delete an element from the queue:

STEP 1: IF FRONT = -1 OR FRONT > REAR            
                   Write UNDERFLOW                                               
              ELSE                                                                              
                    SET VAL = QUEUE[FRONT]
                    SET FRONT = FRONT + 1
               [END OF IF]
STEP 2: EXIT

In step 1,we check for underflow condition  an underflow occurs if  FRONT= -1 or FRONT >REAR 

QUEUE ADT:
DATA: It is a finite sequence of elements of a particular type. (arrays / linked list)
OPERATIONS:
1. Initialize a queue.
2. check whether the queue is empty.
3. check whether the queue is full.
4. Insert from the rear end if a queue is not full. This operation is called Insert.
5. Delete a element from the front of queue if it is not empty. This operation is called Delete.

Implementation of queue using array

#include<stdio.h>
#include<unistd.h>
#define MAX 5

struct Queue
{
int data[MAX];
int front,rear;
};

void initialize(struct Queue *q)
{
q->front=q->rear=-1;
}

int isFull(struct Queue *q)
{
return (q->rear==MAX-1)?1:0;
}

int isEmpty(struct Queue *q)
{
return (q->rear==-1)?1:0;
}

int insert(struct Queue *q,int d)       //enqueue
{
if(isFull(q))
return 0;
q->data[++q->rear]=d;
if(q->front==-1)            //check for first insertion
q->front=0;	
return 1;
}


void display(struct Queue *q)
{
int i;
if(isEmpty(q))
printf("\n\tQueue is Empty->");
else
{
printf("\nQueue Contents ->->\n");
printf("Queue Size : %d\nFront = %d\nRear = %d\n",MAX,q->front,q->rear);
for(i=q->front;i<=q->rear;i++)
{
printf("%d\n",q->data[i]);
}
}
}


int delete(struct Queue *q)         //dequeue
{
int d;
if(isEmpty(q))
printf("\nQueue is Empty.");
else
{
d=q->data[q->front];
if(q->front==q->rear)
q->front=q->rear=-1;
else
q->front++;
return d;
}
}

int search(struct Queue *q,int k)
{
int i;
for(i=q->front;i<=q->rear;i++)
if(q->data[i]==k)
return i;
return -1;
}


int main()
{
int ch,d;
struct Queue q;
initialize(&q);
while(1)
{

printf("\n\t\t\tMENU\n1. Insert.\n2. Delete.\n3. Search.");
printf("\n4. Display.\n5. Exit.");
printf("\n\tEnter your choice :: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nEnter Data to be Inserted : ");
scanf("%d",&d);
d=insert(&q,d);
if(d==0)
printf("Queue is full...");
else
printf("Insertion is done successfully...");
break;
case 2:
if(isEmpty(&q))
printf("\nQueue is empty...");
else
printf("\nDeleted element is %d",delete(&q));
break;
case 3:
printf("\nEnter Data to be Searched : ");
scanf("%d",&d);
d=search(&q,d);
if(d==-1)
printf("\nKey is not found..");
else
printf("\nKey is found at location %d..",d);
break;
case 4:
display(&q);
break;
case 5:
exit(0);
default:
printf("\n\tPlease enter correct choice->->->->");
}}}

Output

                          MENU
1.  Insert.
2.  Delete.
3.  Search. 
4.  Display.
5.  Exit.
            Enter your choice:: 1
Enter data to be inserted: 4
Insertion is done successfully...

Note: The process of inserting an element in the queue is known as en queue, and the process of deleting an element from the queue is known as dequeue.

Types of Queues
  1. Circular queue
  2. deque.
  3. Priority queue.
  4. Multiple queues.
we will discuss each of these queues in detail in the next blog.

Application of queues 

  • Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
  • Queues are used to transfer data asynchronously between two processors e.g, pipes, file IO, sockets.
  • Queues are used as buffers on MP3 players and portable CD players, iPod playlist.

Data Structure Interview Questions on Queues

  1. What is a Queue Data Structure?

  2.  List some applications of queue Data Structure?

  3.  What is a Dequeue?

  4.  What operations can be performed on queues?


NEXT CHAPTER-->




Comments

Post a Comment

Popular posts from this blog

LINEAR DATA STRUCTURE : STACK

Image
 What is a stack? A stack is a linear data structure in which the addition and deletion of data are done from the same end. This end is often referred to as the top of a stack. Last-In-First-Out (LIFO) structure. STACK ADT: DATA: It is a finite sequence of elements of a particular type. (arrays / linked list) OPERATIONS: 1. Initialize a stack. 2. check whether the stack is empty. 3. check whether the stack is full. 4. Insert at the top of stack if a stack is not full. This operation is called Push. 5. Delete a element from the top of stack if it is not empty. This operation is called Pop. 6. Retrieve an element from the top of stack. This operation is called Peek. STACK OPERATION Implementation of Stack: 1. Using Array 2. Using Linked List. Message Passing Methods in C: 1. Pass by Value / Call by Value. 2. Pass by Address / Call by Address. Implementation of a stack using arrays #include<stdio.h>   //pre-processor directive #include<unistd.h> #define MAX 5 str...
Read more