A queue is a collection of items which are kept in order. Adding an item to the queue adds it to the end of the queue, and removing an item removes the item at the front of the queue. Queues are used in many real life applications.
A double queue is a queue where items can not only be added to the end and removed from the front, but added to the front and removed from the end as well.
Here is an implementation of a double queue in Java.
MyDoubleQueue.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 | public class MyDoubleQueue { // Reference to the first node in the list. private Node _first = null ; // Reference to the last node in the list. private Node _last = null ; /** * Insert a Node at the front of the list. * * @param n */ public void insertFront(Node n) { // Make sure we have a valid node. if (n == null ){ return ; } // If the list is already empty, set the node to be first. if (isEmpty()){ _first = n; _last = n; } else { // The list is not empty, so we must set a proper connection. n.setNext(_first); _first.setPrev(n); _first = n; } } /** * Insert a node at the end of the list. * * @param n */ public void insertRear(Node n) { // Make sure we have a valid node. if (n == null ){ return ; } // If the list is empty, add at first spot. if (isEmpty()){ _first = n; _last = n; } else { // Add the node at the end. _last.setNext(n); n.setPrev(_last); _last = n; } } /** * Remove the node from the front of the list. * * @return */ public Node removeFront() { // If the list is empty, nothing should be removed. if (!isEmpty()){ // If the length of the list is 1. if (getSize() == 1 ){ _first = null ; _last = null ; } else { // We have 2 nodes or more. _first = _first.getNext(); _first.setPrev( null ); } } // Return the new first node. return _first; } /** * Remove a node from the end of the list. * * @return */ public Node removeRear() { // If the list is empty, we have nothing to remove. if (!isEmpty()){ // If the list has one element, we are removing both the front and last element. if (getSize() == 1 ){ _first = null ; _last = null ; } else { // We have at least two elements. _last.getPrev().setNext( null ); _last = _last.getPrev(); } } // Return the new last node. return _last; } /** * Check if the list is empty. */ public boolean isEmpty() { // By definition, if _first is null, we have an empty list. return _first == null ; } /** * Get the size of the list. * * @return */ public int getSize() { // If the list is empty, the size is 0. if (isEmpty()){ return 0 ; } else if (_first.getNext() == null ) { return 1 ; // We have a list of length one. } else { // Define the size. int size = 1 ; // We have at least two nodes. Go until the end of the list, counting each node. Node temp = _first; while (temp.getNext() != null ){ // Increase the size. size++; // Update the reference. temp = temp.getNext(); } // Return the size. return size; } } } |
Node.java
This class is an abstraction of an actual class that you would want to use in a queue.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | public class Node { private Node _prev = null ; // Reference to the previous node. private Node _next = null ; // Reference to the next node. /** * Constructor. */ Node() { } public Node getPrev() { return _prev; } public void setPrev(Node n) { _prev = n; } public Node getNext() { return _next; } public void setNext(Node n) { _next = n; } } |