[S4] Advanced queue

You must implement the enqueue and dequeue functions of a Queue that is implemented as a simple circular list. This Wikipedia page describes such a list as follows:

"With a circular list, a pointer to the last node gives easy access also to the first node, by following one link. Thus, in applications that require access to both ends of the list (e.g., in the implementation of a queue), a circular structure allows one to handle the structure by a single pointer, instead of two."

https://upload.wikimedia.org/wikipedia/commons/d/df/Circularly-linked-list.svg

Assume that the head of the queue is the leftmost node and that the tail of the queue is the rightmost node. In the previous example, the head and the tail are respectively 12 and 37. So in this case, the only pointer you can use will point to the 37 node.

You can use the following datastructures for this exercise:

typedef struct node{
  struct node* next;
  int value;
} node_t;

typedef struct queue{
  struct node* tail;
  int size;
} queue_t  ;

Question 1: Enqueue
/*
* Add @val value at the head of the @q queue
*
* @val     : the value to enqueue
* @q     : the queue
*
* @return 0 if no error, -1 otherwise
*
* pre : The queue q will always be valid, you don't need to handle the NULL case.
*/
int enqueue(queue_t* q, int val){
Question 2: Dequeue

HINT : Do not forget to free all the unused memory.

/*
* Remove the node at the tail of the @q queue and return the value of this node
* @q         : the queue
* @return     : the value at the tail
*
* pre         : The given queue will always be valid, you do not need to handle the NULL case.
*/
int dequeue(queue_t* q){

Information

Author(s) Maxime Mawait & Nicolas Rybowski
Deadline No deadline
Submission limit No limitation
Category Tags Data structures, S4

Tags

Sign in