StacksQueues/Java/LinkedQueue

Link: https://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/queues/LinkedQueue.java

LinkedQueue is a linked list based queue class implemented in Java.

Code

Interface

This class implements the standard queue methods:

• add/enqueue
• remove/dequeue

as well as the convenience methods:

• size
• isEmpty
• rotate (rotate moves one element from front of queue to rear of queue)

Test

Here is a test of the LinkedQueue object that shows how it works; this manipulates a queue of integers.

	public static void main(String[] args) {
		LinkedQueue<Integer> q = new LinkedQueue<Integer>();
		System.out.println(q);

		q.enqueue(100);
		q.enqueue(100);
		q.enqueue(100);
		System.out.println(q);

		for(int i=0; i<10; i++) { 
			q.enqueue(i);
		}
		System.out.println(q);

		q.dequeue();
		q.dequeue();
		q.dequeue();
		System.out.println(q);

		for(int i=0; i<3; i++) { 
			q.dequeue();
		}
		System.out.println(q);

		System.out.println("Rotate:");
		q.rotate();
		System.out.println(q);
		q.rotate();
		System.out.println(q);
		q.rotate();
		System.out.println(q);
		
		System.out.println("Size = " + q.size());

	}

Implementation

class Empty extends ArrayIndexOutOfBoundsException{}

class LinkedQueue {

	Node<E> tail;
	int size;

	public LinkedQueue() {
		size = 0;
	};

	public int size() { return size; }
	public boolean isEmpty() { return (size==0); }

	public String toString() { 
		StringBuffer sb = new StringBuffer();
		if(isEmpty()) {
			return "[ EMPTY QUEUE ]";
		} else {
			sb.append("[ ");
			Node<E> runner = tail.getNext();
			int k = 0;
			while(k<size && runner != null) {
				sb.append(runner);
				sb.append(" ");
				k++;
				runner = runner.getNext();
			}
			sb.append(" ]");
			return sb.toString();
		}
	};

	/** Add item e to the back of the linked list. */
	public void enqueue(E e) { 
		if(isEmpty()) {		

			Node<E> newtail = new Node<E>(e);

			// everybody point at the new node
			tail = newtail;

			// tail will link to itself in a 1 item list
			tail.setNext(tail);

		} else {

			Node<E> newtail = new Node<E>(e, tail.getNext());

			// link the new tail 
			tail.setNext(newtail);

			// advance tail pointer
			tail = tail.getNext();

		}
		size++;
	}

	/** Remove item e from the front of the linked list. */
	public E dequeue() { 

		if(isEmpty()) {
			throw new Empty();

		} else if(size==1) { 
			E res = tail.getData();
			tail = null;
			size--;
			return res;

		} else {

			// length of list is at least 2 items.
			// if length = 2, we will end up linking tail to itself, which is fine.
			Node<E> rm = tail.getNext();
			Node<E> newhead = rm.getNext();

			tail.setNext(newhead);
			size--;
			return rm.getData();
		}
	}


	/** Rotate the deque by skipping the next item in line and putting it in back. */
	public void rotate() { 
		if(isEmpty()) { 
			throw new Empty();
		}

		// The whole point of using a circular linked list is to avoid creating 
		// a new node to do this kind of operation.
		// So don't call enqueue(dequeue()) !!!
		// 
		// Simply advance the tail pointer forward by one.
		tail = tail.getNext();
	}


}