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.
Here are the key operations that are available in the queue
|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.head = None 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(): self.head = node else: self.tail.next = node self.tail = node self.size = self.size + 1 def dequeue(self): if not self.isEmpty(): n = self.head self.head = self.head.next 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)