Queue

The queue is a fundamental data container in which are the stored  elements removed (polled) in the same order as they were inserted into the structure (enqueued). This principle is called FIFOfirst in, first out. The opposite approach LIFOlast in, fist out – is used in the stack data structure.

A special type of a queue is a priority queue, in which are the elements polled in the order defined by their priority.

Typical operations

Queue
Queue
  • addLast (enqueue) – Put the element into the queue.
  • deleteFirst (poll, dequeue) – Get and remove the first element (head) of the queue.
  • getFirst (peek) – Get the first element of the queue.
  • isEmpty – Query whether the queue does not contain any element.
  • size – Return the number of contained elements.

Usage

In computer science the queue is widely used, for example in these applications:

  • Synchronization primitive in multi-threaded applications
  • Unix pipe operator used for interprocess communication
  • Circular buffer – buffer for data streams
  • Heapsort – a sorting algorithm based on a priority queue

Code

 

/**
 * Queue - implemented as a linked list
 */
public class Queue {
    private Node first;
    private Node last;
    private int size;
    public Queue() {
        this.size = 0;
    }

    /**
     * Insert the element at the end of the queue
     * @param i element
     */
    public void addLast(int i) {
        Node n = new Node(i);
        if(getSize() == 0) {
            this.first = n;
            this.last = n;
        } else {
            this.last.next = n;
            this.last = n;
        }
        size++;     
    }

    /**
     * Remove the first element
     * @return element
     */
    public int deteteFirst() {
        if(getSize() == 0) throw new IllegalStateException("Queue is empty");
        int value = first.value;
        first = first.next;
        size--;
        return value;
    }
    /**
     * Return the first element
     * @return element
     */
    public int getFirst() {
        if(getSize() == 0) throw new IllegalStateException("Queue is empty");
        return first.value;
    }
    /**
     * Get number of contained elements
     * @return lenght of the queue
     */
    public int getSize() {
        return size;
    }
    
    /**
     * Query, whether is the queue empty
     * @return true if the queue is empty, false otherwise
     */
    public boolean isEmpty() {
        return this.size == 0;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node curr = first;
        for(int i = 0;  i < this.size; i++) {
            builder.append(curr.value).append(" ");
            curr = curr.next;
        }
        return builder.toString();
    }  

    /**
     * Inner representation of the element (node of the linked list)
     */
    private class Node {
        private int value;
        private Node next;
        private Node(int value) {
            this.value = value;
        }
    }    
}