Operations on Simple Queue : Algorithms and their analysis

A simple queue supports several key operations, each with its own algorithm and time complexity. Below are the primary operations along with their algorithms and analysis.

1. Enqueue Operation

Description: Adds an element to the rear of the queue.

Algorithm:

void enqueue(Queue* q, int value) {
if (isFull(q)) {
printf(“Queue is full!\n”);
return;
}
q->rear = (q->rear + 1) % MAX; // Circular increment
q->items[q->rear] = value;
if (q->front == -1) { // Queue was empty
q->front = 0;
}
}

Time Complexity: O(1)
Analysis: The enqueue operation is efficient, taking constant time because it only involves updating the rear index and adding the new element.

2. Dequeue Operation

Description: Removes an element from the front of the queue.

Algorithm:

int dequeue(Queue* q) {
if (isEmpty(q)) {
printf(“Queue is empty!\n”);
return -1; // Indicating empty queue
}
int value = q->items[q->front];
if (q->front == q->rear) { // Queue becomes empty after dequeue
q->front = -1;
q->rear = -1;
} else {
q->front = (q->front + 1) % MAX; // Circular increment
}
return value;
}

Time Complexity: O(1)
Analysis: The dequeue operation also runs in constant time, as it simply involves updating the front index and returning the element.

3. Peek Operation

Description: Returns the element at the front of the queue without removing it.

Algorithm:

int peek(Queue* q) {
if (isEmpty(q)) {
printf(“Queue is empty!\n”);
return -1; // Indicating empty queue
}
return q->items[q->front];
}

Time Complexity: O(1)
Analysis: The peek operation is efficient, requiring constant time since it only accesses the element at the front index without modifying the queue.

4. IsEmpty Operation

Description: Checks if the queue is empty.

Algorithm:

bool isEmpty(Queue* q) {
return q->front == -1;
}

Time Complexity: O(1)
Analysis: This operation is also efficient, requiring constant time to check if the front index is set to -1.

5. IsFull Operation

Description: Checks if the queue is full.

Algorithm:

bool isFull(Queue* q) {
return (q->rear + 1) % MAX == q->front;
}

Time Complexity: O(1)
Analysis: This operation runs in constant time, as it simply checks the condition based on the front and rear indices.

Time Complexity Summary of Queue Operations

Operation	Time Complexity
Enqueue	O(1)
Dequeue	O(1)
Peek	O(1)
IsEmpty	O(1)
IsFull	O(1)

Space Complexity Summary of Queue Operations

Operation	Space Complexity
Enqueue	O(n)
Dequeue	O(n)
Peek	O(n)
IsEmpty	O(n)
IsFull	O(n)