Lecture 15

Queues

A queue is a list in which all additions to the list are made at one end and all deletions are made at the other end. The first item put into the queue will always be the first one out, thus a queue is first-in-first-out data structure (FIFO). In order to implement a queue, we can use the stack pop function and another function to add an item to the end of the queue. To simplify adding an item to the end of a queue we will use another pointer that always holds the address of the last item - the tail pointer.

New definitions:

typedef struct _list_item {
  char name[64];
  struct _list_item *next;
} list_item;

typedef struct _list_info {
  list_item *head;
  list_item *tail;
} list_info;

typedef list_info *list;

typedef list_item *item_ptr;

A function to initialise the list will now be used.

list new_list()
{
  list l;
  l=newptr(list_info,1);
  l->head=NULL;
  l->tail=NULL;
  return l;
}

Pop will change slightly because it now has to keep a track of the tail pointer

void pop(list li, char *name) {

  item_ptr top=li->head;

  if(top != NULL) {
    li->head=top->next;
    strcpy(name,top -> name);
    free(top);
    if(li->head == NULL)
      li->tail=NULL;
  } else strcpy(name,"");

}

We now need a function to add to the end of the queue.

void add_to_end(list li, char *name) {
  item_ptr new_item;

  new_item = newptr(list_item, 1);
  if(new_item != NULL) {
    strcpy(new_item->name,name);
    new_item->next = NULL;
    if(li->tail==NULL)
       li->head=new_item;
    else
       li->tail->next=new_item;
    li->tail=new_item;
  }
}

#include <stdio.h>
#include <stdlib.h>

#define newptr(x,y) (x *)malloc((int)sizeof(x)*y)

typedef struct _queue_item {
  char name[64];
  struct _queue_item *next;
} queue_item;

typedef struct _queue_info {
  queue_item *head;
  queue_item *tail;
} queue_info;

typedef queue_info *queue;

typedef queue_item *item_ptr;

queue new_queue() {
  queue q;
  q=newptr(queue_info,1);
  q->head=NULL;
  q->tail=NULL;
  return q;
}

void pop(queue q, char *name) {

  item_ptr top=q->head;

  if(top != NULL) {
    q->head=top->next;
    strcpy(name,top -> name);
    free(top);
    if(q->head == NULL)
      q->tail=NULL;
  } else strcpy(name,"");
}

void add_to_end(queue q, char *name) {
  item_ptr new_item;

  new_item = newptr(queue_item, 1);
  if(new_item != NULL) {
    strcpy(new_item->name,name);
    new_item->next = NULL;
    if(q->tail==NULL)
       q->head=new_item;
    else
       q->tail->next=new_item;
    q->tail=new_item;
  }
}

void print_queue(queue q)  {
   item_ptr i=q->head;
   puts("The queue is:");
   while(i)  {
      printf("%s\n",i->name);
      i=i->next;
   }
}

void main() {
   queue q;
   int i;
   char name[64];

   q=new_queue();

   add_to_end(q,"Florence");
   add_to_end(q,"Dougal");
   add_to_end(q,"Dylan");
   add_to_end(q,"Zebedee");
   add_to_end(q,"Mr Rusty");
   add_to_end(q,"Mr McHenry");
   add_to_end(q,"Brian");

   print_queue(q);

   for(i=0;i<3;i++) {      
      pop(q,name);
      printf("%s popped\n",name);
   }
   print_queue(q);
}

Queues are useful in programs where one part of the program (the producer) produces data and another part (the consumer) uses that data. If the producer can produce data faster than the consumer can use it then a queue will be necessary to hold unconsumed data. When used in this way, a queue is often called a buffer because it shields one part of the program from the effects of another.

Implementing Stacks and Queues Using Arrays.

Pointers are not the only way of implementing stacks and queues. If the maximum size of the stack or queue is known and is reasonably small then an array can be used. An integer variable is used to to hold the index of the next element in the array to be used to hold a stack item. Here the bottom of the stack is s[0].

char *stack[N];

char *queue[N];

int top_of_stack=0;

int push_name(char *name) {
  if (top_of_stack==N)
    return 1;
  stack[top_of_stack]=malloc(strlen(name)+1);
  strcpy(stack[top_of_stack++],name);
  return 0;
}

char *pop_name() {
  if(top_of_stack==0)
    return "";
  return stack[--top_of_stack];
}

To push an item, the item is copied into the the array in the position given by the top of the stack. The top of the stack is then incremented.

To implement a queue using an array we use integers to hold the index of the head and the tail.

Note that the queue may 'wrap around' so that the head is before the tail in the array.

char *queue[N];

int head=0;
int tail=0;


int add_to_head(char *name) {
  if ((head+1)%N==tail)
    return 1;
  queue[head]=(char *)malloc(strlen(name)+1);
  strcpy(queue[head],name);
  head=(head+1)%N;
  return 0;
}

char *remove_from_tail() {
  if(head==tail)
    return NULL;
  tail=(tail+1)%N;
  return queue[(tail-1)%N];
}

Here is a program that implements both a stack and a queue using an array.

#include <stdio.h>
#include <stdlib.h>
#define N 100

char *queue[N];

int head=0;
int tail=0;


int add_to_head(char *name) {
  if ((head+1)%N==tail)
    return 1;
  queue[head]=(char *)malloc(strlen(name)+1);
  strcpy(queue[head],name);
  head=(head+1)%N;
  return 0;
}

int add_to_tail(char *name) {
  if ((head+1)%N==tail)
    return 1;
  tail=(tail-1)%N;
  queue[tail]=(char *)malloc(strlen(name)+1);
  strcpy(queue[tail],name);
  return 0;
}

char *remove_from_tail() {
  if(head==tail)
    return NULL;
  tail=(tail+1)%N;
  return queue[(tail-1)%N];
}

char *remove_from_head() {
  if(head==tail)
    return NULL;
  head=(head-1)%N;
  return queue[head];
}

void print() {
   int i;
   printf("The queue is:\n");
   for(i=(head-1)%N;i!=(tail-1)%N;i=(i-1)%N)
      printf("%s\n",queue[i]);
}

void main() {
   int i;
   char *name;

   add_to_head("Florence");
   add_to_head("Dougal");
   add_to_tail("Dylan");
   add_to_head("Zebedee");
   add_to_tail("Mr Rusty");
   add_to_head("Mr McHenry");
   add_to_head("Brian");

   print();

   for(i=0;i<2;i++) {      
      name=remove_from_head();
      if(name) {
         printf("%s removed from head\n",name);
         free(name);
      }
   }
   for(i=0;i<2;i++) {      
      name=remove_from_tail();
      if(name) {
         printf("%s removed from tail\n",name);
         free(name);
      }
   }

   print();
}