Course Content

Other Courses

Tribhuvan university > CSIT - 2065 Syllabus > Data Structures and Algorithms > Old Questions > 2068

Data Structures and Algorithms - Old Questions

Syllabus Notes Old Questions Unit Wise Questions Question Bank

1. Define Queue as an ADT. Write a program for basic operations in Linear queue in array implementation.

10 marks | Asked in 2068

A Queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (the rear of the queue).

Queue follows First-In-First-Out (FIFO) methodology, i.e. the first element inserted into the queue is the first element to be removed.




Queue as an ADT

A queue q of type T is a finite sequence of elements with the operations:

  • MakeEmpty(q): To make q as an empty queue
  • IsEmpty(q): To check whether the queue q is empty. Return true if q is empty, return false otherwise.
  • IsFull(q): To check whether the queue q is full. Return true in q is full, return false otherwise.
  • Enqueue(q, x): To insert an item x at the rear of the queue, if and only if q is not full.
  • Dequeue(q): To delete an item from the front of the queue q. if and only if q is not empty.
  • Traverse (q): To read entire queue that is display the content of the queue.
Thus by using a queue we can perform above operations thus a queue acts as an ADT.

Program for basic operations in Linear queue

#include<stdio.h>

#include<conio.h>

#define SIZE 10

 

void enQueue(int);

void deQueue();

void display();

 

int queue[SIZE], front = -1, rear = -1;

 

void main()

{

   int value, choice;

   clrscr();

   while(1){

      printf("\\n\\n***** MENU *****\\n");

      printf("1. Insertion\\n2. Deletion\\n3. Display\\n4. Exit");

      printf("\\nEnter your choice: ");

      scanf("%d",&choice);

      switch(choice){

         case 1: printf("Enter the value to be insert: ");

                scanf("%d",&value);

                enQueue(value);

                break;

         case 2: deQueue();

                break;

         case 3: display();

                break;

         case 4: exit(0);

         default: printf("\\nWrong selection!!! Try again!!!");

      }

   }

}

void enQueue(int value){

   if(rear == SIZE-1)

      printf("\\nQueue is Full!!! Insertion is not possible!!!");

   else{

      if(front == -1)

         front = 0;

      rear++;

      queue[rear] = value;

      printf("\\nInsertion success!!!");

   }

}

void deQueue(){

   if(front == rear)

      printf("\\nQueue is Empty!!! Deletion is not possible!!!");

   else{

      printf("\\nDeleted : %d", queue[front]);

      front++;

      if(front == rear)

         front = rear = -1;

   }

}

void display(){

   if(rear == -1)

      printf("\\nQueue is Empty!!!");

   else{

      int i;

      printf("\\nQueue elements are:\\n");

      for(i=front; i<=rear; i++)

         printf("%d\\t",queue[i]);

   }

}