Basée sur la baie vs Basés sur des listes Piles et Files d'attente

Il y a plusieurs façons différentes de mettre en œuvre des files d'attente et les piles avec des listes et des tableaux, et je ne suis pas sûr que ceux que vous êtes la recherche pour. Avant d'analyser l'une de ces structures, cependant, nous allons examiner certains des plus importants d'exécution des considérations pour les structures de données.

Dans une liste liée individuellement avec juste un pointeur de tête, le coût à ajouter une valeur est O(1) - il suffit de créer le nouvel élément, le fil de son pointeur à la vieille tête de la liste, puis mettre à jour le pointeur de tête. Le coût de supprimer le premier élément est également en O(1), qui est effectuée par la mise à jour de la tête pointeur sur l'élément après la tête, puis libérer la mémoire de l'ancien chef (si explicite de gestion de la mémoire est effectuée). Cependant, les facteurs constants dans ces O(1) les conditions qui peuvent être élevés en raison de la charge des allocations dynamiques. La surcharge de la mémoire de la liste chaînée est généralement de O(n) total de la mémoire supplémentaire en raison du stockage de pointeur dans chaque élément.

Dans un tableau dynamique, nous pouvons accéder à tout élément de O(1) fois. Nous pouvons aussi ajouter un élément dans amorti O(1), ce qui signifie que le temps total pour n insertions est de O(n), bien que le temps réel limites sur toute insertion est peut-être bien pire. Généralement, les tableaux dynamiques sont mises en œuvre par la plupart des insertions prendre en O(1) en ajoutant dans préaffectés de l'espace, mais ayant un petit nombre d'insertions exécuter en Θ(n) de temps de doublement de la capacité de la pile et de la copie des éléments en plus. Il existe des techniques pour essayer de réduire ce en allouant de l'espace supplémentaire et paresseusement la copie d'éléments (voir cette structure de données, par exemple). Généralement, l'utilisation de la mémoire d'un tableau dynamique est assez bonne - lorsque le tableau est complètement plein, par exemple, il y a seulement O(1) frais généraux supplémentaires - si à droite après le tableau a doublé de taille, il peut être O(n) éléments non utilisés alloués dans le tableau. Parce que les allocations sont rares et l'accès sont rapides, les tableaux dynamiques sont généralement plus rapides que les listes chaînées.

Maintenant, nous allons réfléchir à la façon de mettre en œuvre une pile et une file d'attente à l'aide d'une liste ou un tableau dynamique. Il y a beaucoup de façons de le faire, donc je vais supposer que vous êtes en utilisant les implémentations suivantes:

• De la pile:
  • Liste chaînée: Comme un liste liée individuellement avec une tête de pointeur.
  • Tableau: Comme un tableau dynamique
• File d'attente:
  • Lié liste: une liste liée individuellement avec une tête et d'une queue de pointeur.
  • Tableau: Comme un tampon circulaire soutenu par un tableau.

Examinons chacun à son tour.

Pile soutenu par une liste liée individuellement. Parce que une liste liée individuellement prend en charge O(1) temps d'ajouter et de supprimer des-tout d'abord, le coût de pousser ou de la pop dans une liste liée adossés à pile est également en O(1) le pire des cas. Cependant, chaque nouvel élément ajouté nécessite une nouvelle allocation, et les allocations peuvent être cher par rapport à d'autres opérations.

Pile soutenu par un tableau dynamique. En poussant sur la pile peut être mis en œuvre par l'ajout d'un nouvel élément du tableau dynamique, qui prend amorti O(1) au temps et au pire des cas en O(n) fois. Popping de la pile peut être mis en œuvre par juste de retirer le dernier élément, qui s'exécute dans le pire des cas en O(1) (ou amorti O(1) si vous voulez essayer de récupérer l'espace inutilisé). En d'autres termes, le plus commun de mise en œuvre a le meilleur des cas O(1) push et pop, dans le pire des cas en O(n) appuyez et O(1) pop, et amorti O(1) push et O(1) pop.

File d'attente soutenu par une liste liée individuellement. Replacement dans la liste liée peut être mis en œuvre par l'ajout à l'arrière de la liste liée individuellement, qui prend le pire des cas en temps O(1). La file d'attente peut être mis en œuvre par la suppression du premier élément, qui prend également en pire cas en temps O(1). Cela nécessite aussi une nouvelle allocation pour mettre en file d'attente, qui peut être lente.

File d'attente soutenu par une croissance de la mémoire tampon circulaire. Replacement dans le buffer circulaire fonctionne en insérant quelque chose à la prochaine position libre dans le tampon circulaire. Cela fonctionne par la croissance de la matrice, si nécessaire, puis insérer le nouvel élément. À l'aide d'une analyse similaire pour le tableau dynamique, il prend le meilleur des cas en temps O(1), dans le pire des cas en temps O(n), et amorti au temps O(1). La file d'attente à partir de la mémoire tampon des œuvres par la suppression du premier élément de la mémoire tampon circulaire, ce qui prend du temps O(1) dans le pire des cas.

Pour résumer, toutes les structures de soutien à pousser et à éclater de n éléments en O(n) fois. La liste liée versions ont un meilleur pire des cas, le comportement, mais peut avoir un pire global d'exécution en raison du nombre d'allocations effectuées. Le tableau des versions sont plus lents, dans le pire des cas, mais ont une meilleure performance globale si le temps par de l'opération n'est pas trop important.

Une autre option que vous pouvez regarder dans pour la mise en œuvre des piles est la VList récente de la structure de données qui est un hybride d'une liste, et un tableau dynamique. Il fait moins d'allocations de une liste, et a moins de pointeurs, bien que l'utilisation de l'espace est un peu plus élevé dans le pire des cas. Vous pouvez également regarder dans chunklists, qui sont un autre hybride de tableaux et les listes chaînées, qui peut être utilisé pour les deux piles et les files d'attente.

Espérons que cette aide!