AlgoDocs

Queue Implementation Using Array

Implementing queue operations using an Array

Implementation

Initialize the Queue

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

Check if the Queue is Empty

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

Check if the Queue is Full

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

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].

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).

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

</TabsContent>
<TabsContent value="py">

```python
print("We're Working")
console.log("We're Working");

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.

Visualization of Circular 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;
}
print("We're Working")
console.log("We're Working");

Comparison of Queue Implementation Using Array and Linked List

Comparison of Queue Implementation Using Array and Linked List

How is this guide?