Queue in C using Arrays

[vinitmittal2008]

Hello Friends...
i made this Queue Program in c and its working good.. But I want to make it circular Queue please give some ideas..

# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
# include <string.h>
# define QSIZE 5
typedef struct{
    int head,tail;
    char names[QSIZE][30];
}QUEUE;
void enqueue(char *);
char* dequeue();
void display();
int is_full();
int is_empty();
void init();
QUEUE *pq;
int main(){
    int choice;
    char str[30];
    QUEUE q;
    pq=&q;
    init();
    do{
     clrscr();
     printf("\n\n\t\tEnter your Choice:");
     printf("\n\t\t:1 for Add into the Queue.. ");
     printf("\n\t\t:2 for Delete from the Queue.. ");
     printf("\n\t\t:3 Display Elements of the Queue.. ");
     printf("\n\t\t:4 For Exit..\n\t\t\t :: ");
     scanf("%d",&choice);
     switch(choice){
       case 1: if(is_full())
		printf("\n\n\t\t Error: Queue Overflow..!!");
	       else{
		 printf("\n\n\t\t Enter a Name:");
		 fflush(stdin);
		 gets(str);
		 enqueue(str);
	       }
	       break;
       case 2: if(is_empty()){
		printf("\n\n\t\t Error: Queue UnderFlow..!!");
		init();
	       }
	       else
		printf("\n\n\t\t Deleted Queue Element is %s",dequeue());
	       break;
       case 3: if(is_empty())
		printf("\n\n\t\t Error: Queue is Empty..!!");
	       else
		display();
	       break;
       case 4: exit(0);
       default: printf("\n\n\t\t Plz press 1,2,3 or 4 key..");
     }
     while(!kbhit());
    }while(1);
    return 0;
}
void init(){
     pq->head = pq->tail = 0;
}
int is_full(){
    return pq->tail == QSIZE;
}
int is_empty(){
    if(pq->head == pq->tail){
     init();
     return 1;
    }
    else
     return 0;
}
void enqueue(char *p){
     strcpy(pq->names[(pq->tail)++],p);
     printf("\n\n\t\t Element Successfully Inserted");
}
char* dequeue(){
     return pq->names[(pq->head)++];
}
void display(){
     int i;
     for(i=pq->head;i<pq->tail;i++)
       printf("\n\t\t :%s",pq->names[i]);
}

[Ancient Dragon]

Sorry to say but that is not a linked list -- its just an array. Linked lists look somethig like this:

typedef struct _tagNode
{
   struct _tagNode* next;
   struct _tagNode* prev; // circular list
   char name[30]; // node data
} NODE;

NODE* head = 0;
NODE* tail = 0;

[vinitmittal2008]

Sorry to say but that is not a linked list -- its just an array. Linked lists look somethig like this:

typedef struct _tagNode
{
   struct _tagNode* next;
   struct _tagNode* prev; // circular list
   char name[30]; // node data
} NODE;

NODE* head = 0;
NODE* tail = 0;

This program is implementetion of a queue of array containing names.. i want to make a circular Queue of array.

[Ancient Dragon]

It would be simpler to use an int as the current index into the array instead of a pointer. When the index value reaches the end of the queue then just reset it back to the beginning.

void enqueue(char *p){
    strcpy(pq->names[(pq->tail)++],p);
    if( pq->tail == &names[QSIZE] )
        pq->tail = &names[0];  
     printf("\n\n\t\t Element Successfully Inserted");
}

[nezachem]

In the circular queue you may not rely on relative head and tail positions. You must keep track of the number of elements manually. Extend the struct queue with an int count initialized to 0. Increment it on every enqueue and decrement on every dequeue operations. Rewrite is_empty and is_full to inspect the count and act accordingly.

Of course, upon reaching the end of array, head and tail shall go back to 0.

PS: I'd recommend to test the queue state inside enqueue and dequeue.

[vinitmittal2008]

In the circular queue you may not rely on relative head and tail positions. You must keep track of the number of elements manually. Extend the struct queue with an int count initialized to 0. Increment it on every enqueue and decrement on every dequeue operations. Rewrite is_empty and is_full to inspect the count and act accordingly.

Of course, upon reaching the end of array, head and tail shall go back to 0.

PS: I'd recommend to test the queue state inside enqueue and dequeue.

Thanks Buddy.... Your suggestion was really helpful to me...

[vinitmittal2008]

Here is My Circular Queue of Arrays Program.. and its working fine...

/* Implementation of a circular queue of Array containg names.. */
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
# include <string.h>
# define QSIZE 5
typedef struct{
    int count;
    int head,tail;
    char names[QSIZE][30];
}QUEUE;
char* enqueue(char *);
char* dequeue();
void display();
void init();
QUEUE *pq;
int main(){
    int choice;
    char str[30];
    QUEUE q;
    pq=&q;
    init();
    do{
     clrscr();
     printf("\n\n\t\tEnter your Choice:");
     printf("\n\t\t:1 for Add into the Queue.. ");
     printf("\n\t\t:2 for Delete from the Queue.. ");
     printf("\n\t\t:3 Display Elements of the Queue.. ");
     printf("\n\t\t:4 For Exit..\n\t\t\t :: ");
     scanf("%d",&choice);
     switch(choice){
       case 1:
	       printf("\n\n\t\t Enter a Name:");
	       fflush(stdin);
	       gets(str);
	       puts(enqueue(str));
	       break;
       case 2:
	       puts(dequeue());
	       break;
       case 3:
	       display();
	       break;
       case 4: exit(0);
       default: printf("\n\n\t\t Plz press 1,2,3 or 4 key..");
     }
     printf("\n\n\n\t Press Any Key to continue...");
     fflush(stdin);
     while(!kbhit());
    }while(1);
    return 0;
}
void init(){
     pq->head = pq->tail = pq->count= 0;
}
char* enqueue(char *p){
     if(pq->count==QSIZE)
       return "\n\n\t\t Error: Queue Overflow..!!";
     pq->tail= (pq->tail)%QSIZE;
     strcpy(pq->names[(pq->tail)++],p);
     pq->count++;
     return "\n\n\t\t Element Successfully Inserted";
}
char* dequeue(){
     if(pq->count==0)
       return "\n\n\t\t Error: Queue Underflow..!!";
     pq->head= (pq->head)%QSIZE;
     pq->count--;
     printf("\n\n\t\t Deleted Queue Element is :");
     return pq->names[(pq->head)++];
}
void display(){
     int i=pq->head;
     int x=0;
     if(pq->count==0)
      printf("\n\n\t Queue is Empty..");
     else{
      while(x<pq->count){
	if(i==QSIZE)
	 i%=QSIZE;
	printf("\n\t\t :%s",pq->names[i]);
	i++;
	x++;
      }
    }
}