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