This question tests the following learning outcomes:

• Apply stacks, queues and priority queues and algorithmic techniques to efficiently solve computational problems.
• Explain in a clear and succinct way how an algorithm or data structure works, and its assumptions, in order to communicate with peers.
• Write readable, tested and documented Python functions and classes to implement algorithms and abstract data types.

This question is about an application that implements a priority queue for cinema customers awaiting the release of a new film. When customers buy an advance ticket they join the queue. When the film showings are confirmed, customers are allocated seats in the following priority order, from highest (priority value 1) to lowest (priority value 4):

1. Disabled
2. Member
3. Premier
4. Standard

Within each priority, seats are allocated in the order that customers joined the queue. When a customer is allocated a seat, they are removed from the queue.

(a) (10 marks)

Assume the application implements an unbounded min-priority queue.

A customer joins the queue behind all customers already queueing with the same priority. All customers with priority value 1 are queued in the order they joined, before all customers with priority value 2, and so on. The next customer to be allocated a seat will be the customer currently at the front of the queue. A customer is represented by a unique string.

For example, if customers join the queue in this order:

Customer	Priority value
Smith25	2
Thomson3	4
Tang18	1
Eber87	1
Green201	2

they will be queued in this order, where the left end is the front of the queue:

Complete the table below to help you decide whether to implement the queue as a dynamic array or a singly linked list.

Write your answer here

Question	Your Answer
Which operations are most frequently needed?
For the same queue, which implementation method uses less memory?
Are items shifted on insert/remove for a dynamic array?
Are items shifted on insert/remove for a linked list?

Given your answers above, would you implement the queue as a dynamic array or as a singly linked list? Briefly justify your answer. I would...