# Queue Data Structure

A

**queue**is a data structure that stores items in a*first in first out*(FIFO) order.An example of a queue is a line at a store register.

Let's say 3 people are waiting in line. The first person that entered the line is Bob. Then two others entered the line.

The next person up to pay at the register is Bob since he has been in the line the longest.

### Queue main operations

A queue has 2 main functions:

**Enqueue**- Add an item to the queue**Dequeue**- Remove the next item from the queue - the*first*item, or the one that has been in the queue the longest.

### Queue Big O Overview

Operation | Time |
---|---|

Enqueue | O(1) |

Dequeue | O(1) |

### Queue Implementation in Python

Under the hood, a queue is represented by a

**linked list**.The queue's

**enqueue**operation simply adds a node to the end of the*linked list*.The queue's

**dequeue**operation retrieves and removes the*head*of the*linked list*, or the first item in the list, which has been in the queue the longest.Since items can be added and removed from the queue in constant time, Python's

**dynamic array**is a great way to represent a queue.A

**deque**, or a double-ended queue, is a data structure that supports insertion and removal from*both*sides of the queue in*constant O(1)*time.In Python, we can also use the

`collections.deque()`

library to model a *queue*, which gives us those constant time operations.### Queue Pros

*Enqueue*, or adding items to the queue, takes constant time.- Similarly,
*dequeue*, or removing the next item from the queue, takes constant time. - Good for use cases such as tracking tasks to do in priority order, such as a todo list, or a background job.

### Queue Cons

The main con with queue is that it's not useful for iterating through items, as linked lists aren't

*cache friendly*, which means nodes won't necessarily be placed next to eachother in memory.It's better to just use a regular array, or dynamic array, if your data structure will primarily be accessed iteratively.

## 5 Essential Stacks & Queues Coding Interview Problems

Master Stacks & Queues by trying the coding challenges below.

- 1.Implement StackEasy
- 2.Implement QueueEasy
- 3.Max StackMedium
- 4.Valid ParenthesesMedium
- 5.Simplify PathMedium