DS: Queues

• A queue is a data-structure that, unlike a stack, follows the First-In First-Out (FIFO) principle. Think of it as a line to a ride at an amusement park. The people in the front of the line will get to the ride first, because they got to the line first.

• There are five types of queues: Simple, Circular, Priority, Double-ended (or Deques), & Monotonic.

• Queues support the following operations: enqueue(add to end), dequeue(removes and returns first element), peek(returns first element), isEmpty(checks if any elements exist), and size(gets number of elements).

Simple Queues

• Simple queues are simply queues where insertion takes place at the rear and removal occurs at the front.

Circular Queues

• Circular queues are queues implemented by Circular Linked-Lists.

Priority Queues

• Priority Queues are queues where the element with the most priority will be the first to get out of the queue, then the one with the next highest priority, and so on. Priority can be defined in many ways, i.e the number that is higher/lower or an object with a higher/lower specific score, etc.

Double-ended Queues (Deques)

• Double-ended Queues (Deques) are queues that allow adding & removing elements from both front and back.

Monotonic Queues

• Monotonic Queues are dequeues used for storing elements in a specific order to solve sliding-window problems(i.e if you want to track the min/max of all contiguous k-sized sub-arrays of an array, etc).