Data Structure - [Linear Queue Opeartions]

♠ Posted by Unknown in , at 04:05

Linear(Sequential) Queue Operations

This is a linear list DATA STRUCTURE used to represent a linear list and permits deletion to be performed at one end of the list and the insertion at the other end. The information in such a list is processed in the same order as it was received, that is on first-come-first-out (FIFO) basis. The Railway Reservation counter is an example of queue where the people collect their tickets on the first-come-first-serve (FIFS) basis. There are two types of operations possible on the linear queue.

 1.      Insertion (from rear side)
2.      Deletion (from front side)

A queue has two pointers front and rear, pointing to the front and rear elements of the queue, respectively. Consider a queue Q consisting of  n elements and an elements  Value, which we have no insert into the Q. The value NULL (0) of front pointer implies an empty queue and the MAXVALUE implies the queue is full.

ALGORITHM OF QUEUE:

1. Insert Operation:

Insert operation inserting the new value from the rear side (right hand side). The first value is arranged in the queue as a left most value (in queue as first value) and second value is also inserted on rear side and set behind first value. Thus, each new value is set behind the previous entered value.
                                    Step 1: [Check overflow condition]
                                          if rear >= size
                                          Output “Overflow” and return
                                    Step 2: [Increment rear pointer]
                                          Rear = rear + 1
                                    Step 3: [Insert an element]
                                          Q [rear] = value
                                    Step 4: [Set the front pointer]
                                          If front  = 0
                                          front = 1
                                    Step 5: return

2. Deletion Operation:

Deletion Operation is used to remove the values in the queue. It is works on the first-in-first-out (FIFO) basis, means, it is removed item from the front side (at the right hand side of the queue). This operation is removed first entered item after second entered item and so on in the queue.

                                    Step 1: [Check underflow condition]
                                          if front = 0
                                          Output “Underflow” and return
                                    Step 2: [Remove an element]
                                          Value = Q [front]
                                    Step 3: [Check for empty queue]
                                          If front = rear
                                          front = 0
                                          rear = 0
                                          else
                        front = front + 1
Example:

/*LINEAR QUEUE IMPLEMENTING POINTER AND STRUCUTRE.*/

#include<stdio.h>
#define SIZE 10
struct queue
{
 int item[SIZE];
}*q;

static int front = 0;
static int rear = 0;
main()
{
 int ans;
 do
 {
  clrscr();
  printf("1. Enter the New Element.\n");
  printf("2. Remove the Element.\n");
  printf("3. Display the Queue.\n");
  printf("4. Exit...\n");
  printf("Enter your choice :");
  scanf("%d",&ans);

  switch(ans)
  {
            case 1:
                        insert(&q);
                        break;
            case 2:
                        rem(&q);
                        break;
            case 3:
                        display(&q);
                        break;
            case 4:
                        break;
            default:
                        printf("You have entered wrong choice....");
  }
  }while(ans != 4);
 getch();
 return;
}

insert(struct queue *temp)
{
 int newitem;
 if(front >= SIZE)
 {
  printf("QUEUE IS FULL....");
  getch();
  return;
 }
 else
 {
  printf("Enter a New Value :");
  scanf("%d",&newitem);
  temp->item[++rear] = newitem;
  if(front <= 0)
            front = 1;
 }
 getch();
 return;
}

rem(struct queue *temp)
{
 int remitem;
 if (rear <= 0)
 {
  printf("THE QUEUE IS EMPTY....");
  getch();
  return;
 }
 else
 {
  temp->item[front++] = 0;

  if(front > rear)
  {
   front = 0;
   rear = 0;
  }
 }
getch();
return;
}

display(struct queue *temp)
{
 int fnt = 1;
 if(front <= 0 || rear <=0)
 {
  printf("THE QUEUE IS EMPLTY....");
  getch();
  return;
 }
 else
 {
   while(fnt <= rear)
   {
    printf("%d ",temp->item[fnt]);
    fnt++;
   }
 }
getch();
return;
}

0 comments:

Post a Comment