Queue - fundamental data type to manage collections of objects.

0-Queue.md

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).

##Queue

####Concept

• one of the fundamental data types used to manage a collection of objects
• works like a 'queue' of people
  • people enter from the back of the queue and leave from the front
  • new items are enqueued on to the back of the queue
  • items are dequeued from the front of the queue
  • this management method known as a First In, First Out (FIFO)

####Implementation

• there is more than one way to accomplish this behaviour
  • both linked lists and arrays are two fundamental ways to store the data
  • the rest of the data type then determines when and how the array/linked list is accessed
    • this is what determines the stack's behaviour

####Notes

• the order in which items are taken out will always match the order in which they were added

####See Also

• Stacks

ArrayQueue.java

public class ArrayQueue{
	String[] s;

        /* 
        - Because we are removing from the front, there
          will be `null` elements at the beginning of the 
          array. 

        - We need another pointer to tell us where the array
          begins.
        */
	int tail = 0;
	int head = 0;

	public ArrayQueue()
	{
		s = new String[1];
	}

	public String dequeue()
	{
		if (isEmpty())
			throw new IndexOutOfBoundsException("No items in queue. Cannot dequeue.");

		String tmp = s[head];
		s[head++] = null;

		if ((tail - head) == s.length/4){
			shiftLeft();
			resize(s.length/2);
		}

		if (isEmpty()){
			head = 0;
			tail = 0;
		}

		return tmp;
	}

	public void enqueue(String item)
	{
		s[tail++] = item;
		if ( tail == s.length)
			shiftLeft();
		if ((tail - head) == s.length)
			resize(s.length * 2);
	}

	private boolean isEmpty()
	{
		return head == tail;
	}

	private void shiftLeft()
	{
		tail = tail - head;

		String[] copy = new String[s.length];
		for (int i = 0; i < tail; i++)
			copy[i] = s[i + head];
		s = copy;

		head = 0;
	}

	private void resize(int capacity)
	{
		System.out.println("Resizing to " + capacity);
		String[] copy = new String[capacity];
		for (int i = 0; i < tail; i++)
			copy[i] = s[i];
		s = copy;
	}
	
	// client
	public static void main(String[] args)
	{
		ArrayQueue queue = new ArrayQueue();
		queue.enqueue("Hello");
		queue.enqueue("my");
		queue.enqueue("name");
		System.out.println(queue.dequeue());
		queue.enqueue("is");
		System.out.println(queue.dequeue());
		System.out.println(queue.dequeue());
		System.out.println(queue.dequeue());
		queue.enqueue("Jim.");
		System.out.println(queue.dequeue());
		queue.dequeue();
	}
}

LinkedQueue.java

public class LinkedQueue{
	Node first;
	Node last;

	// inner class for linked-list
	private class Node{
		String item;
		Node next;
	}

	public void enqueue(String item)
	{
		Node oldlast = last;	
		last = new Node();
		last.item = item;

		if (isEmpty()) first = last;
		else           oldlast.next = last;
	}
		
	public String dequeue()
	{
		if (isEmpty())
			throw new IndexOutOfBoundsException("Queue empty, cannot dequeue.");
		String item = first.item;
		first = first.next;

		if (isEmpty())
			last = null;
		return item;

	}

	public boolean isEmpty()
	{
		return first == null;
	}

	// client
	public static void main(String args[])
	{
		LinkedQueue queue = new LinkedQueue();
		queue.enqueue("Hello");
		queue.enqueue("my");
		queue.enqueue("name");
		System.out.println(queue.dequeue());
		queue.enqueue("is");
		System.out.println(queue.dequeue());
		System.out.println(queue.dequeue());
		System.out.println(queue.dequeue());
		queue.enqueue("Jim.");
		System.out.println(queue.dequeue());
		queue.dequeue();
	}
}