Expert: Narendra - 11/10/2005

Question
I have a program for my programming class that uses an array queue implementation.  I am supposed to rewrite all the functions to where it used the linked-list format and has a maximum of 6 nodes.  I've used linked-lists before and we were just introduced to queues.  We were never taught how to combine the two though, so I am lost.  I was wondering if you could just give me a basic outline of where to start.  I read above and I don't want you to do my homework for me.  I just want to know how I would go about this.  Also, please put your answer in the simplest terms possible.  I have written the code below that I am supposed to augment.  Thank you.

[code]
#include <stdio.h>
#define QSIZE 5

typedef struct{
    int elem[QSIZE];
    int front;
    int rear;
    int count;
}QType;
     
     /*    function prototypes   */
void initialize(QType *);
int empty(QType *);
int full(QType *);
int rem(QType *);
void insert(QType *, int);

main()
{
  QType Q;     /* queue declaration */
  int code, code1, i, n;
  int i1, i2;

  initialize(&Q);
  printf("initially: is empty?\n %d\n", empty(&Q));
  printf("is full?\n %d\n", full(&Q));

  printf("Enter 1 to continue, 0 to stop: ");
  scanf("%d", &code);
  while(code!=0)
  {  printf("Enter 2 to insert an item, 3 to remove an item: ");
     scanf("%d", &code1);
     switch(code1)
     {   case 2: printf("Enter an integer to be inserted: ");
                 scanf("%d", &i1);    
              /*   printf("case2: i1 is %d\n", i1); */
                 insert(&Q, i1);
                 break;
         case 3: i2=rem(&Q);
                 if(i2==0)
                   printf("Nothing is removed\n");
                 else
                   printf("%d is removed\n", i2);
                 break;
         default: printf("Wrong code\n");
     }
     printf("Currently in the queue:\n");
     if(Q.count==0)
        printf("Nothing\n");
     else
     {
     i=Q.front; n=0;
     do{
        printf("%d ", Q.elem[i]);
        n++;
        if(i>=QSIZE-1)
           i=0;
        else
           i++;
        }while(n<Q.count);   
    printf("\n");
    }
  printf("Enter 1 to continue, 0 to stop: ");
  scanf("%d", &code);
  }
  return 0;
}

void initialize(QType *q)
/* set head counter and tail counter to 0;   */
/* set counter of elements in the queue to 0 */
{   q->front=q->rear=0;
   q->count=0;
}

int empty(QType * q)
/* This function will determine if the queue is empty by        */
/* testing  the value of a counter of elements in the queue.    */
/* If the queue is empty, this function will print the message  */
/* "queue is empty" and return a value of 1.                    */
/* Otherwise, no message is displayed, and zero is returned.    */
{
  if (q->count == 0)
  { printf("QUEUE IS EMPTY\n");
    return 1;
  }
  else return 0;
}

int full(QType * q)
/* This function will determine if the queue is full by    */
/* testing the value of a counter of elements in the queue.*/
/* If the queue is full, prints "queue is full" and returns*/
/* a value of 1. Otherwise, does not print anything        */
/* and returns zero.                                       */
{
  if (q->count == QSIZE)
  {  printf("QUEUE IS FULL\n");
     return 1;
  }
  else return 0;
}

int rem(QType *q)
/* This function will return the item currently located  */
/* in the head of the queue. Then, the head counter      */
/* will be incremented.                                  */
{
  int temp;

  if (empty(q)) return 0;
  temp = q->elem[q->front];
  q->front=(q->front+1) % QSIZE;
  (q->count)--;
  return temp;
}

void insert(QType *q, int item)
/* The integer 'item' is inserted at the tail of the   */
/* queue and the tail counter is incremented.          */
{
  if (full(q)) return;
  q->elem[q->rear] = item;
/*   printf("in the insert: %d inserted\n", q->elem[q->rear]);*/
  q->rear = (q->rear + 1) % QSIZE;
  (q->count)++;
  return;
}
[/code]

Answer
The basic thing about Linked List is that, each node points to next node.
In programming terminology, this means every node holds the address of next node and the list ends when it encounters a NULL address.

So, you have to declare a structure which has one of the members as a pointer to itself, so that it can hold the address of the next node.
So, chnage your structure definition:
typedef struct{
   int elem[QSIZE];
   int front;
   int rear;
   int count;
}QType;
To:
typedef struct my_queue QType;
struct my_queue{
   int elem[QSIZE];
   QType* front;
   QType* rear;
   int count;
};

Next you need a front and tail which can be a global variables.
This is the starting point of the list and the last element of the list.

And when you add an element add at the tail.
When you delete remove from the front.

And adding and removing an element is to adjust the pointer, so that it points to the correct element afterwards.
And also free the element when you are deleting (so, you need to give its address to a temp variable before doing pointer adjustments)

And for Linked List you don't need to keep the limit of 5 or 6 elements. It has to grow dynamically.

Let me know if you want any other idea or if anything you didn't understand in my explanation.

Regards,
Narendra