📦

Implementing a Queue Data Structure

Nov 17, 2024

Queue Data Structure Implementation

Introduction

  • The queue can be implemented using various data structures:
    • Arrays
    • Linked Lists
    • Stacks

What is a Queue?

  • Queue is a collection/list where:
    • Insertion (enqueue) is possible from one end (rear)
    • Deletion (dequeue) is possible from the other end (front)

Implementation Using Arrays

  1. Static Memory Allocation

    • Specify the size of the queue (capacity)
    • Enforce FIFO (First In First Out) rule
    • Time complexity for enqueue and dequeue operations must be O(1)

  2. Array Declaration

    • Example: int q[n]; (where n is the size of the array, defined as a macro)

  3. Global Variables

    • Front and rear variables initialized to -1 for empty queue:
      • int front = -1;
      • int rear = -1;

Enqueue Operation (nq Function)

  • Conditions to Check:

    1. Overflow Condition: If rear == n - 1, queue is full.
    2. Empty Queue Condition: If both front and rear are -1.
    3. Insertion into Non-empty Queue:
      • Increment rear and insert the value.

  • Code Example:

if (rear == n - 1) { printf("Queue is full"); } else if (front == -1 && rear == -1) { front = rear = 0; } else { rear++; } q[rear] = x;

Dequeue Operation (dq Function)

  • Conditions to Check:

    1. Empty Queue: If both front and rear are -1.
    2. Only One Element: If front == rear, reset both to -1 after dequeue.
    3. More than One Element: Increment the front pointer.

  • Code Example:

if (front == -1 && rear == -1) { printf("Queue is empty"); } else if (front == rear) { front = rear = -1; } else { front++; }

Display Function

  • Check if the queue is empty, then print the elements of the queue using a loop.
  • Code Example:
if (front == -1 && rear == -1) { printf("Queue is empty"); } else { for (i = front; i <= rear; i++) { printf("%d ", q[i]); } }

Peek Function

  • Check the front value of the queue without removing it.
  • Code Example:
if (front != -1) { printf("The front element is: %d", q[front]); }

Drawbacks of Array Implementation

  • If all elements are dequeued, the rear pointer still points to the last position, causing an overflow condition even if space is available.
  • Circular Queue: Modify the implementation to use circular indexing (e.g., rear = (rear + 1) % n).

Conclusion

  • Next video will cover the implementation of a queue using linked lists.

Full transcript