Question

Implement a FIFO queue of integers using a circular array a[0] .. a[n-1], where n is a constant. a) Declare the data structure. b) Write a function that is given the circular array queue and an integer x and returns true if and only if x is an entry in the queue. Please use C language

Answer 1

Here is the implementation:

#define SIZE 10 // queue size

typedef struct {

int a[SIZE]; // array of elements

int front; // front pointer

int rear; // rear pointer

} Queue;

// initialize queue

void initQueue(Queue *q) {

q->front = 0;

q->rear = 0;

}

// check if queue is full

int isFull(Queue *q) {

return ((q->rear + 1) % SIZE == q->front);

}

// check if queue is empty

int isEmpty(Queue *q) {

return q->front == q->rear;

}

// insert an element

void enqueue(Queue *q, int x) {

if (isFull(q))

return;

q->a[q->rear] = x;

q->rear = (q->rear + 1) % SIZE;

}

// remove an element

int dequeue(Queue *q) {

if (isEmpty(q))

return -1;

int x = q->a[q->front];

q->front = (q->front + 1) % SIZE;

return x;

}

bool isInQueue(Queue *q, int x) {

for (int i = q->front; i != q->rear; i = (i + 1) % SIZE) {

if (q->a[i] == x) return true;

}

return false;

}

int main() {

Queue q;

initQueue(&q);

enqueue(&q, 10);

enqueue(&q, 5);

enqueue(&q, 2);

enqueue(&q, 7);

enqueue(&q, 1);

if (isInQueue(&q, 10)) printf("Yes\\");

if (isInQueue(&q, 50)) printf("No\\");

}

Time Complexity: O(n) where n is the queue size.

Space Complexity: O(n) due to the fixed size array.