Queue

A queue is a FIFO (First In First Out) data structure. It is extensively used in programming in algorithms such as Breadth-First Search and in scheduling where first-come-first-serve is desired.

A queue acts very much like a line does in real life. Barring any "cuts" the first person to get in line will be the first person to get out of line. This kind of behavior is best implemented by a linked list which gives a queue the following complexities:

Operation Complexity Description
push $O(1)$ puts an element on the back of queue
pop $O(1)$ removes an element from the front of queue

Here, we will put 4 numbers in a queue and have them print them back.

import java.util.*;
 
public static void main (String[] args) throws IOException {
 
    // Queue is the abstract type. For this example, we shall use a 
    // simple linked list as our queue
    Queue q = new java.util.LinkedList();
    // Let's put in 4 numbers
    q.offer(0);
    q.offer(1);
    q.offer(2);
    q.offer(3);
    // Let's print them out
    for(int i=0; i<4; i++) {
        System.out.print(q.poll() + " ");
    }
    // We should have gotten: 0 1 2 3
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License