r/javaexamples • • Jun 27 '15

Double-Ended Queue (Deque) with Multiple Iterators

Double-Ended Queue (Deque)

A Deque or double-ended Queue is a data structure that has the methods of both a Stack and a Queue. Elements can be inserted and removed from either the head(front) or the tail(end) of the list. Java has a Deque interface already, but it is interesting to make one ourselves.

A Deque can be implemented either with a doubly-linked list structure, or with a dynamic array. Here we are using the linked list style.

Like most of our other linked-list based data structures, we start with a Node class:

// inner class for nodes
class Node
{
	private E value;
	private Node next;
	private Node previous;

	public Node(E value, Node next, Node previous)
	{
		this.value = value;
		this.next = next;
		this.previous = previous;
	}
}	

Our Deque class has the following methods:

  • push() - add element to the beginning of the deque

  • append() - add element to the end of the deque

  • pop() - retrieve and remove the element at the head of the deque

  • eject() - retrieve and remove the element at the end

  • peekFirst() - retrieve first element without removing it

  • peekLast() - retrieve last element without removing it

  • clear()

  • size()

  • isEmpty()

Also of interest is I have provided two different Iterators for the Deque, one that will iterate through the list normally, and one that will iterate in a descending or reverse order. Since we are using a doubly-linked list, going through the list in reverse is trivial.

To make multiple iterators for one class, make a default one which implements Iterable for the class, then you can make additional methods that return an Iterable instance, using nested anonymous inner classes like this:

public Iterable<E> reverse()
{
	return new Iterable<E>()
	{
		public Iterator<E> iterator()
		{
			return new Iterator<E>()
			{
				Node current = tail;
				@Override
				public E next()
				{
					E value = current.value;
					current = current.previous;
					return value;
				}

				@Override
				public boolean hasNext()
				{
					return (current != null);
				}
				@Override
				public void remove()
				{
					throw new UnsupportedOperationException("remove() not available.");
				}		

			};
		}
	};
}

You use this easily within a For-Each loop like this:

for (Type each : dequeName.reverse())
{
	...do stuff...
}

Or, in the Java 8 fashion:

dequeName.reverse().forEach(...do stuff...);

Here's the code:

/*
 * Double-Ended Queue Implementation (Deque.java)
 *
 * A simple, doubly linked list
 */
import java.util.NoSuchElementException;
import java.util.Iterator;


/**
 * class Deque - Double Ended Queue
 * @author /u/Philboyd_Studge
 */
@SuppressWarnings("unchecked")
public class Deque<E> implements Iterable<E>
{
	Node head;
	Node tail;
	int length;

	//Node current;

	/**
	 * Construct empty Deque
	 */
	public Deque()
	{
		head = null;
		tail = null;
		length = 0;
	}

	/**
	 * @return true if deque is empty
	 */
	public boolean isEmpty()
	{
		return (head==null);
	}

	/**
	 * @return number of elements in deque
	 */
	public int size()
	{
		return length;
	}

	/**
	 * clear deque
	 */
	public void clear()
	{
		head = null;
		tail = null;
		length = 0;
	}

	/**
	 * add value of type E to beginning of deque
	 * @param value E
	 */
	public void push(E value)
	{
		if (head==null)
		{
			head = new Node(value, null, null);
			tail = head;
			length++;
		}
		else
		{
			Node temp = new Node(value, head, null);
			head.previous = temp;
			head = temp;
			length++;
		}
	}

	/**
	 * add value of type E to end of deque
	 * @param value E
	 */
	public void append(E value)
	{
		if (head==null)
		{
			head = new Node(value, null, null);
			tail = head;
			length++;
		}
		else
		{
			Node temp = new Node(value, null, tail);
			tail.next = temp;
			tail = temp;
			length++;
		}		
	}

	/**
	 * return and remove value at beginning of deque
	 * @return E value of type E
	 * @throws NoSuchElementException
	 */
	public E pop()
	{
		if (head==null) throw new NoSuchElementException("List is empty.");
		E value = head.value;
		head = head.next;
		if (head != null)
		{
			head.previous = null;
		} 
		else
		{
			// empty
			tail = head;
		}
		length--;
		return value;
	}

	/**
	 * return and remove value at end of deque
	 * @return E value of type E
	 * @throws NoSuchElementException
	 */
	public E eject()
	{
		if (tail==null) throw new NoSuchElementException("List is empty.");
		E value = tail.value;
		tail = tail.previous;
		if (tail != null)
		{
			tail.next = null;
		} 
		else
		{
			// empty
			head = tail;
		}
		length--;
		return value;
	}

	/**
	 * return value at beginning of deque without removing it
	 * @return E value of type E
	 * @throws NoSuchElementException
	 */
	public E peekFirst()
	{
		if (head==null) throw new NoSuchElementException("List is empty.");
		return head.value;
	}

	/**
	 * return value at end of deque without removing it
	 * @return E value of type E
	 * @throws NoSuchElementException
	 */
	public E peekLast()
	{
		if (tail==null) throw new NoSuchElementException("List is empty.");
		return tail.value;
	}

	/**
	 * Implement method for Iterable
	 * @return Iterator of type E
	 */
	@Override
	public Iterator<E> iterator()
	{
		return new Iterator<E>()
		{
			Node current = head;
			/**
			 * Implement method for Iterator
			 * @return value of type E
			 */
			@Override
			public E next()
			{
				E value = current.value;
				current = current.next;
				return value;
			}

			/**
			 * Implement method for Iterator
			 * @return true if more elements available
			 */
			@Override
			public boolean hasNext()
			{
				return (current != null);
			}

			@Override
			public void remove()
			{
				throw new UnsupportedOperationException("remove() not available.");
			}		
		};
	}

	/**
	 * Secondary Iterator - reversed order
	 * use like <code>for (Type each : deque.reverse())</code>
	 * @return Iterable instance of Iterable with reverse Iterator
	 */
	public Iterable<E> reverse()
	{
		return new Iterable<E>()
		{
			public Iterator<E> iterator()
			{
				return new Iterator<E>()
				{
					Node current = tail;
					@Override
					public E next()
					{
						E value = current.value;
						current = current.previous;
						return value;
					}

					@Override
					public boolean hasNext()
					{
						return (current != null);
					}
					@Override
					public void remove()
					{
						throw new UnsupportedOperationException("remove() not available.");
					}		

				};
			}
		};
	}



	// inner class for nodes
	class Node
	{
		private E value;
		private Node next;
		private Node previous;

		public Node(E value, Node next, Node previous)
		{
			this.value = value;
			this.next = next;
			this.previous = previous;
		}
	}	
}

Here is some test code:

public class TestDeque
{

	public static void main(String[] args)
	{
		Deque<Integer> d = new Deque<>();
		d.push(2);
		d.push(1);
		d.append(3);
		d.append(4);
		d.push(0);

		for (Integer each : d) System.out.println(each);

		System.out.println("Size:" + d.size());

		System.out.println(d.pop());
		System.out.println(d.eject());
		System.out.println();

		d.clear();
		d.append(7);
		d.push(5);
		System.out.println(d.peekFirst() + " : " + d.peekLast());
		System.out.println(d.isEmpty());
		d.forEach(System.out::println);
		System.out.println("Size:" + d.size());

		System.out.println(d.eject());
		System.out.println(d.pop());
		System.out.println();

		int[] a = { 4, 567, 8, 443, 12, 33, 4, 1029, 7};

		Deque<Integer> d2 = new Deque<>();

		for (int each : a) d2.append(each);

		for (Integer each : d2) System.out.println(each);
		System.out.println("Reversed");
		d2.reverse().forEach(System.out::println);	
	}
}
2 Upvotes

0 comments sorted by