What is a Queue?

A queue is a linear data structure which models real world queues by having two primary operations, namely *enqueue* and *dequeue*

In a FIFO data structure, the first element added to the queue will be processed first.

As shown in the picture above, the queue is a typical FIFO data structure. The insert operation is also called enqueue (поставить в очередь) and the new element is always added at the end of the queue. The delete operation is called dequeue (снять с очереди). You are only allowed to remove the first element.

The FIFO property of a queue causes it to operate like a line of customers waiting to pay a cashier. The queue has a head and a tail. When an element is en- queued, it takes its place at the tail of the queue, just as a newly arriving customer takes a place at the end of the line. The element dequeued is always the one at the head of the queue, like the customer at the head of the line who has waited the longest.

Queues and Stacks can be effectively implemented using either arrays or linked lists. The key issue is whether an upper bound on the size of the container is known in advance, thus permitting the use of a statically-allocated array.

Queue Terminology

There does not seem to be consistent terminology for inserting and removing elements from queues.

Enqueue = Adding = Offering

Dequeue = Polling = Removing (means removing from the front of the queue unless you are tolled otherwise)

When and Where is a Queue Used?

Breadth First Search (BFS) graph traversal. In BFS queue is used to store a list of the nodes that we need to progress. Each time we process a node, we add its adjacent nodes to the back of the queue. This allows us to process nodes in the order in which they are viewed. So the processing order of the nodes is the exact same order as how they were added to the queue, which is First-in-First-out (FIFO). That's why we use a queue in BFS.
Any waiting line models a queue. For example a lineup at a movie theatre.
Can be used to efficiently keep track of the x most recently added elements.
Web server request management where you want first come first serve (FIFO)