implement a Queue using a BST

Question

How do i implement a Queue using a BST.

Is this the way to do it, keep on inserting the nodes in the tree while maintaining a count value associated with each and every node,but while deletion BST should work like queue(FIFO) so start deleting from BST with the node having lowest count value in the tree.

Did i get the question and solution right? If not,then please explain me the question.

Answer 1

A BST is really an inappropriate data structure to use to back a queue. You really ought to use a linked list instead, because it would be way faster, less complicated, and plain old better.

However, if you insist on using a BST...

You would use the BST as a priority queue, and define a wrapper type that also holds a 'queue index', which is what the items would be sorted by. You would have to define the comparison to take into account the current queue index though, because otherwise you could only ever add as many items as the difference between the highest and lowest values of your index type.