Share
Explore BrainMass

Priority Queues

people queued around several corners

priority queue is much like a normal queue in that it is an abstract data type for ordering elements. However, in this version of a queue, elements in the list/map are assigned priority values and those with the higher priorities always are served/processed before those with lower ones. In the case that two or more elements have the same priority value, they will be served with as a stack (last-in; first-out order) or a normal queue (first-in; first-out). 

Priority queues can be implemented using a heap, among other methods, but it is not only a heap. It must facilitate the following operations that are not required for a basic heap (the first two are fundamental; the others, useful):

  • insert an item with a priority value assigned
  • retrieve the item with the highest priority
  • query the priority of any item in it
  • change the priority of an item
  • reverse all priorities
  • compare the priorities of two items (including how to deal with equal priorities, as mentioned above)

Priority queues are especially useful for when resources are limited. For example, with limited bandwidth on a transmission line from a network router, priorities can ensure that the most important traffic is sent first and is therefore the least likely to be rejected for surpassing maximum capacity. Priorities can also sometimes act as 'weights' on items, helping with projects where strict budgets make it desirable to buy the most important things first.

 

[ Photo credit Yves Tennevin ]

Stacks Problem

1. Suppose there is a program that reads a word and writes the reverse of the word to to output. For example, the program reads "faced" and writes "decaf". The program uses a stack to reverse the string. Please list all activation of the push and pop methods along with which letter is being pushed or popped at each step if the i

System Administrator

1. As a system administrator you have noticed that usage peaks between 10:00AM to 5:00PM and between 7:00PM to 10:00PM. The company's CEO decided to call on you to design a system where during these peak hours there will be three levels of users. Users in level 1 are to enjoy better response time than users in level 2, who in tu