Question

4. Priority queues are very useful structures. Outline a scheme that lets a priority queue function as a FIFO queue. 5. Priority queues are very useful structures. Outline a scheme that lets a priority queue function as a stack.

Answer 1

Priority queues have three basic operations:

1. IS_EMPTY() : returns whether the queue is empty
2. INSERT(value, priority) : inserts a new element with the given priority into the queue
3. PULL() : removes and returns the element with the highest priority in the queue

Based on these basic operations, stack and FIFO queue can be implemented using a priority queue. This will require a global counter to assign the priority to a new element that goes in.

Answer 4.

In a FIFO queue, the first element to go in is the first to come out. Therefore in terms of priority, if element A comes before element B, then A must have a higher priority. This can be implemented as follows:

The FIFO-QUEUE must have a global value priority initialized to MAX_VALUE, which is a very high value, or the highest value if there is a maximum value for priority. For every enqueue operation, this value is updated. The pseudo code for the various operations is given below.

A FIFO-QUEUE is made up of a priority queue Q and a value priority:

INITIALIZATION:

• Q = EMPTY
• priority = MAX_VALUE

IS_EMPTY():

• Return Q.IS_EMPTY()

ENQUEUE(value):

• Q.INSERT(value, priority)
• Decrement priority by 1

DEQUEUE()

• Value v = Q.PULL()
• If Q.IS_EMPTY() then set priority := MAX_VALUE
• Return v

Answer 5

Stack is a LIFO structure. Using a priority queue, it can be constructed similar to a FIFO queue, but here, the last element inserted must have the highest priority. This is accomplished as follows:

A STACK consists of a priority queue Q and a value priority:

INITIALIZATION:

• Q = EMPTY
• priority = 0

IS_EMPTY():

• Return Q.IS_EMPTY()

PUSH(value):

• Q.INSERT(value, priority)
• Increment priority by 1

POP()

• Value v = Q.PULL()
• If Q.IS_EMPTY() then set priority := 0
• Return v