A queue

Queue in Java

A queue program in Java: This program gives an array-based circular queue. The index variables rp ("rear pointer") and fp ("front pointer") are confusing and require explanation. Remember that as you move along the queue using increasing index values, the next index beyond qMaxSize -1 is index 0. So rp always gives the index of the current rear of the queue, and fp always gives the index one less than the current front of the queue. Thus fp gives an index one less than where to find the next value to delete. The index rp gives an index one less than where to place next value when inserting. One has fp == rp in case the queue is full and also in case the queue in empty. (These ways that this queue uses the values rp and fp are just arbitrary choices. The queue could have been set up in a different way.)

The source below can be found in: Queue.java and QueueTest.java.

Queue Implementation: Queue.java Test the Queue: QueueTest.java

Queue Implementation: `Queue.java`	Test the Queue: `QueueTest.java`
// Queue.java: queue implementation public class Queue { private int qMaxSize;// max queue size private int fp = 0; // front pointer private int rp = 0; // rear pointer private int qs = 0; // size of queue private char[] q; // actual queue public Queue(int size) { qMaxSize = size; fp = 0; rp = 0; qs = 0; q = new char[qMaxSize]; } public char delete() { if (!emptyq()) { qs--; fp = (fp + 1)%qMaxSize; return q[fp]; } else { System.err.println("Underflow"); return '?'; } } public void insert(char c) { if (!fullq()) { qs++; rp = (rp + 1)%qMaxSize; q[rp] = c; } else System.err.println("Overflow\n"); } public boolean emptyq() { return qs == 0; } public boolean fullq() { return qs == qMaxSize; } public void printq() { System.out.print("Size: " + qs + ", rp: " + rp + ", fp: " + fp + ", q: "); for (int i = 0; i < qMaxSize; i++) System.out.print("q[" + i + "]=" + q[i] + "; "); System.out.println(); } }	// QueueTest.java: test the queue import java.io.*; public class QueueTest { // in: reader for reading input data private static Reader in = new InputStreamReader(System.in); private static char getNextChar() { char ch = ' '; try { ch = (char)in.read(); } catch (Exception exception) { System.err.println("Read Error"); ch = ' '; } return ch; } public static void main(String[] args) { Queue queue = new Queue(4); // 10 chars char ch; while ((ch = getNextChar()) != 'q') { switch (ch) { case 'i': ch = getNextChar(); queue.insert(ch); System.out.println(ch + " inserted"); break; case 'd': System.out.println(queue.delete() + " deleted"); break; case 'p': queue.printq(); break; default: System.out.println("Input error"); } while ((ch = getNextChar()) != '\n') ; } } }
Execution of the program: Interactive session
% javac Queue.java % javac QueueTest.java % java QueueTest ia a inserted ib b inserted p Size: 2, rp: 2, fp: 0, q: q[0]=; q[1]=a; q[2]=b; q[3]=; fp^ rp^ ic c inserted id d inserted p Size: 4, rp: 0, fp: 0, q: q[0]=d; q[1]=a; q[2]=b; q[3]=c; rp,fp^ d a deleted d b deleted p Size: 2, rp: 0, fp: 2, q: q[0]=d; q[1]=a; q[2]=b; q[3]=c; rp^ fp^ ix x inserted iy y inserted p Size: 4, rp: 2, fp: 2, q: q[0]=d; q[1]=x; q[2]=y; q[3]=c; rp,fp^ d c deleted d d deleted d x deleted d y deleted p Size: 0, rp: 2, fp: 2, q: q[0]=d; q[1]=x; q[2]=y; q[3]=c; rp,fp^ d Underflow ? deleted ir r inserted is s inserted it t inserted iu u inserted iv Overflow v inserted p Size: 4, rp: 2, fp: 2, q: q[0]=s; q[1]=t; q[2]=u; q[3]=r; rp,fp^ q %

// Queue.java: queue implementation
public class Queue {
   private int qMaxSize;// max queue size
   private int fp = 0;  // front pointer
   private int rp = 0;  // rear pointer
   private int qs = 0;  // size of queue
   private char[] q;    // actual queue

   public Queue(int size) {
      qMaxSize = size;
      fp = 0;
      rp = 0;
      qs = 0;
      q = new char[qMaxSize];
   }

   public char delete() {
      if (!emptyq()) {
         qs--;
         fp = (fp + 1)%qMaxSize;
         return q[fp];
      }
      else {
         System.err.println("Underflow");
         return '?';
      }
   }

   public void insert(char c) {
      if (!fullq()) {
         qs++;
         rp = (rp + 1)%qMaxSize;
         q[rp] = c;
      }
      else
         System.err.println("Overflow\n");
   }

   public boolean emptyq() {
      return qs == 0;
   }

   public boolean fullq() {
      return qs == qMaxSize;
   }
   
   public void printq() {
      System.out.print("Size: " + qs +
         ", rp: " + rp + ", fp: " + fp + ", q: ");
      for (int i = 0; i < qMaxSize; i++)
         System.out.print("q[" + i + "]=" 
            + q[i] + "; ");
      System.out.println();
   }
}

// QueueTest.java: test the queue
import java.io.*;
public class QueueTest {
   // in: reader for reading input data
   private static Reader in = 
         new InputStreamReader(System.in);

   private static char getNextChar() {
      char ch = ' ';
      try {
         ch = (char)in.read();
      }
      catch (Exception exception) {
         System.err.println("Read Error");
         ch = ' ';
      }
      return ch;
   }

   public static void main(String[] args) {
      Queue queue = new Queue(4); // 10 chars
      char ch;
      while ((ch = getNextChar()) != 'q') {
         switch (ch) {
         case 'i':
            ch = getNextChar();
            queue.insert(ch);
            System.out.println(ch + " inserted");
            break;
         case 'd':
            System.out.println(queue.delete() + 
               " deleted");
            break;
         case 'p':
            queue.printq();
            break;
         default: System.out.println("Input error");
         }
         while ((ch = getNextChar()) != '\n')
            ;
      }
   }
}

Execution of the program: Interactive session

% javac Queue.java
% javac QueueTest.java
% java QueueTest
ia
a inserted
ib
b inserted
p
Size: 2, rp: 2, fp: 0, q: q[0]=; q[1]=a; q[2]=b; q[3]=; 
                          fp^            rp^
ic
c inserted
id
d inserted
p
Size: 4, rp: 0, fp: 0, q: q[0]=d; q[1]=a; q[2]=b; q[3]=c; 
                       rp,fp^
d
a deleted
d
b deleted
p
Size: 2, rp: 0, fp: 2, q: q[0]=d; q[1]=a; q[2]=b; q[3]=c;
                          rp^             fp^
ix
x inserted
iy
y inserted
p
Size: 4, rp: 2, fp: 2, q: q[0]=d; q[1]=x; q[2]=y; q[3]=c; 
                                       rp,fp^
d
c deleted
d
d deleted
d
x deleted
d
y deleted
p
Size: 0, rp: 2, fp: 2, q: q[0]=d; q[1]=x; q[2]=y; q[3]=c; 
                                       rp,fp^
d
Underflow
? deleted
ir
r inserted
is
s inserted
it
t inserted
iu
u inserted
iv
Overflow

v inserted
p
Size: 4, rp: 2, fp: 2, q: q[0]=s; q[1]=t; q[2]=u; q[3]=r; 
                                       rp,fp^
q
%