14. LinkedQueue

  • Given the definition of a queue, how can it be implemented?

    • Remember, the what and the how are separate

  • Things needed for the implementation

    • A container

    • A way to keep track of the front/head

    • A way to keep track of the rear/tail

    • A way to keep track of the size

14.1. Implementing a Queue with a Linked Structure

../../_images/linked_queue0.png

An example LinkedQueue containing four elements. Note that front and rear reference Node objects that have reference to the actual data stored in the queue.

../../_images/linked_queue1.png

The state of the LinkedQueue after an element was enqueued to the rear of the queue. Note that rear changed to reference a new Node containing the newly pushed element. The front was left unchanged after the enqueue.

../../_images/linked_queue2.png

The state of the LinkedQueue after an element was dequeued from the front of the queue. Note that front changed to reference the Node that was after the Node that contained the element at the front of the queue (the Node that was removed). The rear was left unchanged after the dequeue.

14.1.1. Edge Cases

  • What would the LinkedQueue look like if the queue is empty?

  • What if it only had one element?

14.2. Implementation

 5/**
 6 * Implementation of a queue with a linked structure as the container. The class contains a static inner class defining
 7 * a node for the linked structure.
 8 *
 9 * @param <T> Type of elements that are to be in the queue
10 */
11public class LinkedQueue<T> implements Queue<T> {
12
13    private Node<T> front;
14    private Node<T> rear;
15    private int size;
16
17    /**
18     * Create an empty LinkedQueue.
19     */
20    public LinkedQueue() {
21        front = null;
22        rear = null;
23        size = 0;
24    }

  • Like the Stack implementations, the LinkedQueue implements the Queue interface

  • The constructor creates an empty queue

  • Both front and rear reference null since there are no Node objects containing any elements

14.2.1. enqueue

29    @Override
30    public boolean enqueue(T element) {
31        Node<T> toEnqueue = new Node<>(element);
32
33        // If nothing is in the queue, then the front is null and the enqueued element will become the front. If the
34        // queue is not empty, the enqueued element is added after the current rear.
35        if (isEmpty()) {
36            front = toEnqueue;
37        } else {
38            rear.setNext(toEnqueue);
39        }
40        // Either way, the rear of the queue will be the newly enqueued element.
41        rear = toEnqueue;
42        size++;
43        return true;
44    }

  • The above enqueue method has some nuance to it

14.2.1.1. Enqueuing into an Empty Queue

  • This is an edge case

  • If the queue is empty, both front and rear reference null

  • When this is the case, the element being enqueued will end up being the only element in the queue

    • Thus, both front and rear need to reference the new Node containing the enqueued element

    • The new Node will be both the first and last thing in the queue

  • When looking at the code, this would result in

    1. Create a new Node with the element to be enqueued

    2. Set front to reference the newly added Node

    3. Update rear to reference the newly added Node

    4. Update size

14.2.1.2. Enqueuing into a Nonempty Queue

  • This is the general case

    • Notice how this is just adding to the rear of a linked structure

  • If the queue is not empty, both front and rear reference a Node

    • It is possible for front and rear to reference the same Node

    • This happens where there is only one element in the queue

  • When looking at the code, this would result in

    1. Create a new Node with the element to be enqueued

    2. Add the new Node after the current rear Node

    3. Update rear to reference the newly added Node

    4. Update size

  • What is the computational complexity of an enqueue?

14.2.2. dequeue & first

48    @Override
49    public T dequeue() {
50        if (isEmpty()) {
51            throw new NoSuchElementException("Empty queue");
52        }
53        T returnElement = front.getData();
54        front = front.getNext();
55        size--;
56        // The front will update correctly regardless. The rear must be set to null if the queue is now empty.
57        if (isEmpty()) {
58            rear = null;
59        }
60        return returnElement;
61    }
62
63    @Override
64    public T first() {
65        if (isEmpty()) {
66            throw new NoSuchElementException("Empty queue");
67        }
68        return front.getData();
69    }

  • Like LinkedStack and ArrayStack, trying to access something from the empty queue throws an exception

  • dequeue does a remove/delete from the front of a linked structure

  • Notice the edge case of a dequeue resulting in an empty queue

    • The update to the front will not be a problem

      • front = front.getNext() will set front to null since front.getNext() in this situation would return null

    • The trouble is with rear — typically rear is left alone with a dequeue

    • However, if the dequeue resulted in an empty queue, rear would be left referencing the Node that was just removed

    • The solution is to simply set it to null if the stack is empty after the dequeue

Note

Although not true in general, with the provided implementation of the LinkedQueue, missing this edge case in the dequeue would not actually cause a problem since the enqueue was written such that it also checks for the empty case.

  • What is the computational complexity of a dequeue?

14.3. Queue Variation — Priority Queue

  • Think of triage at a hospital

  • It somewhat operates on a first-come-first-served basis

  • But if someone is there for a cut thumb and someone else comes in with an arrow sticking out of their knee, they will be helped first

  • In other words, it’s first-come-first-served, but those with a priority value deemed more important will jump the line

14.3.1. What

  • Everything would be the same except dequeue

  • It would need to get the element with the most important priority of all those in the queue

    • If there is a tie, then use first-come-first-serve to break the tie

14.3.2. How

  • There is an implementation decision to be made

  1. On enqueue, insert the element into the queue such that the queue is always ordered based on priority and time of arrival

    • This requires a linear search to find the right place to insert

    • This would make enqueue \(O(n)\)

    • This makes dequeue \(O(1)\) since it simply removes from the front of the queue

  2. On dequeue, search for and remove the element with the most important priority

    • This requires a linear search to find the element to remove

    • This would make dequeue \(O(n)\)

    • This makes enqueue \(O(1)\) since it simply adds to the rear of the queue

  • Which implementation is better?

14.4. For Next Time

  • Read Chapter 5 Section 6

    • 6 pages

14.4.1. Playing Code

 1import java.util.NoSuchElementException;
 2
 3public class PlayingLinkedQueue {
 4    public static void main(String[] args) {
 5        // Create a LinkedQueue
 6        Queue<Integer> myQueue = new LinkedQueue<>();
 7
 8        // Check queue is empty
 9        System.out.println(myQueue.size());
10        System.out.println(myQueue.isEmpty());
11        System.out.println(myQueue);
12
13        // Test enqueue
14        myQueue.enqueue(0);
15        myQueue.enqueue(1);
16        myQueue.enqueue(2);
17        myQueue.enqueue(3);
18        myQueue.enqueue(4);
19        System.out.println(myQueue.size());
20        System.out.println(myQueue.isEmpty());
21        System.out.println(myQueue);
22
23        // Test enqueue more
24        myQueue.enqueue(10);
25        myQueue.enqueue(11);
26        myQueue.enqueue(12);
27        myQueue.enqueue(13);
28        myQueue.enqueue(14);
29        System.out.println(myQueue.size());
30        System.out.println(myQueue.isEmpty());
31        System.out.println(myQueue);
32
33        // Test first
34        System.out.println(myQueue.first());
35        System.out.println(myQueue.size());
36        System.out.println(myQueue.isEmpty());
37        System.out.println(myQueue);
38
39        // Test dequeue
40        System.out.println(myQueue.dequeue());
41        System.out.println(myQueue.dequeue());
42        System.out.println(myQueue.dequeue());
43        System.out.println(myQueue.dequeue());
44        System.out.println(myQueue.dequeue());
45        System.out.println(myQueue.dequeue());
46        System.out.println(myQueue.dequeue());
47        System.out.println(myQueue.dequeue());
48        System.out.println(myQueue.dequeue());
49        System.out.println(myQueue.dequeue());
50        System.out.println(myQueue.size());
51        System.out.println(myQueue.isEmpty());
52        System.out.println(myQueue);
53
54        // Test first and dequeue throwing exception
55        try {
56            myQueue.first();
57        } catch (NoSuchElementException e) {
58            e.printStackTrace();
59        }
60        try {
61            myQueue.dequeue();
62        } catch (NoSuchElementException e) {
63            e.printStackTrace();
64        }
65    }
66}