Comment implémenter une file d'attente avec un tableau alloué dynamiquement?

Question

Je veux implémenter la file d'attente en utilisant un tableau alloué dynamiquement. Cela présente des problèmes dont je ne sais pas comment traiter. Comment puis-je vérifier si la file d'attente est vide? Comment puis-je savoir combien d'éléments sont dans la file d'attente en un instant?

Pour le deuxième problème, je me dis que je peux créer une variable pour garder une trace du nombre d'éléments dans la file d'attente qui se met à jour chaque fois que j'utilise realloc(). Je suis bienvenu à d'autres suggestions cependant.

Si vous avez d'autres considérations je devrais penser à s'il vous plaît les présenter.

Answer 1

Généralement, vous conservez une variable de pointeur sur la "tête" de votre file d'attente. Lorsque ce pointeur est nul, la liste est vide, sinon, il pointe vers le premier noeud. Maintenant, quand il s'agit du nombre d'éléments dans la file d'attente à un moment donné, une autre solution à ce que vous avez suggéré est de réellement parcourir tous les nœuds et compter, mais en fonction du nombre d'éléments, cela pourrait être assez lent .

Answer 2

pour votre compteur, il suffit de garder un compte de référence de combien d'éléments ont été insérés

INSERT() { 
    //code to insert element 
    size++; 
} 

POP(){ 
    //code to remove element 
    size--; 
} 

SIZE(){ 
    return size; 
} 

Ensuite vous allez devoir décider quel type de stratégie vous allez utiliser pour insérer des éléments.

La plupart des gens utilisent simplement une liste. Et puisque les files d'attente sont généralement soit FILO (First in Last out), soit LILO (Last in last out), cela peut être un peu délicat.

Une liste est juste ce

struct Node{ 
    T* Value; 
    ptr Next; 
} 

où vous avez un tas de ces derniers dans la séquence qui crée une liste. Chaque insertion génère un nouveau noeud et une suppression supprime le noeud et rattache la liste.

Answer 3

est ici une file d'attente FIFO à base de tableau assez simple:

struct queue { 
    T *store;  // where T is the data type you're working with 
    size_t size; // the physical array size 
    size_t count; // number of items in queue 
    size_t head; // location to pop from 
    size_t tail; // location to push to 
}; 

struct queue q; 
q.store = malloc(sizeof *q.store * SIZE); 
if (q.store) 
{ 
    q.size = SIZE; 
    q.count = q.head = q.tail = 0; 
} 

Pour pousser un élément, faire quelque chose comme ce qui suit:

int push(struct queue q, T new_value) 
{ 
    if (q.count == q.size) 
    { 
    // queue full, handle as appropriate 
    return 0; 
    } 
    else 
    { 
    q.store[q.tail] = new_value; 
    q.count++; 
    q.tail = (q.tail + 1) % q.size; 
    } 
    return 1; 
} 

Pops sont similaires

int pop(struct queue q, T *value) 
{ 
    if (q.count == 0) 
    { 
    // queue is empty, handle as appropriate 
    return 0; 
    } 
    else 
    { 
    *value = q.store[q.head]; 
    q.count--; 
    q.head = (queue.head + 1) % q.size; 
    } 

    return 1; 
} 

Comme écrit, ceci est une file "circulaire"; les pointeurs head et tail s'enrouleront alors que les éléments sont poussés et sortent de la file d'attente.

Comme pour toute approche, cela a des points forts et des points faibles. C'est simple, et cela évite une gestion excessive de la mémoire (juste l'allocation du backing store). Juste mettre à jour count est plus simple que d'essayer de le calculer à partir de head et tail.

L'extension du magasin de stockage n'est pas si simple; si le pointeur de la queue est enroulée autour, vous devrez passer tout après head:

Before: 

+---+---+---+---+---+ 
| x | x | x | x | x | 
+---+---+---+---+---+ 
     ^^
      | | 
      | +--- head 
      +------- tail 

After:   
+---+---+---+---+---+---+---+---+---+---+ 
| x | x | x | | | | | | x | x | 
+---+---+---+---+---+---+---+---+---+---+ 
     ^     ^
      |      | 
      |      +--- head 
      +------- tail 

Aussi, si vous voulez quelque chose de plus sophistiqué qu'un simple FIFO, vous voudrez probablement utiliser une structure de données différentes que votre magasin de soutien.