CompSci Lecture Mon 6th of April
Array Implementation of a Queue
Overview of Queue with Circular Array:
Implementation using an array structure which does not inherently change the array itself.
Instead, utilizes indices stored in additional fields (variables) to manage the array differently.
Characteristic of a circular array.
Key Properties
Fields of Circular Array Queue:
data: the actual array storing the elements.manyItems: tracks how many items are currently in the queue.front: index of the first element in the queue.rear: index of the last element inserted in the queue.
Functionality
The front and rear fields prevent unnecessary shifting of elements.
The only operation that may necessitate
O(n)time complexity is resizing the array if it becomes full, addressing limitations of using an array.
Adding and Removing Elements
Efficient Add and Remove:
Adding and removing elements does not require shifting, thanks to pointers for front and rear.
Example Initialization
Setup of Queue:
For a queue of capacity 10 (
data.length = 10), the indices range from 0 to 9.Assume
manyItemsis 5,rearis at index 2,frontis at index 8.
Contents of the Queue
Added in the following order: 6, 8, 4, 2, 14.
The first element (6) is at the front of the queue, meaning it will be dequeued first (FIFO principle).
Index Mapping:
front (index 8) -> 6rear (index 2) -> 8
Circular Behavior
Wrapping around:
If the current index reaches the end of the array and still