Queues

Question 1

What is the philosophy of a queue and what can it be resembled to in real life?

Answer 1

Queues work in first-in, first-out and just as their name suggests, they resemble a queue in real life (FIFO)

Question 2

What are the three operations that we learnt when implementing queues?

Answer 2

1) Front
2) Enqueue
3) Dequeue

Question 3

What is an enqueue implementation look like?

Answer 3

void enqueue(queue_t queue, int elem) {
assert(queue != NULL);
node_t newnode = malloc(sizeof(node_t));
newnode->element = elem;
newnode->next = NULL;
if (queue->rear == NULL) {
queue->front = newnode;
} else {
queue->rear->next = newnode;
}
queue->rear = newnode;
queue->size++;
}

Question 4

What about an implementation of front()?

Answer 4

_Bool front(queue_t *queue, int *elem) {
assert(queue != NULL && elem != NULL);
if (queue->front == NULL) {
return false;
}
*elem = queue->front->element;
return true;
}

Question 5

What is an example of the implementation of dequeue()?

Answer 5

_Bool dequeue(queue_t *queue, int *elem) {
assert(queue != NULL && elem != NULL);
if (queue->size == 0) {
return false;
}
elem = queue->front->element;
node_t node_to_delete = queue->front;
if (queue->size == 1) {
queue->rear = NULL;
}
queue->front = queue->front->next;
free(node_to_delete);
queue->size–;
return true;
}

Question 6

What would be a type of implementation that can be used to print queues?

Answer 6

void print_queue(queue_t queue) {
assert(queue != NULL);
if (queue->size == 0) {
printf(“{ }\n”);
return;
}
printf(“{“);
for (node_t curr = queue->front; curr != queue->rear;
curr = curr->next) {
printf(“%d, “, curr->element);
}
printf(“%d}\n”, queue->rear->element);
}

Question 7

What changes for an circular linked list?

Answer 7

There is no actual front of the loop, the front of the loop is referred to by queue->rear->next;

Question 8

What is an enqueue implementation for a circular queue?

Answer 8

void enqueue(queue_t *queue, int value) {
assert(queue != NULL);
node_t *newnode;
newnode = malloc(sizeof(node_t));
assert(newnode != NULL); //will ensure that malloc did not fail
newnode -> data = value;
if (queue -> rear == NULL){
newnode->next = newnode; //creates that circular link
queue->rear = newnode;

} else{
    newnode->next = queue->rear->next;
    // queue->rear->next = newnode->next;
    queue->rear->next = newnode;
} 
queue->rear = newnode; //ask ta to explain this LOL
queue->size++;

}

Question 9

What is a dequeue implementation for a circular linked list?

Answer 9

_Bool dequeue(queue_t *queue, int element) {
assert(queue != NULL && element != NULL);
if (queue->rear == NULL){ //empty queue
return false;
}
node_t to_remove = queue->rear->next;
*element = to_remove->data; //copying elem
if (queue->size == 1){
queue->rear = NULL;
} else {
queue->rear->next = to_remove->next;
}
free(to_remove);
queue->size -=1 ;
return true;

}

Question 10

What is a front implementation for a circular queue?

Answer 10

_Bool front(const queue_t *queue, int *element) {
assert(queue != NULL && element != NULL);
if (queue->rear == NULL){
return false;
}
*element = queue->rear->next->data;
return true;
}