Queue

From DocForge

A queue is a data structure usually based off of a Linked List which maintains a order such that the newest items added to the queue are the last to be removed, (this behaviour is also know as a FIFO (first-in,first-out) list). Adding something to the queue is said to "push" the queue, and removing an item is said to "pop" the queue. A Queue can be likened to a line (ie. Queue) at an amusement park. The first person in line gets to the ride first, and the last person in line gets to the ride last (usually). To see what's next in the queue without removing it (which would destroy the ordering) you can "peek" at the queue. A short header of what a queue is all about is here:

abstract class Queue {
    public abstract void push(Object e);
    public abstract Object pop();
    public abstract Object peek();
}

A paramaterized version follows:

abstract class Queue<T> {
    public abstract void push(T e);
    public abstract T pop();
    public abstract T peek();
}

[edit] Priority Queues

A priority queue is like a queue, except certain items have the ability to cut in front of other items depending upon conditions defined by the programmer. Think of it sort of like the lines at the amusement park, only now the Chairman of the Board that owns the park steps in line. Naturally, the security guys kick the other people out of their place to let the big cheese go up in front. All elements in a priority queue must be comparable, otherwise it is impossible to infer an ordering based on them. In Java you will have to ensure that each element in the queue implements Comparable, which means that you will have to write a compareTo method for each object. In a language like C++ or Digital Mars D you could overload the comparator operator to do this, or else use a delegate function to perform ordering comparisons.