Instructions
Objective
Write a C assignment program to implement queues and priority queues.
Requirements and Specifications
Part I (Queue Implementation)
Implement the queue ADT (FIFO) using a linked list in C. To do this, you need to implement functions enqueue (for adding an element of type int to the rear end of queue), dequeue (for removing an element of type int from the front end of the queue), and size (for returning the number of elements in the queue). Please test your implementation extensively to be sure about its correctness. You need to submit the C program containing you test cases along the queue implementation.
Part II (Priority Queue Implementation)
Implement the priority queue ADT using a max binary heap in C. To do this, you need to implement functions add (for adding an element of type int to the heap), extract_max (for removing the greatest element stored in the heap), and size (for returning the number of elements in the heap). Please test your implementation extensively to be sure about its correctness. You need to submit the C program containing you test cases along the heap implementation.
Source Code
QUEUE
#include
#include "queue.h"
queue* createQueue() {
queue* newQueue = (queue*)malloc(sizeof(queue));
newQueue->head = NULL;
newQueue->tail = NULL;
newQueue->size = 0;
return newQueue;
}
void enqueue(queue* q, int data) {
node* newNode = (node*)malloc(sizeof(node));
newNode->data = data;
newNode->next = NULL;
if (q->size == 0) {
q->head = newNode;
q->tail = newNode;
}
else {
q->tail->next = newNode;
q->tail = newNode;
}
q->size++;
}
int dequeue(queue* q) {
node* top = q->head;
int result = top->data;
q->head = q->head->next;
if (q->head == NULL) {
q->tail = NULL;
}
q->size--;
free(top);
return result;
}
int size(queue *q) {
return q->size;
}
void freeQueue(queue* q) {
while(q->size > 0) {
dequeue(q);
}
free(q);
}
PRIORITY QUEUES
#include
#include "priorityqueue.h"
void siftUp(pqueue* q, int index) {
if (index == 0) {
return;
}
int parent = (index - 1) / 2;
if (q->vals[parent] < q->vals[index]) {
int sw = q->vals[parent];
q->vals[parent] = q->vals[index];
q->vals[index] = sw;
siftUp(q, parent);
}
}
void siftDown(pqueue* q, int index) {
int child1 = 2*index + 1;
int child2 = 2*index + 2;
if (child1 < q->size) {
int child = child1;
if (child2 < q->size && q->vals[child1] < q->vals[child2]) {
child = child2;
}
if (q->vals[child] > q->vals[index]) {
int sw = q->vals[child];
q->vals[child] = q->vals[index];
q->vals[index] = sw;
siftDown(q, child);
}
}
}
pqueue* createPQueue(int capacity) {
pqueue* q = (pqueue*)malloc(sizeof(pqueue));
q->vals = (int*)calloc(capacity, sizeof(int));
q->capacity = capacity;
q->size = 0;
return q;
}
void add(pqueue* q, int data) {
if (q->size == q->capacity) {
return;
}
q->vals[q->size] = data;
q->size++;
siftUp(q, q->size-1);
}
int extract_max(pqueue* q) {
int result = q->vals[0];
q->vals[0] = q->vals[q->size-1];
q->size--;
siftDown(q, 0);
return result;
}
int size(pqueue *q) {
return q->size;
}
void freePQueue(pqueue *q) {
free(q->vals);
free(q);
}