|
|
| (3 intermediate revisions by the same user not shown) |
| Line 11: |
Line 11: |
| ==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://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/queues/ArrayQueue.java |
| | |
| | A fixed size implementation: https://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/queues/ArrayQueueFS.java |
|
| |
|
| ==interface== | | ==interface== |
| Line 28: |
Line 30: |
| * resize - allocates a new array, and copies from old to new from head to tail, resetting index values. | | * resize - allocates a new array, and copies from old to new from head to tail, resetting index values. |
|
| |
|
| ==implementation== | | ==implementations== |
| | |
| 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;
| |
| }
| |
| }
| |
| }
| |
| | |
| =Flags=
| |
|
| |
|
| [[Category:Queue]]
| | First version: using an array, floating head and tail pointers, dynamically sized array. |
| [[Category:Arrays]]
| |
| [[Category:Java]]
| |
| {{DataStructuresFlag}}
| |
Notes
array-based 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://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/queues/ArrayQueue.java
A fixed size implementation: https://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/queues/ArrayQueueFS.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.
implementations
First version: using an array, floating head and tail pointers, dynamically sized array.