QUEUES AND STACKS: ARRAY IMPLEMENTATION

Array Implementations

• Overview of Array Functions

  • Functions like adding and removing elements can impact performance.

  • Efficient operations are crucial for data structures like queues and stacks.

• Dequeue and Peak

  • Using a dequeue allows for more efficient operations compared to traversing the entire array for peak functionality.

  • Traversing from the beginning to the second-to-last element leads to a time complexity of O(n).

Stack Implementations

• Using Arrays for Stack

  • A stack implemented with an array uses a pointer (top) indicating if the stack is empty.

  • If the stack is empty:

    • Special marker (e.g., -1) is used to denote that nothing is present.

• Front and Rear Pointers in Queues

  • In a deque implementation, the left boundary (front) and right boundary (rear) mark the elements in the queue.

  • Moving the front pointer to the right after a removal operation reduces usable space, creating a gap.

Element Removal Handling

• Visualizing Element Removal

  • When an element is removed, pointers adjust:

    • Elements can shift left, or

    • Just move front when implementing removals.

  • After shifting, front points back to the start while rear updates to the new position.

Operations on Queue

• Enqueue Operation

  • Example for enqueue in a simple array with a fixed capacity (e.g., 5):

    • Pre-increment rear to point to a new available slot.

    • Access the indexed position of the array to store the new element.

  • Updating the rear pointer occurs after the shifting operation to reflect changes.

  • Enqueue operations may require checking if the queue is empty first to avoid unnecessary processing.

Challenges with Circular Arrays

• Handling Gaps in Circular Queue

  • When the front pointer shifts and creates empty spaces, the queue may fill up due to conceptual limits of fixed-array size.

  • Future enqueue operations may exceed available indices without dynamic sizing.

• Mapping Imaginary Indices to Actual

  • To implement circular functionality correctly:

    • Use a modulus operation:

      • Calculate the actual index by assessing the rear pointer’s position and capacity.

      • For example, if rear points to an imaginary index 5, correct its position back into the array using modulus with capacity.

  • This approach prevents out-of-bounds errors and manages element positioning effectively.

QUIZ 3