Queues: Practice Questions

In a priority queue, how is the position of an item determined when it is added to the structure?

A circular queue is implemented using an array of size 4 (indices 0 to 3). The queue currently contains the following data:
Index 0: [Empty]
Index 1: 'A'
Index 2: 'B'
Index 3: 'C'

If the front pointer is 1 and the rear pointer is 3, what happens to the rear pointer when item 'D' is added?

A priority queue is implemented using an ordered list where the highest priority item is at the front. If a new item with priority \(P\) is added, and there are currently \(n\) items in the queue, what is the worst-case time complexity for the add operation?

Which of the following operations is necessary to test if a linear queue implemented using a static array of size N is full?

A linear queue is implemented using a static array of size 6 (indices 0 to 5).

Initially, the queue is empty with front at 0 and rear at -1. The following operations occur:
1. Enqueue 'X', 'Y', 'Z'
2. Dequeue two items
3. Enqueue 'W'

What are the current values of the front and rear pointers?

Consider a linear queue implemented with a static array of size 10. After several additions and removals, the front pointer is at index 9 and the rear pointer is also at index 9. Explain why this queue might be reported as 'full' even if index 0 to 8 are empty.

A priority queue is used in a CPU scheduler. If three tasks with priorities 1, 5, and 3 (where 5 is the highest priority) are added in that order, what is the logical order in which they will be removed?

A Priority Queue is used to manage print jobs. Each job has a priority level (1 = High, 5 = Low).

a. If the queue contains jobs with priorities [3, 1, 4] in that order, which job will be removed first? (1 point)
b. Describe the steps to add a job with priority 2 to a priority queue implemented as an ordered list. (2 points)
c. How does the remove operation in a priority queue differ from that in a standard FIFO linear queue? (1 point)

A circular queue is implemented using a fixed-size array of 8 elements, indexed 0 to 7. The current state of the queue is as follows:
- front pointer: 6
- rear pointer: 1
- size: 4

a. Identify the indices of the array that currently contain data, assuming the rear pointer points to the last element added. (2 points)

b. Describe the steps involved in adding a new item to this circular queue. In your answer, include the specific calculations for updating the rear pointer using the MOD operator, given the array size of 8. (3 points)

c. Explain how a circular queue differs from a linear queue in terms of memory utilization. (2 points)