To learn how to work with Deques.
A Deque, is a linear data structure that permits to insert and to remove elements on both sides. To build it, we will be based on the use of a Double Linked List [DLL] on which we will implement the corresponding methods to achieve such behaviour.
A Deque's behaviour can be achieved by the implementation of the following interface that shows its main methods:
/** * Interface for a Deque. * * @author DIT-UC3M * */ public interface Dqueue { void insertFirst[Object obj]; void insertLast[Object obj]; Object removeFirst[]; Object removeLast[]; int size[]; }To implement a Deque by using a DLL, perform the following tasks:
Program the DNode class which represents the node of a Double Linked List [DLL]. Such node will contain both prev and next references to the previous and next node of the current one, as well as an Object reference to the data to be stored.
Declare the DLDqueue class that will implement a Deque based on a DLL. In order to do this, it must implement the Dqueue interface that has been previously mentioned.
Add the head and tail attributes that represents the nodes at both ends of the DLL and the integer attribute size that permits to store the size of it.
Program the constructor of the DLDqueue class that initializes the head and tail references to an emtpy DLL node and set the size to 0.
Program the following methods of the Dqueue's interface:
public void insertFirst[Object obj]
This method inserts an object at the beginnig of the DLL.
public void insertLast[Object obj]
This method inserts an object at the end of the DLL.
public Object removeFirst[]
This method extracts an object from the beginning of the DLL and removes it from the list. If such object does not exist, the method returns null.
public Object removeLast[]
This method extracts an object from the end of the DLL and removes it from the list. If such object does not exist, the method returns null.
public int size[]
This method returns the size of the DLL list.
Finally, implement the public String toString[] method that permits to print the content of the Deque on console according the next format [the shown values are examples]:
head [ 1-2-3-4-5 ] tail
IMPORTANT NOTE!!
In this exercise, we have practice with the design and implementation of a Deque. However, in the Java API there are also several classes that implement such data structures. A Deque is defined by the following interface: Interface Deque. There are also two possible class implemntations of it, one that is based on arrays [ArrayDeque] and another one based on linked lists [LinkedList].
Solution
Solutions are included in the following listings:
/** * An Implementation of a Double Linked List Node * * @author DIT-UC3M * */ public class DNode { DNode next, prev; Object val; public DNode[] { this.next = null; this.prev = null; this.val = null; } public DNode[Object val, DNode first, DNode last] { this.next = first; this.prev = last; this.val = val; } public DNode getNext[] { return next; } public void setNext[DNode next] { this.next = next; } public DNode getPrev[] { return prev; } public void setPrev[DNode prev] { this.prev = prev; } public Object getVal[] { return val; } public void setVal[Object val] { this.val = val; } } /** * Class that implements a Deque with a Double Linked List. * * @author DIT-UC3M * */ public class DLDqueue implements Dqueue { DNode head, tail; int size; public DLDqueue[] { head = new DNode[]; tail = new DNode[]; head.setNext[tail]; tail.setPrev[head]; size = 0; } public void insertFirst[Object obj] { DNode h = head; DNode node = new DNode[]; node.setVal[obj]; node.setNext[h]; h.setPrev[node]; head = node; if [size == 0] tail = node; size++; } public void insertLast[Object obj] { DNode t = tail; DNode node = new DNode[]; node.setVal[obj]; node.setPrev[t]; t.setNext[node]; tail = node; if [size == 0] head = node; size++; } public Object removeFirst[] { if [head == null] return null; Object val = head.getVal[]; head = head.getNext[]; size--; return val; } public Object removeLast[] { if [tail == null] return null; Object val = tail.getVal[]; tail = tail.getPrev[]; size--; return val; } public int size[] { return size; } public String toString[] { String s = "head ["; DNode aux = head; for [int i = 0; i < size; i++] { s += aux.getVal[]; if [aux == tail] { break; } s += "-"; aux = aux.getNext[]; } return s + "] tail"; } }