Revision as of 21:23, 3 June 2017

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.

Flags

@@ Line 27: / Line 27: @@
 * 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.
-<pre>
-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.");
-		}
-	}
-</pre>
-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:
-<pre>
-	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];
-	}
-</pre>
-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.)
-<pre>
-	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;
-		}
-	}
-}
-</pre>
 =Flags=

StacksQueues/Java/ArrayDeque: Difference between revisions

From charlesreid1

Revision as of 21:23, 3 June 2017

Contents

Notes

code

interface

Flags