Danh sách khoá học Đăng ký Đăng nhập

Thông tin

Tác giả Maxime Mawait & Nicolas Rybowski
Hạn chót Không có hạn chót
Giới hạn nộp bài Không có giới hạn
Các tag chuyên mục s4, category_pointer, category_struct, category_linked_list, level3

Tags

Đăng nhập

Đăng nhập

[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  ;
Câu hỏi 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){
Câu hỏi 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){