thesarfo

Reference

Queue: FIFO Operations

How a queue's enqueue, dequeue, and peek operations work, tracked with FRONT and REAR pointers.

views 0

A queue follows First In First Out (FIFO): the item that goes in first is the item that comes out first. Putting items in is called enqueue; removing items is called dequeue.

Basic Operations

A queue is an abstract data structure (ADT) that supports:

  • Enqueue — add an element to the end of the queue.
  • Dequeue — remove an element from the front of the queue.
  • IsEmpty — check if the queue is empty.
  • IsFull — check if the queue is full.
  • Peek — get the value at the front without removing it.

Working of a Queue

  1. Two pointers, FRONT and REAR, are used.
  2. FRONT tracks the first element of the queue.
  3. REAR tracks the last element of the queue.
  4. Initially, both FRONT and REAR are set to -1.

Enqueue

  1. Check if the queue is full.
  2. For the first element, set FRONT to 0.
  3. Increase the REAR index by 1.
  4. Add the new element at the position pointed to by REAR.

Dequeue

  1. Check if the queue is empty.
  2. Return the value pointed to by FRONT.
  3. Increase the FRONT index by 1.
  4. For the last element, reset FRONT and REAR to -1.

Complexity

Enqueue and dequeue on an array-backed queue are O(1). If you use pop(n) in Python, the complexity can be O(n) depending on the position of the item being popped.