A queue is First-In-First-Out (FIFO) data structure. New elements are inserted at rear (enqueue), and existing elements are removed from the front (dequeue). Both enqueue and dequeue operation have O(1) complexity. Queue can be implemented with array, linked list or stacks.

In this post, linked list is used to implement queue. Linked list is preferred because it is flexible to add and remove elements.  Array is not recommended because it wastes a lot of space if there are many adds and removes. However array can be efficient to implement circular queue. Deque is a queue that can be enqueue and dequeue at both end. It is implemented in doubly linked list.

Part 1 – Queue implementation
Part 2 – Circular queue implementation with array
Part 3 – Circular queue as circular linked list
Part 4 – Deque as doubly linked list

### Enqueue

Using linked list, first we need to define a queue node. This class has variables of data and next. Next we define the queue class. It has three class variables: front, rear and length. The front is a pointer to the first node. The rear is a pointer to the last node. The length is to track the length of the list.

The enqueue operation is to add an element at the rear. If the queue is empty, we points both front and rear to the new node. If it is not empty, we simply add the new node to the rear.

## Doodle

### Dequeue

The dequeue operation is to remove the first node from the queue. First we check whether the queue is empty. If it is empty, the method should return. In this implementation, we simply move the front pointer to the next node. The “removed” node is still in the list without accessible until the linked list is removed from the memory.

## Python

### Peek

Peek is to return the value of the first node. The same as dequeue, we should check whether the queue is empty. If it is not empty, return the value.

## Python

### Print

Print is to print all elements in the queue. Starting from the front node, a while loop is used to iterate through each node till to the rear in the list.