Operations on Queue:
- Create: Initializing a queue data structure before it can be used. This typically involves allocating memory and setting initial values for the front and rear pointers.
- Add (Enqueue): Adding an element to the rear of the queue. This operation is also known as enqueue.
- Delete (Dequeue): Removing an element from the front of the queue. This operation is also known as dequeue.
- Full: Checking if the queue is full and cannot accept more elements. This operation is important in array-based implementations where the capacity is fixed.
- Empty: Checking if the queue is empty and does not contain any elements.
Circular Queue:
A circular queue is an improvement over a regular queue where the rear pointer can wrap around to the beginning of the array when it reaches the end. This allows for better utilization of space and avoids unnecessary shifting of elements.
Deque (Double-ended Queue):
A deque is a data structure that allows insertion and deletion of elements from both the front and rear ends. It combines the features of both stacks and queues. Deques can be implemented using arrays or linked lists.
Priority Queue:
A priority queue is a type of queue where each element has an associated priority, and elements are dequeued based on their priority. Elements with higher priority are dequeued before elements with lower priority, regardless of the order in which they were enqueued. Priority queues can be implemented using various data structures such as heaps or balanced binary search trees.
Example of Circular Queue:
Here’s a simple example of a circular queue implementation in C:
typedef struct {
int arr[MAX_SIZE];
int front;
int rear;
} CircularQueue;
void initQueue(CircularQueue *q) {
q->front = -1;
q->rear = -1;
}
int isFull(CircularQueue *q) {
return (q->front == (q->rear + 1) % MAX_SIZE);
}
int isEmpty(CircularQueue *q) {
return (q->front == -1 && q->rear == -1);
}
void enqueue(CircularQueue *q, int item) {
if (isFull(q)) {
printf(“Queue is full\n”);
return;
}
if (isEmpty(q))
q->front = q->rear = 0;
else
q->rear = (q->rear + 1) % MAX_SIZE;
q->arr[q->rear] = item;
}
int dequeue(CircularQueue *q) {
if (isEmpty(q)) {
printf(“Queue is empty\n”);
return -1;
}
int item = q->arr[q->front];
if (q->front == q->rear)
q->front = q->rear = -1;
else
q->front = (q->front + 1) % MAX_SIZE;
return item;
}
int main() {
CircularQueue q;
initQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
enqueue(&q, 40);
enqueue(&q, 50); // Queue is full now
printf(“Dequeued item: %d\n”, dequeue(&q)); // Output: 10
printf(“Dequeued item: %d\n”, dequeue(&q)); // Output: 20
enqueue(&q, 60); // Now, queue can accept elements again
return 0;
}
In this implementation, the circular nature of the queue is achieved by using the modulo operator (%) when incrementing the rear pointer. This allows the rear pointer to wrap around to the beginning of the array when it reaches the end.