# Implement a Queue

## Problem

Write an efficient `Queue<T>`

a FIFO datastructure offers `Enqueue`

and `Dequeue`

operations.

### Example

```
var q = new Queue<int>();
q.Enqueue(10);
q.Enqueue(3);
q.Dequeue();
q.Enqueue(4);
q.Enqueue(5);
```

## Analysis

**Queue** is a `FIFO`

data structure; items added and removed in first-in0first-out order. In different word insertion and deletion happens on two different ends.

There are several methods to implement queues, each with different Time and Space Complexity. assuming that the data structure will support two main operations `Enqueue`

and `Dequeue`

### Method 1 - Array based Queue

In this approach, we will use a fixed length array to store the queue elements, and two pointers, `head`

to point at the first item in queue to be removed on calling `Dequeue`

and `tail`

pointing at the next empty position in the queue. with Every enqueue operation we will move the tail pointer to next empty position, and with every dequeue we will decrement the head pointor to point at the next item in line. we will also keep a size varible to assist in determinig if the queue is full by comparing to initial capacity.

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

Enqueue | O(1) |

Dequeue | O(1) |

Remove | n/a |

**Note** Arrays are fixed length data structure, dequeuing items from the queue will leave empty spots in the array not utilized which will lead to wasted space, a more efficient approach is to build a circular array, wraps around to the first position. The `Size`

variable will be key in this approach since it will be used to determine if there are space left in the array to wrap around .

### Method 2 - LinkedList based Queue

**Linked List** is a very efficient and flexiable data structure, it will gives time complexity of `O(1)`

for both adding and removing just like arrays. and also will enable us to change the queue items in the middle (although not usually needed operation).

**Note** Theoritically Arrays and LinkedLists will give you `O(1) head and tail inserts and deletes which in turns works very well for implementing a queue. But practically the overhead of an array is much less than linkedlist. Array is much more efficient data structure in memroy than a linkedlist.

**Notice** using LinkedList to store data internally for the queue, enabled me to implmement `Remove(T item)`

method, the method will run in O(K) where k number of elements iterated until match found.

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

Enqueue | O(1) |

Dequeue | O(1) |

Remove | O(k) |

### Bouns - Implement a Queue using two stacks

This is not a usual method to implement queues since it’s not efficent for both Time and Space Complexity! but it’s a fun problem to play with. if we are given two `Stack<T>`

how can we implement a queue. `Stack`

is the oppsite data strucuture of queue. Last-in-First-Out or **LIFO**

We will use one Stack for `Enqueue`

operation, which will be very fast operation `O(1)`

, and we will use the other stack to handle `Dequeue`

this will make the operation more costly in terms of time complexity. here are the steps:

- If enqueue and dequeue stacks are emtpy then queue is empty return
`default(T)`

- If dequeue stack has values then
`pop`

value from dequeue stack and return it. - if dequeue stack has no values
- while enqueue stack is not empty,
`pop`

items from enqueue stack and`push`

to dequeue stack

- while enqueue stack is not empty,
`pop`

item from dequeue stack

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

Enqueue | O(1) |

Dequeue | O(k) |

Remove | n/a |

*Happy Coding!*

## Leave a Comment