CS3343/3341
 Analysis of Algorithms 
Spring 2012
  Circular Queue  
(Array-Based)

Circular Array-Based Queue

This is the circular queue from your text. The text, as show below, presents an overview of a circular array-based queue, with a number of details left out.

This example also illustrates the text's notation, especially difficulties with its pseudocode and with convertion of their algorithms into running code in Java or C (or whatever). This is an extreme example of these difficulties. Most of the text's algorithms are more detailed than this one. This first illustration gives a nice picture of how the queue works and presents the main ideas. The second and third illustrations give pseudocode for the two important functions (in each case, click on the image for a larger view). The images are from your text, 3rd edition, pages 234-235.

Implementation of the Queue

See the page Computing: Information and Policies for information about implementing programs for this course.

The implementation of this queue in Java uses a separate class (of course) for the queue, in a separate file, though it doesn't have to be separate. For simplicity, this queue is not generic but just holds ints. However, it meets the criterion of allowing a completely different implementation as long as the same public functions are provided.

For the implementation in C, there are no classes, and the best way to implement an ADT is to use a separate file, with a header file (.h) providing the interface. If this is done properly, the code for the queue (or other ADT) itself could be completely replaced by an entirely different implementaion. This new queue could then be compiled and used by a calling program without recompiling that program.

I followed your text's algorithms and even much of its notation, even when that notation differed from Java or C standards. Notice that your book stores Q.length in the variable n, so I often used n where the book writes Q.length. Your book's queue Q has its index from 1 to n inclusive, while I used an array Q with index from 0 to n-1 inclusive. In both cases the array has n elements and the queue can hold n-1 elements. Your book writes Q.head and Q.tail, while I just use simple variables head and tail. In C these variables are private, stored in the separate file and not accessible from the outside.

I took the liberty of translating the book's code: 

if Q.tail == Q.length
     Q.tail = 1
else Q.tail = Q.tail + 1

into the following: 
tail = (tail + 1) % n;

and similarly for head. This does the same thing, only from 0 to n-1. With your text's arrays from 1 to n no similar trick works.

Circular Queue
JavaC
// Queue.java: simple circular queue of ints
public class Queue {
   private int n;
   private int Q[];
   private int head;
   private int tail;


 


   public Queue(int np) {
      n = np;
      Q = new int[n];
      head = 0;
      tail = 0;
   }
   public void enqueue(int x) {
      if (isFull()) {
         System.out.println("Overflow, x:" + x);
      }
      else {
         Q[tail] = x;
         tail = (tail + 1) % n;
      }
   }

   public int dequeue() {

      if (isEmpty()) {
         System.out.println("Underflow");
         return -1;
      }
      int x = Q[head];
      head = (head + 1) % n;
      return x;
   }

   public boolean isEmpty() {
      return head == tail;
   }

   public boolean isFull() {
      return head == (tail + 1) % n;
   }

   public int getHead() {
      if (!isEmpty())
         return Q[head];
      else return -1;
   }

   public void dumpQ(int i) {
      System.out.println("i:" + i +
        ", head:" + head + ", tail:" + tail +
        ", Q[head]:" + getHead());
   }
}

// QueueMain.java: test Queue.java
public class QueueMain {

   public static void main(String[] args) {
      Queue queue = new Queue(4);
      queue.dumpQ(1);
      queue.enqueue(101);queue.dumpQ(2);
      queue.enqueue(202);queue.dumpQ(3);
      queue.enqueue(303);queue.dumpQ(4);
      queue.enqueue(404);queue.dumpQ(5);
      queue.enqueue(505);queue.dumpQ(6);
      System.out.println(queue.dequeue());
         queue.dumpQ(7);
      System.out.println(queue.dequeue());
         queue.dumpQ(8);
      System.out.println(queue.dequeue());
         queue.dumpQ(9);
      System.out.println(queue.dequeue());
         queue.dumpQ(10);
      System.out.println(queue.dequeue());
         queue.dumpQ(11);
   }
}

// queue.h: header file
int dequeue();
void enqueue(int );
int isempty();
int isfull();
int gethead();
void dumpq();

// queue.c: queue definition
#include <stdio.h>
#include "queue.h"
#define n 4

int Q[n];
int head = 0;
int tail = 0;

void enqueue(int x) {
   if (isfull()) {
      printf("Overflow, x:%i\n", x);
   }
   else {
      Q[tail] = x;
      tail = (tail + 1) % n;
   }
}
   
int dequeue() {
   int x;
   if (isempty()) {
      printf("Underflow\n");
      return -1;
   }
   x = Q[head];
   head = (head + 1) % n;
   return x;
}
   
int isempty() {
   return head == tail;
}

int isfull() {
   return head == (tail + 1) % n;
}

int gethead() {
   if (!isempty())
      return Q[head];
   else return -1;
}

void dumpq(int i) {
   printf("i:%i, head:%i,", i, head);
   printf(" tail:%i, Q[head]:%i\n", 
      tail, gethead());
}

// queuemain.c: test queue
#include <stdio.h>
#include "queue.h"

int main() {

   dumpq(1);
   enqueue(101);dumpq(2);
   enqueue(202);dumpq(3);
   enqueue(303);dumpq(4);
   enqueue(404);dumpq(5);
   enqueue(505);dumpq(6);
   printf("%i\n", dequeue());
      dumpq(7);
   printf("%i\n", dequeue());
      dumpq(8);
   printf("%i\n", dequeue());
      dumpq(9);
   printf("%i\n", dequeue());
      dumpq(10);
   printf("%i\n", dequeue());
      dumpq(11);
}
Common Output
i:1, head:0, tail:0, Q[head]:-1
i:2, head:0, tail:1, Q[head]:101
i:3, head:0, tail:2, Q[head]:101
i:4, head:0, tail:3, Q[head]:101
Overflow, x:404
i:5, head:0, tail:3, Q[head]:101
Overflow, x:505
i:6, head:0, tail:3, Q[head]:101
101
i:7, head:1, tail:3, Q[head]:202
202
i:8, head:2, tail:3, Q[head]:303
303
i:9, head:3, tail:3, Q[head]:-1
Underflow
-1
i:10, head:3, tail:3, Q[head]:-1
Underflow
-1
i:11, head:3, tail:3, Q[head]:-1

Revision date: 2012-01-02. (Please use ISO 8601, the International Standard Date and Time Notation.)