A queue follows FIFO (first in first out). In a queue, elements are added and removed from opposite sides.
- There is also a data structure called a deque, short for double-ended queue, and pronounced “deck”. In a deque, you can add or delete elements from both ends.
Adding to a queue is called enqueue and deletions are called dequeue.
A doubly linked list that maintains pointers to the head and tail (both ends, usually with sentinel nodes) can implement an efficient queue.
For algorithm problems, queues are less common than stacks, and the problems are generally more difficult. The most common use of a queue is to implement an algorithm called breadth-first search (BFS). Outside of BFS, unlike stack, there aren’t many problems whose main focus is a queue.