Question

Write a C program: Implement the abstract data type (ADT) queue (FIFO) of strings. ADT has the following methods: clear – clears the queue; is_empty – returns 1 if the queue is empty, otherwise 0; is_full – returns 1 if the queue is full, otherwise 0; add – adds a new string at the end of the queue; remove – removes the string from the front of the queue. Use ADT queue to solve the following problems: • Write an interactive program that adds and removes elements from the queue. • Use ADT queue to find the way out from a maze. The maze is an 8 x 8, 2 D array of characters, ‘*’ indicating a wall. The program reads the starting point from which the way out is found. This kind of search is called breadth-first-search.

Input File:

********
* * *** 
**  *  *
** *** *
*   * **
*   *  *
*** * **
*** ****

Answer 1

   #include<stdio.h>

   #include<stdlib.h>

   #define MAXIMUM 100

   #define intial 1

   #define waitng 2

   #define visiited 3

   int n;

   int adj[MAXIMUM][MAXIMUM];

   int state[MAXIMUM];

   void create_Graph();

   void breadth_First_Search_Traversal();

   void breadth_First_Search(int v);

   int que[MAXIMUM], frnt = -1,rearr = -1;

   void insert-Queue(int vertex);

   int delete_Queue();

   int is_Empty_Queue();

   int main()

   {

   create_Graph();

   breadth_First_Search_Traversal();

   return 0;

   }

   void breadth_First_Search_Traversal()

   {

   int h;

   for(h=0; h<n; h++)

   state[h] = intial;

   printf("Enter Start Vertex for breadth_First_Search: \n");

   scanf("%d", &h);

   breadth_First_Search(h);

   }

   void breadth_First_Search(int h)

   {

   int i;

   insert-Queue(h);

   state[h] = waitng;

   while(!is_Empty_Queue())

   {

   h= delete_Queue( );

   printf("%d ",h);

   state[h] = visiited;

   for(i=0; i<n; i++)

   {

   if(adj[h][i] == 1 && state[i] == intial)

   {

   insert-Queue(i);

   state[i] = waitng;

   }

   }

   }

   printf("\n");

   }

   void insert-Queue(int vertex)

   {

   if(rearr == MAXIMUM-1)

   printf("Queue Overflow\n");

   else

   {

   if(frnt == -1)

   frnt = 0;

   rearr = rearr+1;

   que[rearr] = vertex ;

   }

   }

   int is_Empty_Queue()

   {

   if(frnt == -1 || frnt > rearr)

   return 1;

   else

   return 0;

   }

   int delete_Queue()

   {

   int deleteitem;

   if(frnt == -1 || frnt > rearr)

   {

   printf("Queue Underflow\n");

   exit(1);

   }

   deleteitem = que[frnt];

   frnt = frnt+1;

   return deleteitem;

   }

   void create_Graph()

   {

   int cnt,max_Edge,orgn,destn;

   printf("Enter number of vertices : ");

   scanf("%d",&n);

   max_Edge = n*(n-1);

   for(cnt=1; cnt<=max_Edge; cnt++)

   {

   printf("Enter edge %d( -1 -1 to quit ) : ",cnt);

   scanf("%d %d",&orgn,&destn);

   if((orgn == -1) && (destn == -1))

   break;

   if(orgn>=n || destn>=n || orgn<0 || destn<0)

   {

   printf("Invalid edge!\n");

   cnt--;

   }

   else

   {

   adj[orgn][destn] = 1;

   }

   }

   }