A double-ended queue, or deque (pronounced like deck). With a deque you can add, remove, or view
Question:
A double-ended queue, or deque (pronounced like "deck"). With a deque you can add, remove, or view elements from both ends of the queue. Rather than use the Deque interface supplied by the Java API, design your own DequeADT interface (patterned after QueueADT). Then, implement a deque using links.
The driver should makes a deque of moderate size (say five or six). It should repetitively add elements to the front, and then the rear. For each addition, output the contents of the deque as well as the size, front element, and last element. Then, repetitively remove elements from the deque. For each removal, output the contents of the deque as well as the size, front element, and last element.
package jsjf;
import jsjf.exceptions.*;
/** * LinkedQueue represents a linked implementation of a queue. * * Solution to Programing Project 14.1 (full implementation) * * @author Java Foundations * @version 4.0 */ public class LinkedQueue
/** * makes a empty queue. */ public LinkedQueue() { count = 0; head = tail = null; }
/** * Adds the specified element to the tail of this queue. * @param element the element to be added to the tail of the queue */ public void enqueue(T element) { LinearNode
if (isEmpty()) head = node; else tail.setNext(node);
tail = node; count++; }
/** * Removes the element at the head of this queue and returns a * reference to it. * @return the element at the head of this queue * @throws EmptyCollectionException if the queue is empty */ public T dequeue() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException("queue");
T result = head.getElement(); head = head.getNext(); count--;
if (isEmpty()) tail = null;
return result; }
/** * Returns a reference to the element at the head of this queue. * The element is not removed from the queue. * @return a reference to the first element in this queue * @throws EmptyCollectionsException if the queue is empty */ public T first() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException("queue");
return head.getElement(); }
/** * Returns true if this queue is empty and false otherwise. * @return true if this queue is empty */ public boolean isEmpty() { return (count == 0); }
/** * Returns the number of elements currently in this queue. * @return the number of elements in the queue */ public int size() { return count; }
/** * Returns a string representation of this queue. * @return the string representation of the queue */ public String toString() { String result = ""; LinearNode
while (current != null) { result = result + current.getElement() + " "; current = current.getNext(); }
return result; } }
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest