Queue implementation is using underlying data structures (linked list, array) to implement enqueue and dequeue. A queue is a First-In-First-Out (FIFO) data structure. New elements are inserted at the rear (enqueue), and existing elements are removed from the front (dequeue). Both enqueue and dequeue operation have O(1) complexity.

In this post, the linked list is used to implement a queue. A 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, an array can be efficient in implementing a circular queue. Deque is a queue that can be enqueued and dequeued at both ends. It is implemented in a doubly linked list.

### You are here

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

### Enqueue

Using a 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 point 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 being 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.