Implementation of the Queue is so similar to a Stack. We operate with the queue using a FIFO-approach: add elements to the end (tail) of the queue and retrieve (poll) from the head.
General points of the algorithm:
- Store the head and tail in the class fields.
- Implement the add(…) method to extend the queue and poll() methods to retrieve the first (head) element.
- add(…) appends the queue and assigns the tail to the previous node.
- poll() method retrieves the head element and reassigns the new head to the previous element.
- Time complexity: O(1) for the add(..) and poll() methods.
- Space complexity: O(1) for the add(…) and poll() methods.
public class ImplementQueue {
private static class Queue<T> {
private Node<T> head;
private Node<T> tail;
private static class Node<T> {
private final T value;
private Node<T> prev;
public Node(T value, Node<T> prev) {
this.value = value;
this.prev = prev;
}
}
public void add(T value) {
var node = new Node<>(value, null);
if (head == null) {
head = node;
} else {
tail.prev = node;
}
tail = node;
}
public T poll() {
if (this.tail == null) {
throw new IllegalArgumentException("The stack is empty");
}
var node = this.head;
this.head = this.head.prev;
return node.value;
}
}
public static void main(String[] args) {
var stack = new Queue<Integer>();
stack.add(1);
stack.add(2);
stack.add(3);
stack.add(4);
System.out.println(stack.poll());
System.out.println(stack.poll());
System.out.println(stack.poll());
System.out.println(stack.poll());
System.out.println(stack.poll());
}
}