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 FIFO – first in, first out. The opposite approach LIFO – last 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

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

Java

/**
 * 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;
        }
    }    
}

Typical operations

Usage

Code

Doporučujeme