[go: up one dir, main page]
Scribd
Upload
10 views14 pages

Week 3

The document contains multiple implementations of queue data structures in C, including priority queues using sorted and unsorted lists, linear queues using linked lists and arrays, and circular queues using arrays. Each implementation provides functions for enqueueing, dequeueing, displaying the queue, and checking its status. The code is structured with main functions to handle user input and operations on the queues.

Uploaded by

md sameer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views14 pages

Week 3

The document contains multiple implementations of queue data structures in C, including priority queues using sorted and unsorted lists, linear queues using linked lists and arrays, and circular queues using arrays. Each implementation provides functions for enqueueing, dequeueing, displaying the queue, and checking its status. The code is structured with main functions to handle user input and operations on the queues.

Uploaded by

md sameer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 14

Week 3

Priority Queue Implementation using Sorted List

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_TASK_NAME 51

typedef struct Node {


int priority;
char task[MAX_TASK_NAME];
struct Node* next;
} Node;

Node* head = NULL;

void enqueue(int priority, char* task) {


Node* newNode = (Node*)malloc(sizeof(Node));
newNode->priority = priority;
strcpy(newNode->task, task);

// If queue is empty or new priority is highest


if (head == NULL || priority > head->priority) {
newNode->next = head;
head = newNode;
} else {
Node* current = head;
while (current->next != NULL && current->next->priority >= priority) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
printf("Task added: %s (priority: %d)\n", task, priority);
}

void dequeue() {
if (head == NULL) {
printf("Queue is empty\n");
return;
}

Node* temp = head;


printf("%s (priority: %d)\n", temp->task, temp->priority);
head = head->next;
free(temp);
}

void display() {
if (head == NULL) {
printf("Queue is empty\n");
return;
}

Node* current = head;


while (current != NULL) {
printf("%s (priority: %d)\n", current->task, current->priority);
current = current->next;
}
}

int main() {
int n, priority;
char operation[10], task[MAX_TASK_NAME];

scanf("%d\n", &n);

for (int i = 0; i < n; i++) {


scanf("%s", operation);

if (strcmp(operation, "enqueue") == 0) {
scanf("%d ", &priority);
fgets(task, MAX_TASK_NAME, stdin);
task[strlen(task)-1] = '\0'; // Remove newline
enqueue(priority, task);
} else if (strcmp(operation, "dequeue") == 0) {
dequeue();
} else if (strcmp(operation, "display") == 0) {
display();
}
}
// Free memory
while (head != NULL) {
Node* temp = head;
head = head->next;
free(temp);
}

return 0;
}

Priority Queue Implementation using Unsorted List

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 100

typedef struct {
int element;
int priority;
} QueueItem;

typedef struct {
QueueItem items[MAX_SIZE];
int size;
} PriorityQueue;

void initialize(PriorityQueue* pq) {


pq->size = 0;
}

void enqueue(PriorityQueue* pq, int element, int priority) {


if (pq->size >= MAX_SIZE) {
return;
}

pq->items[pq->size].element = element;
pq->items[pq->size].priority = priority;
pq->size++;
printf("Enqueued: %d %d\n", element, priority);
}

int dequeue(PriorityQueue* pq) {


if (pq->size == 0) {
printf("Queue is empty\n");
return -1;
}

int maxPriorityIndex = 0;
for (int i = 1; i < pq->size; i++) {
if (pq->items[i].priority >= pq->items[maxPriorityIndex].priority) {
maxPriorityIndex = i;
}
}

int element = pq->items[maxPriorityIndex].element;

// Shift elements to fill the gap


for (int i = maxPriorityIndex; i < pq->size - 1; i++) {
pq->items[i] = pq->items[i + 1];
}

pq->size--;
printf("Dequeued: %d\n", element);
return element;
}

void display(PriorityQueue* pq) {


if (pq->size == 0) {
printf("Queue is empty\n");
return;
}

for (int i = 0; i < pq->size; i++) {


printf("%d:%d\n", pq->items[i].element, pq->items[i].priority);
}
}

int main() {
PriorityQueue pq;
initialize(&pq);

int n;
scanf("%d", &n);

char operation[10];
int element, priority;

for (int i = 0; i < n; i++) {


scanf("%s", operation);

if (strcmp(operation, "enqueue") == 0) {
scanf("%d %d", &element, &priority);
enqueue(&pq, element, priority);
}
else if (strcmp(operation, "dequeue") == 0) {
dequeue(&pq);
}
else if (strcmp(operation, "display") == 0) {
display(&pq);
}
}

return 0;
}

Linear Queue Implementation using Linked List

#include <stdio.h>
#include <stdlib.h>

// Structure for queue node


struct Node {
int data;
struct Node* next;
};

// Structure for queue


struct Queue {
struct Node *front, *rear;
};

// Initialize queue
struct Queue* createQueue() {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->front = queue->rear = NULL;
return queue;
}

// Enqueue operation
void enqueue(struct Queue* queue, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;

// If queue is empty
if (queue->rear == NULL) {
queue->front = queue->rear = newNode;
printf("Element %d enqueued successfully\n", value);
return;
}

// Add new node at the end


queue->rear->next = newNode;
queue->rear = newNode;
printf("Element %d enqueued successfully\n", value);
}

// Dequeue operation
void dequeue(struct Queue* queue) {
// If queue is empty
if (queue->front == NULL) {
printf("Queue is empty\n");
return;
}

struct Node* temp = queue->front;


int value = temp->data;

queue->front = queue->front->next;

// If front becomes NULL, set rear as NULL too


if (queue->front == NULL) {
queue->rear = NULL;
}

free(temp);
printf("Element %d dequeued successfully\n", value);
}

// Display operation
void display(struct Queue* queue) {
if (queue->front == NULL) {
printf("Queue is empty\n");
return;
}

struct Node* temp = queue->front;


while (temp->next != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("%d\n", temp->data);
}

int main() {
struct Queue* queue = createQueue();
int n, operation, value;

scanf("%d", &n);

for (int i = 0; i < n; i++) {


scanf("%d", &operation);

switch(operation) {
case 1:
scanf("%d", &value);
enqueue(queue, value);
break;
case 2:
dequeue(queue);
break;
case 3:
display(queue);
break;
}
}

// Free memory
while (queue->front != NULL) {
struct Node* temp = queue->front;
queue->front = queue->front->next;
free(temp);
}
free(queue);

return 0;
}

Queue Implementation using Array

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 10

typedef struct {
int arr[MAX_SIZE];
int front;
int rear;
int count;
} Queue;

void initialize(Queue *q) {


q->front = 0;
q->rear = -1;
q->count = 0;
}

int isfull(Queue *q) {


return q->count == MAX_SIZE;
}

int isempty(Queue *q) {


return q->count == 0;
}
void insert(Queue *q, int value) {
if (isfull(q)) {
printf("Queue is full\n");
return;
}
q->rear = (q->rear + 1) % MAX_SIZE;
q->arr[q->rear] = value;
q->count++;
printf("Inserted: %d\n", value);
}

void delete(Queue *q) {


if (isempty(q)) {
printf("Queue is empty\n");
return;
}
int value = q->arr[q->front];
q->front = (q->front + 1) % MAX_SIZE;
q->count--;
printf("Deleted: %d\n", value);
}

void display(Queue *q) {


if (isempty(q)) {
printf("Queue is empty\n");
return;
}
int i, index;
for (i = 0; i < q->count; i++) {
index = (q->front + i) % MAX_SIZE;
printf("%d", q->arr[index]);
if (i < q->count - 1) printf(" ");
}
printf("\n");
}

void frontelement(Queue *q) {


if (isempty(q)) {
printf("Queue is empty\n");
return;
}
printf("%d\n", q->arr[q->front]);
}
void endelement(Queue *q) {
if (isempty(q)) {
printf("Queue is empty\n");
return;
}
printf("%d\n", q->arr[q->rear]);
}

void elementcount(Queue *q) {


printf("%d\n", q->count);
}

int main() {
Queue q;
initialize(&q);
char operation[20];
int n, value;

scanf("%d", &n);
while (n--) {
scanf("%s", operation);
if (strcmp(operation, "insert") == 0) {
scanf("%d", &value);
insert(&q, value);
} else if (strcmp(operation, "delete") == 0) {
delete(&q);
} else if (strcmp(operation, "display") == 0) {
display(&q);
} else if (strcmp(operation, "isempty") == 0) {
printf("%s\n", isempty(&q) ? "true" : "false");
} else if (strcmp(operation, "isfull") == 0) {
printf("%s\n", isfull(&q) ? "true" : "false");
} else if (strcmp(operation, "frontelement") == 0) {
frontelement(&q);
} else if (strcmp(operation, "endelement") == 0) {
endelement(&q);
} else if (strcmp(operation, "elementcount") == 0) {
elementcount(&q);
}
}
return 0;
}
Circular Queue Implementation using Array

#include <stdio.h>
#include <string.h>

#define MAX_SIZE 5

typedef struct {
int arr[MAX_SIZE];
int front;
int rear;
int count;
} CircularQueue;

void initialize(CircularQueue *q) {


q->front = -1;
q->rear = -1;
q->count = 0;
}

int isfull(CircularQueue *q) {


return q->count == MAX_SIZE;
}

int isempty(CircularQueue *q) {


return q->count == 0;
}

void insert(CircularQueue *q, int value) {


if (isfull(q)) {
printf("Queue is full\n");
return;
}

if (isempty(q)) {
q->front = 0;
}
q->rear = (q->rear + 1) % MAX_SIZE;
q->arr[q->rear] = value;
q->count++;
printf("Inserted: %d\n", value);
}

void delete(CircularQueue *q) {


if (isempty(q)) {
printf("Queue is empty\n");
return;
}

printf("Deleted: %d\n", q->arr[q->front]);

if (q->front == q->rear) {
q->front = -1;
q->rear = -1;
} else {
q->front = (q->front + 1) % MAX_SIZE;
}
q->count--;
}

void display(CircularQueue *q) {


if (isempty(q)) {
printf("Queue is empty\n");
return;
}

int i, index;
for (i = 0; i < q->count; i++) {
index = (q->front + i) % MAX_SIZE;
printf("%d", q->arr[index]);
if (i < q->count - 1) printf(" ");
}
printf("\n");
}

void frontelement(CircularQueue *q) {


if (isempty(q)) {
printf("Queue is empty\n");
return;
}
printf("%d\n", q->arr[q->front]);
}

void endelement(CircularQueue *q) {


if (isempty(q)) {
printf("Queue is empty\n");
return;
}
printf("%d\n", q->arr[q->rear]);
}

void elementcount(CircularQueue *q) {


printf("%d\n", q->count);
}

int main() {
CircularQueue q;
initialize(&q);
char operation[20];
int n, value;

scanf("%d", &n);
while (n--) {
scanf("%s", operation);
if (strcmp(operation, "insert") == 0) {
scanf("%d", &value);
insert(&q, value);
} else if (strcmp(operation, "delete") == 0) {
delete(&q);
} else if (strcmp(operation, "display") == 0) {
display(&q);
} else if (strcmp(operation, "isempty") == 0) {
printf("%s\n", isempty(&q) ? "true" : "false");
} else if (strcmp(operation, "isfull") == 0) {
printf("%s\n", isfull(&q) ? "true" : "false");
} else if (strcmp(operation, "frontelement") == 0) {
frontelement(&q);
} else if (strcmp(operation, "endelement") == 0) {
endelement(&q);
} else if (strcmp(operation, "elementcount") == 0) {
elementcount(&q);
}
}
return 0;
}

You might also like