byte sized c++

Queue

17.4 - Priority queue basic 1

Imagine that you are an office drone working in a company where the hierarchy matters a lot. You are in a line waiting in the company's cafeteria to get lunch. Suddenly your boss comes along and jumps ahead you straight to the front. Then the CEO of the company comes and skips straight to the front of the line.

The thing with that queue is that the order of being served does not depend on who comes first, it depends on who has the most priority. In the above scenario the priority might be like this:

• Level 60 CEO
• Level 30 boss
• Level 1 crook (you!)

Note that while the line may not necessarily in order (e.g. it could go from 5, 3, 4, 1, 2), the front of the line will always be the element with the highest priority (or lowest if it is a min-priority queue). After the element with the largest priority is removed (popped), the queue will readjust to make sure that the foremost element is the one with the highest priority again.

Priority queue has these operations:

• push, which inserts an element to the queue then readjust the positions.
• pop, which removes the element with the highest priority then readjust the positions.
• top, which returns the element with the highest priority.
• empty, which returns whether the queue is empty or not.
• size, which returns the number of elements stored in the queue.

Like queue, priority queue is also available from the header.

Your task is to create an interactive program using an integer priority queue which accepts the following commands:

• push
  Push the number into the queue.
• pop
  Remove the highest number.
• top
  Prints the highest number.
• empty
  Print true or false whether the queue is empty or not.
• size
  Print the size of the queue.

Sample input

push 80
push 30
push 90
size
top
pop
size
empty
top
pop
top
pop
size
empty

Sample output

3
90
2
false
80
30
0
true