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:

A function to initialise the list will now be used. Pop will change slightly because it now has to keep a track of the tail pointer We now need a function to add to the end of the queue.



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.