De-Queue (Double-Ended Queue)
A De-Queue (Double-Ended Queue) is a type of queue where elements can be added or removed from both the front and the rear. It is more flexible than a standard queue.
Types of De-Queue
- Input-Restricted De-Queue: Insertion is allowed only at the rear, but deletion is allowed at both ends.
- Output-Restricted De-Queue: Deletion is allowed only at the front, but insertion is allowed at both ends.
Operations in De-Queue
- InsertFront: Adds an element at the front.
- InsertRear: Adds an element at the rear.
- DeleteFront: Removes an element from the front.
- DeleteRear: Removes an element from the rear.
- Display: Prints the elements of the De-Queue.
Implementation of De-Queue in C
#include <stdio.h>
#define SIZE 5
int deque[SIZE];
int front = -1, rear = -1;
// Insert at the front
void insertFront(int element) {
if ((front == 0 && rear == SIZE – 1) || (front == rear + 1)) {
printf(“De-Queue is full.\n”);
} else {
if (front == -1) { // First element
front = rear = 0;
} else if (front == 0) {
front = SIZE – 1;
} else {
front–;
}
deque[front] = element;
printf(“Inserted %d at the front.\n”, element);
}
}
// Insert at the rear
void insertRear(int element) {
if ((front == 0 && rear == SIZE – 1) || (front == rear + 1)) {
printf(“De-Queue is full.\n”);
} else {
if (front == -1) { // First element
front = rear = 0;
} else if (rear == SIZE – 1) {
rear = 0;
} else {
rear++;
}
deque[rear] = element;
printf(“Inserted %d at the rear.\n”, element);
}
}
// Delete from the front
void deleteFront() {
if (front == -1) {
printf(“De-Queue is empty.\n”);
} else {
printf(“Deleted %d from the front.\n”, deque[front]);
if (front == rear) { // Reset De-Queue
front = rear = -1;
} else if (front == SIZE – 1) {
front = 0;
} else {
front++;
}
}
}
// Delete from the rear
void deleteRear() {
if (front == -1) {
printf(“De-Queue is empty.\n”);
} else {
printf(“Deleted %d from the rear.\n”, deque[rear]);
if (front == rear) { // Reset De-Queue
front = rear = -1;
} else if (rear == 0) {
rear = SIZE – 1;
} else {
rear–;
}
}
}
// Display the De-Queue
void display() {
if (front == -1) {
printf(“De-Queue is empty.\n”);
} else {
printf(“De-Queue elements: “);
int i = front;
while (1) {
printf(“%d “, deque[i]);
if (i == rear) break;
i = (i + 1) % SIZE;
}
printf(“\n”);
}
}
int main() {
insertRear(10);
insertRear(20);
insertFront(5);
display();
deleteFront();
deleteRear();
display();
return 0;
}
Priority Queue
A Priority Queue is a special type of queue where elements are dequeued based on priority rather than their insertion order. Each element has an associated priority, and the element with the highest priority is served first.
Operations in Priority Queue
- Insert: Adds an element based on its priority.
- Delete: Removes the element with the highest priority.
- Display: Shows the elements of the queue along with their priorities.
Implementation of Priority Queue in C
#include <stdio.h>
#define SIZE 5
typedef struct {
int data;
int priority;
} PriorityQueue;
PriorityQueue pq[SIZE];
int count = 0;
// Insert element based on priority
void insert(int data, int priority) {
if (count == SIZE) {
printf(“Priority Queue is full.\n”);
return;
}
int i = count – 1;
while (i >= 0 && pq[i].priority > priority) { // Shift elements with lower priority
pq[i + 1] = pq[i];
i–;
}
pq[i + 1].data = data;
pq[i + 1].priority = priority;
count++;
printf(“Inserted %d with priority %d.\n”, data, priority);
}
// Delete element with the highest priority
void deleteHighestPriority() {
if (count == 0) {
printf(“Priority Queue is empty.\n”);
return;
}
printf(“Deleted %d with priority %d.\n”, pq[0].data, pq[0].priority);
for (int i = 1; i < count; i++) {
pq[i – 1] = pq[i]; // Shift elements left
}
count–;
}
// Display the Priority Queue
void display() {
if (count == 0) {
printf(“Priority Queue is empty.\n”);
return;
}
printf(“Priority Queue elements:\n”);
for (int i = 0; i < count; i++) {
printf(“Data: %d, Priority: %d\n”, pq[i].data, pq[i].priority);
}
}
int main() {
insert(10, 2);
insert(20, 1);
insert(15, 3);
display();
deleteHighestPriority();
display();
return 0;
}
Comparison: De-Queue vs Priority Queue
| Feature | De-Queue | Priority Queue |
| Insertion | Front and Rear | Based on priority |
| Deletion | Front and Rear | Highest priority element |
| Use Cases | Real-time scheduling, navigation | Task scheduling, job queues, simulation |
| Complexity | O(1) for insertion and deletion | O(n) for insertion, O(1) for deletion |
Summary
- A De-Queue allows insertion and deletion from both ends, useful for applications like undo/redo buffers.
- A Priority Queue ensures elements are processed based on priority, useful in scheduling tasks where priority matters.