StacksQueues/Java/ArrayDeque

Notes

array-based deque (double-ended queue) object.

implementation details:

• one option is to have an array that is re-sized and shifted each time the front is removed.
• a better option is to have floating head and tail index variables.
• would then need to check if head floated too far.
• can have variable size array, or fixed size array.

code

Link to the code on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/stacks-queues-deques/queues/ArrayQueue.java

interface

The methods implemented for a queue object are:

• size() - get the number of elements in the queue
• isEmpty() - returns true if queue is empty
• add() - add the element to the back of the queue
• remove() - remove and return the element at the front of the queue
• peek() - return a reference to the first item in the queue, but do not remove it

Implementing these for an array based queue requires us to do the following:

• size - keep track of the size (tail - head)
• add method - when things are added and we are at capacity, copy new items into new array (from head cycling through to tail, in order.)
• remove - to remove an item from the queue we remove it and increment head by 1 (much better than the O(n) scooting everything up)
• resize - allocates a new array, and copies from old to new from head to tail, resetting index values.

implementation

The implementation got a bit confusing, mainly because I was trying to save a few bytes here and there. The take-home: you can optimize for bytes til the cows come home, but if it doubles your implementation time, those were some expensive 8-byte savings. Just add a boolean or an extra index - if you need to keep track of the size, use n or size. Especially with floating head and tail pointers - don't try and do fancy math until you have to.

import java.util.*;
import java.io.*;

class Empty extends ArrayIndexOutOfBoundsException{};

/**
 * Array based implementation of a queue.
 *
 * methods:
 *  - toString
 *  - isEmpty
 *  - size
 *  - add
 *  - remove
 *  - peek
 */
public class ArrayQueue<T> {

	/////////////////////////////////////////////



	public static void main(String[] args) { 
		ArrayQueue<Integer> a = new ArrayQueue<Integer>();
		int na = 17;
		for(int i=0; i<na; i++) { 
			a.add(i);
			System.out.println(a);
		}
		System.out.println(a);
		System.out.println("Added "+na+" items.");

		int nr = 13;
		System.out.println("Removing "+nr+" items.");
		for(int j=0; j<nr; j++) {
			a.remove();
			System.out.println(a);
		}
		System.out.println(a);
		System.out.println("Size: "+a.size());
		
		try {
			int many = 1000;
			System.out.println("Removing "+many+" items.");
			for(int j=0; j<many; j++) {
				System.out.println("Size of a is "+a.size()); 
				a.remove();
				System.out.println(a);
			}
			System.out.println(a);
		} catch(Empty e) {
			System.out.println("Caught empty stack exception.");
		}


	}

The tests are written to test the add, remove, toString, and size methods, and to check whether we can remove from an empty Queue.

Next come the private fields and constructor:

	private Object[] data;
	private int size, head, tail;
	private boolean empty;
	private static final int INIT_CAPACITY = 1;


	public ArrayQueue() {
		this.head = 0;
		this.tail = -1;
		this.size = 0;
		this.empty = true;
		this.data = new Object[INIT_CAPACITY];
	}

The learnings here were again, keep it simple: start with an array of size 1, not of size 10

Keep your variables together, and away from the main method (put the main method at the top or bottom, or in another driver class.)

	public boolean isEmpty() { 
		return empty; 
	}

	/** Return the size - distance from head to tail - with rotating head and tail positions. */
	public int size() { 
		return size; 
	}

	public String toString() { 
		StringBuffer sb = new StringBuffer();
		sb.append("[ ");
		if(isEmpty()) { 
			sb.append("]");
			return sb.toString();
		}

		// length >= 1
		int n = data.length;
		for(int i=this.head; i!=this.tail; i=(i+1)%n ) { 
			// fencepost
			if(i!=this.head) { 
				sb.append(", ");
			}
			sb.append(data[i].toString());
		}
		sb.append(" ]");
		return sb.toString();
	}

	/** Append an item to the back of the queue */
	public void add(T e) {

		if(size==data.length) {
			resize(data.length*2);
		}
		tail++;
		data[tail] = e;
		size++;
		this.empty = false;
	}

	public Object remove() throws Empty {
		if(isEmpty()) {
			throw new Empty();
		}
		Object first = data[head];
		data[head]=null;
		head++;
		size--;
		if(size==0) {
			this.empty = true;
		} else if(size==data.length/4) {
			resize(data.length/2);
		}
		return first;
	}

	private void resize(int newcap) { 
		if(newcap>0) { 
			int n = this.data.length;

			Object[] newdat = new Object[newcap];
			Object[] olddat = this.data;
			int k = 0;

			for(int i=this.head; i!=this.tail; i=(i+1)%n ) { 
			    newdat[k] = olddat[i];
				k++;
			}
			newdat[k] = olddat[this.tail];

			this.data = newdat;
			this.head = 0;
			this.tail = k;
			this.size = k+1;
		}
	}
}