Queues：练习题

What principle governs the way data is added to and removed from a queue data structure?

A standard linear queue is implemented in a program. If the following sequence of operations is performed on an initially empty queue, what value will be returned by the next DEQUEUE operation?

ENQUEUE(12)
ENQUEUE(24)
DEQUEUE()
ENQUEUE(36)

A circular queue is implemented in an array of size 8 (indices 0 to 7). The pointers are initialized as \( \text{Front} = 0 \) and \( \text{Rear} = -1 \). After performing three ENQUEUE operations and one DEQUEUE operation, what are the current values of the Front and Rear pointers?

When implementing a queue using a one-dimensional array, why is a circular queue implementation often preferred over a simple linear queue?

A circular queue is implemented using an array of size N. The queue uses integer pointers 'Front' and 'Rear' (representing indices) to track the elements. Which expression correctly indicates that the circular queue is full, assuming standard practice where one slot is kept empty to distinguish 'full' from 'empty'?

What is the primary operation used to add an item to a queue, and which end of the queue is this item added to?

Describe a typical real-world scenario in computer science where a Queue is the most appropriate data structure to manage tasks.

Given a circular queue implemented with an array of length \(L\), provide the calculation used to update the Rear pointer after a new item is enqueued, ensuring it wraps back to index \(0\) when necessary.

A circular queue is maintained in a one-dimensional array with 10 slots, using indices 0 to 9. The Front pointer currently stores the value 7 and the Rear pointer stores the value 2.
(a) Define the First-In, First-Out (FIFO) principle in the context of this queue. (1 point)
(b) Calculate the total number of items currently stored in the queue, showing your working. (2 points)
(c) Describe the state of the Rear pointer if three additional items are successfully enqueued. (1 point)
(d) Explain how a Linear Queue implementation would eventually fail to accept new items even if slots in the array are empty, and how the circular implementation solves this. (1 point)

A linear queue is implemented in an array Q of maximum size 10 (indices 0 to 9). The current state uses Front pointing to the index of the first item, and Rear pointing to the index of the last item. Initially, Front = -1 and Rear = -1.

(a) If 5 items are enqueued, and then 3 items are dequeued, determine the values of Front and Rear.

(b) Using the values calculated in part (a), describe the state of the queue array Q and explain why this implementation suffers from inefficient use of memory space.

(c) Propose two methods used in programming languages (including the use of specific data structures) to overcome the inefficiencies identified in part (b).