Define circular queue. How queue differ from stack. Write a program to implement linear queue.

A circular queue is a queue in which the last position is connected back to the first, so the array is used in a circle. When rear reaches the end of the array it wraps round to index 0 if there is free space there.

It solves the main problem of a linear queue: in a linear queue, once rear reaches the end, the spaces freed at the front by deletions can never be reused. In a circular queue the positions move with rear = (rear + 1) % MAX and front = (front + 1) % MAX.

Queue vs stack

Program: linear queue using an array

#include <stdio.h>
#define MAX 5

int queue[MAX];
int front = -1, rear = -1;

void enqueue(int x) {
    if (rear == MAX - 1) {
        printf("Queue overflow\n");
        return;
    }
    if (front == -1) front = 0;        /* first element */
    queue[++rear] = x;
    printf("%d inserted\n", x);
}

void dequeue(void) {
    if (front == -1 || front > rear) {
        printf("Queue underflow\n");
        return;
    }
    printf("%d deleted\n", queue[front++]);
}

void display(void) {
    int i;
    if (front == -1 || front > rear) {
        printf("Queue is empty\n");
        return;
    }
    for (i = front; i <= rear; i++)
        printf("%d ", queue[i]);
    printf("\n");
}

int main(void) {
    enqueue(10); enqueue(20); enqueue(30);
    display();          /* 10 20 30 */
    dequeue();          /* 10 deleted */
    display();          /* 20 30 */
    return 0;
}