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 manyItems is 5, rear is at index 2, front is 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) -> 6

    • rear (index 2) -> 8

Circular Behavior
  • Wrapping around:

    • If the current index reaches the end of the array and still