1. Queues
The ADT queue organizes data in the order in which they were added, it follows the FIFO or first-in first-out apporach. Queues can be used for a lot of problems, for example, in the investing world which stock is sold first when the investor made multiple purchases over a time frame. Like any ADT, it restricts accessors and mutators to specific methods defined below.
Abstract Data Type: Queue
Data:
- A collection of objects in chronological order and having the same data type
| Pseudocode | UML | Description |
|---|---|---|
enqueue(newEntry) |
+enqueue(newEntry: integer): void |
Adds a new entry to the back of the queue. |
dequeue() |
+dequeue(): T |
Removes and returns the entry at the front of the queue. |
getFront() |
+getFront(): T |
Retrieves the queue’s front entry without changing the queue in any way. |
isEmpty() |
+isEmpty(): boolean |
Detects whether the queue is empty. |
isFull() |
+isFull(): boolean |
Detects whether the queue is full. |
clear() |
+clear(): void |
Removes all entries from the queue. |
Interface of the ADT Queue
public interface QueueInterface<T> {
/** Adds a new entry to the back of this queue.
@param newEntry An object to be added.
@throws FullQueueException if the queue is fill. */
public void enqueue(T newEntry) throws FullQueueException;
/** Removes and returns the entry at the front of this queue.
@return The object at the front of the queue.
@throws EmptyQueueException if the queue is empty before thecoperation. */
public T dequeue() throws EmptyQueueException;
/** Retrieves the entry at the front of this queue.
@return The object at the front of the queue.
@throws EmptyQueueException if the queue is empty. */
public T getFront() throws EmptyQueueException;
/** Detects whether this queue is empty.
@return True if the queue is empty, or false otherwise. */
public boolean isEmpty();
/** Detects whether this queue is full.
@return True if the queue is full, or false otherwise. */
public boolean isFull();
/** Removes all entries from this queue. */
public void clear();
}
Linked-Based Implementation
We can use a chain with two ends to represent our queue. To enqueue, create a new node with lastNode as next and set lastNode as that new node. To dequeue, get the firstNode and set the firstNode to the next node and return the orginial firstNode.
Implementation
public class LinkedQueue<T> implements QueueInterface<T> {
private Node firstNode;
private Node lastNode;
public LinkedQueue() {
firstNode = null;
lastNode = null;
}
public void enqueue(T newEntry) throws FullQueueException {
Node newNode = new Node(newEntry, null);
if (isEmpty()) {
this.firstNode = newNode;
} else {
this.lastNode.setNextNode(newNode);
}
this.lastNode = newNode;
}
public T getFront() throws EmptyQueueException {
if (isEmpty()) {
throw new EmptyQueueException();
} else {
return firstNode.getData();
}
}
public T dequeue() throws EmptyQueueException {
if (isEmpty())
throw new EmptyQueueException();
T front = getFront();
// Assertion: firstNode != null
this.firstNode.setData(null);
this.firstNode = this.firstNode.getNextNode();
if (this.firstNode == null) {
this.lastNode = null;
} else {
if (this.firstNode.getNextNode() == null) {
this.lastNode = this.firstNode;
}
}
return front;
}
public boolean isEmpty() {
return (this.firstNode == null) && (this.lastNode == null);
}
public void clear() {
this.firstNode = null;
this.lastNode = null;
}
public boolean isFull() {
return false; // since there is no limit to how many nodes we can add, except if the memory completely fills up which is unlikely, the queue will never be filled.
}
private class Node {
private T data;
private Node next;
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
public void setNextNode(Node n) {
this.next = n;
}
public T getData() {
return this.data;
}
public Node getNextNode() {
return this.next;
}
public void setData(T data) {
this.data = data;
}
}
}
Array-Based Implementation With One Unused Element
If we use an array for our data, errors will occur with using a regular array (as the data can't move, you will eventually run out of space) and if we shift the array, it would be too costly (wayyy too many operations). Thus, we will use a circular array as depicted below for our queues.
To add an entry, set backIndex = (backIndex + 1) % array.length and add the entry at that index. To remove an entry, simply set the front index to null and set frontIndex = (frontIndex + 1) % array.length. For this implementation, one space in the array will be left unused to differentiate between when the array is full (condition is frontIndex == (backIndex + 1) % array.length) and empty (condition is frontIndex == backIndex).
class ArrayQueueWithOneUnusedElement<T> implements QueueInterface<T> {
private int frontIndex;
private int backIndex;
private T[] array;
public ArrayQueueWithOneUnusedElement(int capacity) {
this.array = (T[]) new Object[capacity+1];
}
public void enqueue(T newEntry) throws FullQueueException {
if(isFull()) throw new FullQueueException();
array[backIndex] = newEntry;
backIndex = (backIndex + 1) % array.length;
}
public T dequeue() throws EmptyQueueException {
if(isEmpty()) throw new EmptyQueueException();
T removed = array[frontIndex];
array[frontIndex] = null;
frontIndex = (frontIndex + 1) % array.length;
return removed;
}
public T getFront() throws EmptyQueueException {
if(isEmpty()) throw new EmptyQueueException();
return array[frontIndex];
}
public boolean isEmpty() {
return frontIndex == backIndex;
}
public boolean isFull() {
return frontIndex == (backIndex + 1) % array.length;
}
public void clear() {
frontIndex = backIndex;
this.array = (T[]) new Object[this.array.length];
}
}
Array-Based Implementation With No Unused Elements
The Array-Based Implementation above uses one unused element because it needs to differentiate when the array is filled and empty. If you do not care about this functionality or are willing to use a little bit of a work-around by using an int size (shown below as well), you can use this implementation.
class ArrayQueueWithNoUnusedElements<T> implements QueueInterface<T> {
private int frontIndex;
private int backIndex;
private T[] array;
private int size;
public ArrayQueueWithNoUnusedElements(int capacity) {
this.array = (T[]) new Object[capacity];
}
public void enqueue(T newEntry) throws FullQueueException {
if(isFull()) throw new FullQueueException();
array[backIndex] = newEntry;
backIndex = (backIndex + 1) % array.length;
size++;
}
public T dequeue() throws EmptyQueueException {
if(isEmpty()) throw new EmptyQueueException();
T removed = array[frontIndex];
array[frontIndex] = null;
frontIndex = (frontIndex + 1) % array.length;
size--;
return removed;
}
public T getFront() throws EmptyQueueException {
if(isEmpty()) throw new EmptyQueueException();
return array[frontIndex];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == array.length;
}
public void clear() {
frontIndex = backIndex;
this.array = (T[]) new Object[this.array.length];
size = 0;
}
}
Ensure/Expand Capacity for Array-Based Implementations
What if I want the Array-Based to be expandable with any amount of elements? Well the -ensureCapcity(): void method will help.
private void ensureCapcity() {
if (isFull()) {
T[] oldArray = array;
array = (T[]) new Object[array.length * 2];
for (int i = 0; i < oldArray.length; i++) {
System.out.println(oldArray[frontIndex]);
array[i] = oldArray[frontIndex];
frontIndex = (frontIndex + 1) % oldArray.length;
}
frontIndex = 0;
backIndex = oldArray.length - 1;
}
}