Java Tutorial/Collections/Your Queue

A Queue Implemented by a Linked List

   <source lang="java">

class Link {

 public int iData;
 public Link next;
 public Link(int id) {
   iData = id;
 }
 public String toString() {
   return "{" + iData + "} ";
 }

} class LinkList {

 private Link first;
 public LinkList() {
   first = null;
 }
 public boolean isEmpty() {
   return (first == null);
 }
 public void insertFirst(int dd) {
   Link newLink = new Link(dd);
   newLink.next = first;
   first = newLink;
 }
 public int deleteFirst() {
   Link temp = first;
   first = first.next;
   return temp.iData;
 }
 public String toString() {
   String str = "";
   Link current = first;
   while (current != null) {
     str += current.toString();
     current = current.next;
   }
   return str;
 }

} class FirstLastList {

 private Link first;
 private Link last;
 public FirstLastList() {
   first = null;
   last = null;
 }
 public boolean isEmpty() {
   return first == null;
 }
 public void insertFirst(int dd) {
   Link newLink = new Link(dd);
   if (isEmpty())
     last = newLink;
   newLink.next = first;
   first = newLink;
 }
 public void insertLast(int dd) {
   Link newLink = new Link(dd);
   if (isEmpty())
     first = newLink;
   else
     last.next = newLink;
   last = newLink;
 }
 public int deleteFirst() {
   int temp = first.iData;
   if (first.next == null)
     last = null;
   first = first.next;
   return temp;
 }
 public String toString() {
   String str = "";
   Link current = first;
   while (current != null) {
     str += current.toString();
     current = current.next;
   }
   return str;
 }

} class LinkQueue {

 private FirstLastList theList;
 public LinkQueue() {
   theList = new FirstLastList();
 }
 public boolean isEmpty() {
   return theList.isEmpty();
 }
 public void insert(int j) {
   theList.insertLast(j);
 }
 public double remove() {
   return theList.deleteFirst();
 }
 public String toString() {
   return theList.toString();
 }

} public class MainClass {

 public static void main(String[] args) {
   LinkQueue theQueue = new LinkQueue();
   theQueue.insert(20);
   theQueue.insert(40);
   System.out.println(theQueue);
   theQueue.insert(60);
   theQueue.insert(80);
   System.out.println(theQueue);
   theQueue.remove();
   theQueue.remove();
   System.out.println(theQueue);
 }

}</source>

{20} {40} 
{20} {40} {60} {80} 
{60} {80}

Priority Queues

In a priority queue, items are ordered by key value, so that the item with the lowest key (or in some implementations the highest key) is always at the front. Items are inserted in the proper position to maintain the order.

   <source lang="java">

class PriorityQueue {

 private int maxSize;
 private double[] queArray;
 private int nItems;
 public PriorityQueue(int s) {
   maxSize = s;
   queArray = new double[maxSize];
   nItems = 0;
 }
 public void insert(double item) {
   int j;
   if (nItems == 0) {
     queArray[nItems++] = item;
   } else {
     for (j = nItems - 1; j >= 0; j--)
     {
       if (item > queArray[j])
         queArray[j + 1] = queArray[j];
       else
         break;
     }
     queArray[j + 1] = item;
     nItems++;
   }
 }
 public double remove() {
   return queArray[--nItems];
 }
 public double peekMin() {
   return queArray[nItems - 1];
 }
 public boolean isEmpty() {
   return (nItems == 0);
 }
 public boolean isFull() {
   return (nItems == maxSize);
 }

} public class MainClass {

 public static void main(String[] args) {
   PriorityQueue thePQ = new PriorityQueue(5);
   thePQ.insert(30);
   thePQ.insert(50);
   thePQ.insert(10);
   thePQ.insert(40);
   thePQ.insert(20);
   while (!thePQ.isEmpty()) {
     double item = thePQ.remove();
     System.out.print(item + " ");
   }
 }

}</source>

10.0 20.0 30.0 40.0 50.0

Queue: The first item inserted is the first to be removed (FIFO)

   <source lang="java">

class Queue {

 private int maxSize;
 private int[] queArray;
 private int front;
 private int rear;
 private int nItems;
 public Queue(int s) {
   maxSize = s;
   queArray = new int[maxSize];
   front = 0;
   rear = -1;
   nItems = 0;
 }
 public void insert(int j) {
   if (rear == maxSize - 1)
     rear = -1;
   queArray[++rear] = j;
   nItems++;
 }

 public int remove() {
   int temp = queArray[front++];
   if (front == maxSize)
     front = 0;
   nItems--;
   return temp;
 }
 public int peekFront() {
   return queArray[front];
 }
 public boolean isEmpty() {
   return (nItems == 0);
 }
 public boolean isFull() {
   return (nItems == maxSize);
 }
 public int size() {
   return nItems;
 }

} public class MainClass {

 public static void main(String[] args) {
   Queue theQueue = new Queue(5); // queue holds 5 items
   theQueue.insert(10); // insert 4 items
   theQueue.insert(20);
   theQueue.insert(30);
   theQueue.insert(40);
   theQueue.remove(); // remove 3 items
   theQueue.remove(); // (10, 20, 30)
   theQueue.remove();
   theQueue.insert(50); // insert 4 more items
   theQueue.insert(60); // (wraps around)
   theQueue.insert(70);
   theQueue.insert(80);
   while (!theQueue.isEmpty()) { // all items
     int n = theQueue.remove(); // (40, 50, 60, 70, 80)
     System.out.print(n);
     System.out.print(" ");
   }
   System.out.println("");
 }

}</source>

40 50 60 70 80