Stack, queue, priority queue #

Some abstract data types impose strong limitations on the set of operations allowed on a collection. These limitations provide opportunities for specialized implementations (i.e. specialized data structures), which can be very efficient in some contexts.

Stack #

A stack (or Last In First Out queue or LIFO queue) simulates a collection organized as a physical stack (for instance a stack of plates).

A stack exposes three main methods:

• push adds an element to the collection,
• pop removes and returns the most recently added element,
• isEmpty is self-explanatory.

Queue #

A queue (or First In First Out queue or FIFO queue) simulates a collection organized as physical queue (for instance a waiting line).

A queue exposes three main methods:

• enqueue (or add) adds an element to the end of the queue,
• dequeue (or poll) removes and returns the earliest enqueued element,
• isEmpty is self-explanatory.

Priority queue #

A priority queue simulates a collection equipped with a total preorder, so that only (one of) the element(s) with highest priority can be retrieved.

A priority queue exposes three main methods:

• insert adds an element to the collection,
• getMaximumElement removes and returns an element with highest priority,
• isEmpty is self-explanatory.

Note. A regular queue can be viewed as a specific case of priority queue, where each inserted element has (strictly) lower priority than the previous one.