StacksQueues/Java/ArrayDeque - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:53:41Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:53, 9 October 2019
Line 10:		Line 10:
	==code==		==code==

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

	==interface==		==interface==

Admin: /* Notes */

2017-06-03T21:25:50Z

Notes

← Older revision		Revision as of 21:25, 3 June 2017
Line 4:		Line 4:

	implementation details:		implementation details:
	* ~~one option is to have an array that is re-sized and shifted each time the front is removed.~~		* floating head/tail index variables and dynamic resizing
	* a better option is to have floating head ~~and~~ tail index variables.		* dynamic moving also required - if head floats too far.
	* ~~would then need to check~~ if head ~~floated~~ too far.		* variable or fixed size.
	* ~~can have~~ variable ~~size array,~~ or fixed size ~~array~~.

	==code==		==code==

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

	==interface==		==interface==

	The methods implemented for a ~~queue~~ object are:		The methods implemented for a deque object are:
	* size() - get the number of elements in the queue		* size() - get the number of elements in the queue
	* isEmpty() - returns true if queue is empty		* isEmpty() - returns true if queue is empty
	* ~~add~~() - ~~add the element~~ to ~~the back of the queue~~		* first() - return reference to front, but don't remove
	* remove() - remove ~~and return the element at the front of the queue~~		* last() - return reference to back, but don't remove
	* ~~peek~~() - return a reference to ~~the first item in the queue~~, but ~~do not~~ remove it		* addFront() - add new item to front of queue
			* addBack() - add new item to back of queue
	~~Implementing these for an array based~~ queue ~~requires us to do the following:~~		* removeFront() - remove item from front of queue
	* ~~size - keep track of the size~~ (~~tail~~ - ~~head)~~		* removeBack() - remove item from back of queue
	* 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=		=Flags=

Admin: /* implementation */

2017-06-03T21:23:41Z

implementation

Show changes

Admin: Created page with "=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...."

2017-06-03T21:23:29Z

Created page with "=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...."

New page

=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.

<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=

[[Category:Queue]]
[[Category:Arrays]]
[[Category:Java]]
{{DataStructuresFlag}}