A queue is a simple data structure based on First In, First Out (FIFO) principle, where the longer an item has waited, the sooner it will be available.

It is based around the fundamental queue paradigm that we're familiar with: front of the line goes first.

A queue has a head and a tail. We dequeue by removing an element from the head of the queue and enqueue by adding an element to the tail.

Diagram of a Queue

A queue supports the following operations in its typical form:

Operation Pseudocode Description
head HEAD(q) Return element at the head of queue q.
dequeue DEQUEUE(q) Remove and return element at the head of the queue.
enqueue ENQUEUE(o, q) Adds element o to the tail of the queue.
isEmpty? EMPTY(s) Return boolean result of is empty check.
new empty queue new QUEUE q Create a new, empty queue.

Recommended Reading

Introduction to Algorithms, Third Edition

Intro to Algorithms cover

Chapter 10 covers Elementary Data Structures like a Stack or Queue.