Queue Implementation Using Array

Implementing queue operations using an Array

Implementation

1

Initialize the Queue

Set front = -1 and rear = -1 to mark the queue as empty.

2

Check if the Queue is Empty

The queue is empty if front == -1 or front > rear.

3

Check if the Queue is Full

The queue is full if rear == SIZE - 1.

4

Enqueue Operation

  • If the queue is full, print an error message and exit.
  • If the queue is empty, set front = 0 to start tracking elements.
  • Increment rear by 1 and insert the new value at items[rear].
5

Dequeue Operation

  • If the queue is empty, print an error message and exit.
  • Retrieve the value at items[front].
  • Increment front by 1 to move to the next element.
  • If front > rear after the operation, reset both front and rear to -1 (queue is now empty).
6

Display Queue

  • If the queue is empty, print a message and exit.
  • Traverse the array from front to rear and print the elements.

Coding Implementation

//queueimplementationusingarray.c
#include <stdio.h>
#define SIZE 5

typedef struct {
int items[SIZE];
int front;
int rear;
} Queue;

void initializeQueue(Queue *q) {
q->front = -1;
q->rear = -1;
}

int isFull(Queue *q) {
return q->rear == SIZE - 1;
}

int isEmpty(Queue *q) {
return q->front == -1 || q->front > q->rear;
}

void enqueue(Queue *q, int value) {
if (isFull(q)) {
    printf("Queue is full. Cannot enqueue %d.\n", value);
    return;
}
if (isEmpty(q)) {
    q->front = 0; 
}
q->rear++;
q->items[q->rear] = value;
printf("Enqueued %d.\n", value);
}


int dequeue(Queue *q) {
if (isEmpty(q)) {
    printf("Queue is empty. Cannot dequeue.\n");
    return -1;
}
int value = q->items[q->front];
q->front++;

if (q->front > q->rear) {
    initializeQueue(q);
}
printf("Dequeued %d.\n", value);
return value;
}

void displayQueue(Queue *q) {
if (isEmpty(q)) {
    printf("Queue is empty.\n");
    return;
}
printf("Queue elements: ");
for (int i = q->front; i <= q->rear; i++) {
    printf("%d ", q->items[i]);
}
printf("\n");
}

int main() {
Queue q;
initializeQueue(&q);

enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
enqueue(&q, 40);
enqueue(&q, 50);
enqueue(&q, 60);// Queue is Full

displayQueue(&q);

dequeue(&q);
dequeue(&q);

displayQueue(&q);

enqueue(&q, 60); // Failed to reuse the vacated position
displayQueue(&q);

return 0;
}

Why Linear Queue Fails?

The above implementation is not practical because, when a linear queue is completely filled and some elements are dequeued, attempting to enqueue new elements into the vacant positions results in a 'Queue is Full' condition. This happens because the implementation does not reuse the vacated slots at the beginning of the array, even though space is available. This limitation is a key drawback of linear queue implementations.

Linear Queue Limitation Example:

Initial State (Enqueue):
[10, 20, 30, 40, 50] // front = 0, rear = 4

After Dequeue:
[ -, -, 30, 40, 50 ] // front = 2, rear = 4

Attempt to Enqueue:
// Fails as rear == SIZE - 1

Overcoming the Limitation of Linear Queues: Using Circular Queues

In a circular queue, when the rear pointer reaches the end of the array, it wraps around to the beginning. This allows the queue to efficiently reuse the vacated positions created by dequeuing elements, preventing the "Queue is Full" condition from occurring even when space is available.

By using this approach, we ensure that the queue makes better use of its array space, improving memory efficiency and allowing continuous enqueue operations without running into the limitations of a linear queue.

Coding Implementation

//queueimplementationusingarray.c
#include<stdio.h>
#define MAX 5
#define TRUE 1
#define FALSE 0

struct queue{
int frontidx;
int rearidx;
int size;
int arr[MAX];
};

int isFull(struct queue *q) {
return q->size == MAX ? TRUE : FALSE;
}

int isEmpty(struct queue *q) {
return q->size == 0 ? TRUE : FALSE;
}

void enqueue(struct queue *q, int n) {
if (isFull(q)) {
    printf("Queue is Full\n");
    return;
}
q->arr[q->rearidx] = n;
printf("Enqueued Element is: %d\n", q->arr[q->rearidx]);
q->rearidx = (q->rearidx + 1) % MAX;  // Wrapping around if rearidx reaches MAX
q->size++;
}

void dequeue(struct queue *q) {
if (isEmpty(q)) {
    printf("Queue is Empty\n");
    return;
}
printf("Dequeued Element: %d\n", q->arr[q->frontidx]);
q->frontidx = (q->frontidx + 1) % MAX;  // Wrapping around if frontidx reaches MAX
q->size--;
}

int front(struct queue *q) {
return q->arr[q->frontidx];
}

int main() {
struct queue q = {0, 0, 0};
enqueue(&q, 2);
enqueue(&q, 3);
enqueue(&q, 4);
enqueue(&q, 5);
enqueue(&q, 6);

dequeue(&q);  // Removes 2
dequeue(&q);  // Removes 3

// Enqueue more elements
enqueue(&q, 7);
enqueue(&q, 8);

dequeue(&q);  // Removes 4
dequeue(&q);  // Removes 5

return 0;
}

Comparison of Queue Implementation Using Array and Linked List

Comparison of Queue Implementation Using Array and Linked List:

Read more here