Comment implémenter une queue dans une liste chaînée en c?

On me donne ces déclarations de structure afin de mettre en œuvre une collection de files d’attente qui utilise une liste chaînée circulaire.

typedef struct intnode { int value; struct intnode *next; } intnode_t; typedef struct { intnode_t *rear; // Points to the node at the tail of the // queue's linked list int size; // The # of nodes in the queue's linked list } intqueue_t; intnode_t *intnode_construct(int value, intnode_t *next) { intnode_t *p = malloc(sizeof(intnode_t)); assert (p != NULL); p->value = value; p->next = next; return p; } /* Return a pointer to a new, empty queue. * Terminate (via assert) if memory for the queue cannot be allocated. */ intqueue_t *intqueue_construct(void) { intqueue_t *queue = malloc(sizeof(intqueue_t)); assert(queue != NULL); queue->rear = NULL; queue->size = 0; return queue; } 

J’essaie de créer une fonction qui va mettre en queue à une valeur spécifiée (l’append à l’arrière de la file), et je dois prendre en compte les deux cas dans lesquels la file est vide et lorsque la file contient un ou plusieurs éléments. C’est le code que j’ai jusqu’à présent:

 void intqueue_enqueue(intqueue_t *queue, int value) { intnode_t *p = intnode_construct(value, NULL); if(queue->rear->next == NULL) { //the queue is empty queue->rear->next =p; } else { //the queue is not empty queue->rear=p; } queue->rear=p; queue->size++; } 

Ce code me donne une erreur d’exécution donc je ne suis pas sûr de ce qui ne va pas. Dans le code, je suppose que queue-> arrière-> est l’avant, mais je pense que c’est là que réside le problème. Toute aide est grandement appréciée. Merci!

METTRE À JOUR–

J’ai essayé de retravailler le code et j’ai ceci:

 void intqueue_enqueue(intqueue_t *queue, int value) { assert(queue!=NULL); intnode_t *p = intnode_construct(value,NULL); if (queue->size==0){ queue->rear=p; queue->size++; queue->rear->next=p; free(p); } else { p->next = queue->rear; queue->rear=p; queue->size++; free(p); } } 

Cela ne fonctionne que quand il est vide mais pas quand ce n’est pas vide.

File circulaire dans la liste chaînée

Votre code est trop volumineux pour être lu. Voici donc ce que j’utilise pour implémenter la queue circulaire:

#include using namespace std;

 // Structure of a Node struct Node { int data; struct Node* link; }; struct Queue { struct Node *front, *rear; }; // Function to create Circular queue void enQueue(Queue *q, int value) { struct Node *temp = new Node; temp->data = value; if (q->front == NULL) q->front = temp; else q->rear->link = temp; q->rear = temp; q->rear->link = q->front; } // Function to delete element from Circular Queue int deQueue(Queue *q) { if (q->front == NULL) { printf ("Queue is empty"); return INT_MIN; } // If this is the last node to be deleted int value; // Value to be dequeued if (q->front == q->rear) { value = q->front->data; free(q->front); q->front = NULL; q->rear = NULL; } else // There are more than one nodes { struct Node *temp = q->front; value = temp->data; q->front = q->front->link; q->rear->link= q->front; free(temp); } return value ; } // Function displaying the elements of Circular Queue void displayQueue(struct Queue *q) { struct Node *temp = q->front; printf("\nElements in Circular Queue are: "); while (temp->link != q->front) { printf("%d ", temp->data); temp = temp->link; } printf("%d", temp->data); } /* Driver of the program */ int main() { // Create a queue and initialize front and rear Queue *q = new Queue; q->front = q->rear = NULL; // Inserting elements in Circular Queue enQueue(q, 14); enQueue(q, 22); enQueue(q, 6); // Display elements present in Circular Queue displayQueue(q); // Deleting elements from Circular Queue printf("\nDeleted value = %d", deQueue(q)); printf("\nDeleted value = %d", deQueue(q)); // Remaining elements in Circular Queue displayQueue(q); enQueue(q, 9); enQueue(q, 20); displayQueue(q); return 0; }