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		puts an element on the back of queue
pop		removes an element from the front of queue

Java

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
}

C++

Queues are built into C++, but you must include the correct header

#include <queue>

The following methods are available for queues:

void push(const TYPE&) //adds an element to back of queue
void pop() //removes an element from front of queue
TYPE& front() //returns first element in queue (next to be popped)
TYPE& back() //returns last element in queue (last to be pushed)
int size() //returns number of elements in queue
bool empty() //returns true if there are 0 elements

This example puts 5 elements on a queue and takes them back off

#include <iostream>
#include <queue>
 
using namespace std;
 
queue<int> q; //queue that holds integers
 
int main()
{
 
//this loop pushes 5 elements on the queue and tells you
//the size after each push
//the output is "1 2 3 4 5 "
for(int i=0; i<5; i++) {
    q.push(i);
    cout << q.size() << " ";
}
 
cout << endl;
 
//this loop pops elements off the queue until it is empty and tells you
//which one it is taking off
//the output is "0 1 2 3 4 "
while(!q.empty()) {
    cout << q.front() << " ";
    q.pop();
}
 
cout << endl;
 
return 0;
}