# Queues

Queue is a container which supports first-in, first out (FIFO) order. Last weekend I went to a theater to watch a movie. In order to get the tickets I need to stand in the line. This line is called as the queue. I was the last member and this position is called as the tail of the queue. The ticket was issued to the person who stood first in the line. This position is called as the head of the queue. The queue is processed in the order in which the person arrived. Hence it is called as FIFO.

## Key Operations

Here are the key operations that are available in the queue

 Operation Description Time enqueue(e) Adds an element e to the tail of the queue O(1) dequeue() Removes the element e from the head of the queue O(1)

## Implementation of a Queue

A queue can be implemented by using an array or a linked list. I used linked list to implement it. The code is written in python.

```
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next

class Queue:
def __init__(self):
self.tail = None
self.size = 0

def size(self):
return self.size

def isEmpty(self):
return True if self.size == 0 else False

def enqueue(self, n):
node = Node(n)
if self.isEmpty():
else:
self.tail.next = node
self.tail = node
self.size = self.size + 1

def dequeue(self):
if not self.isEmpty():
self.size = self.size - 1
return n.data

```

## Problem 1: Josephus problem

Josephus was a Jewish historian who lived in the 1st century. During the Jewish-Roman war he was trapped in a cave with a group of 40 soldiers surrounded by the Romans. The group decided to suicide themselves instead of being captured by the Romans. They formed a circle and decided to kill every third remaining person until no one was left. Josephus, not keen to die, quickly found the safe spot in the circle and thus stayed alive.

The question is to write a program which returns the position to stand so that you are the only one to stay alive. The program will take 2 inputs N (no of people in the group) and K (every Kth man to be executed). Take a look at the image which explains the process with N = 12 and K = 2. Start counting from position 1.

This problem can be solved very easily using queues. I found this online tool very useful to test the program.

```def josephusProblem(l, k):
q = Queue()
for n in l:
q.enqueue(n)

while q.size > 1:
for i in range(k - 1):
q.enqueue(q.dequeue())
q.dequeue()

return q.dequeue()
```

## Problem 2: Traverse a tree level by level

Write a program to visit each node in a tree level by level. For the tree given below the program should output 1 2 3 4 5 6 7.

A simple class to represent a tree.

```class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
```

For the image here is the code to create the tree

```t = TreeNode(1, \
TreeNode(2, \
TreeNode(4), \
TreeNode(5), \
), \
TreeNode(3, \
TreeNode(6), \
TreeNode(7), \
), \
)
```

The code to traverse the tree level by level

```def traverseLevelByLevel(t):
q = Queue()
q.enqueue(t)
collect = ''
while not q.isEmpty():
n = q.dequeue()
collect = collect + str(n.data)
if n.left != None:
q.enqueue(n.left)
if n.right != None:
q.enqueue(n.right)
#print the contents
print 'Level by Level => ' + ' '.join(collect)
```