Maison Problème commun Quelle structure de données est une file d'attente ?

Quelle structure de données est une file d'attente ?

Dec 25, 2020 am 10:45 AM
队列

Une file d'attente est une structure de données linéaire. La file d'attente autorise uniquement les opérations de suppression à l'avant de la table, tandis que les opérations d'insertion sont effectuées à l'arrière de la table. Comme la pile, la file d'attente est une table linéaire avec des opérations restreintes ; appelé la queue de la file d'attente, et l'opération de suppression est effectuée. La fin est appelée le chef de l'équipe.

Quelle structure de données est une file d'attente ?

L'environnement d'exploitation de cet article : système Windows 10, ordinateur thinkpad t480.

Une file d'attente est une structure de données linéaire.

Une file d'attente est une table linéaire spéciale. La particularité est qu'elle autorise uniquement les opérations de suppression à l'avant (avant) de la table, et les opérations d'insertion à l'arrière (arrière) de la table. comme une pile, une file d'attente est une liste linéaire avec des opérations restreintes. L'extrémité qui effectue l'opération d'insertion est appelée la queue de la file d'attente, et l'extrémité qui effectue l'opération de suppression est appelée la tête de la file d'attente. Lorsqu’il n’y a aucun élément dans la file d’attente, on parle de file d’attente vide.

Les éléments de données de la file d'attente sont également appelés éléments de file d'attente. L'insertion d'un élément de file d'attente dans la file d'attente est appelée mise en file d'attente, et la suppression d'un élément de file d'attente de la file d'attente est appelée sortie de file d'attente. Étant donné que la file d'attente autorise uniquement l'insertion à une extrémité et la suppression à l'autre extrémité, seul l'élément qui entre dans la file d'attente le plus tôt peut être supprimé de la file d'attente en premier. La file d'attente est donc également appelée premier entré, premier sorti (FIFO - premier en premier sorti) liste linéaire.

File d'attente séquentielle

Pour établir une structure de file d'attente séquentielle, vous devez allouer statiquement ou demander dynamiquement un espace de stockage continu et définir deux pointeurs pour la gestion. L'un est le pointeur de tête avant, qui pointe vers l'élément de tête ; l'autre est le pointeur arrière, qui pointe vers l'emplacement de stockage de l'élément suivant dans la file d'attente, comme indiqué sur la figure

Quelle structure de données est une file dattente ?

Chaque fois qu'un élément est inséré en fin de file d'attente, front augmente de 1 ; chaque fois qu'un élément est supprimé de la tête de file d'attente, front augmente de 1. Au fur et à mesure des opérations d'insertion et de suppression, le nombre d'éléments de file d'attente continue de changer et l'espace de stockage occupé par la file d'attente se déplace également dans l'espace continu alloué à la structure de file d'attente. Lorsque front=rear, il n’y a aucun élément dans la file d’attente, appelée file d’attente vide. Lorsque l'arrière augmente au-delà de l'espace continu qui pointe vers l'allocation, la file d'attente ne peut plus insérer de nouveaux éléments, mais il reste souvent une grande quantité d'espace disponible qui n'est pas occupé à ce moment-là. Ces espaces sont des unités de stockage qui ont été occupées par. éléments de file d’attente qui ont été retirés de la file d’attente.

Phénomène de débordement dans la file d'attente séquentielle :

(1) Phénomène de « sous-débordement » : lorsque la file d'attente est vide, le phénomène de débordement provoqué par le fonctionnement de la file d'attente. Le « sous-débit » est un phénomène normal et est souvent utilisé comme condition pour le transfert de contrôle de programme.

(2) Phénomène de « véritable débordement » : Lorsque la file d'attente est pleine, une opération push sur la pile provoquera un débordement d'espace. Le « vrai débordement » est une condition d'erreur et doit être évité.

(3) Phénomène de "faux débordement": Étant donné que les pointeurs de tête et de queue ne font qu'augmenter mais ne diminuent pas pendant les opérations de mise en file d'attente et de sortie de file d'attente, l'espace de l'élément supprimé ne peut jamais être réutilisé. Lorsque le nombre réel d'éléments dans la file d'attente est bien inférieur à la taille de l'espace vectoriel, l'opération de file d'attente peut ne pas être possible car le pointeur de queue a dépassé la limite supérieure de l'espace vectoriel. Ce phénomène est appelé « faux débordement ».

File d'attente circulaire

Lors de l'utilisation réelle d'une file d'attente, afin de rendre l'espace de la file d'attente réutilisable, l'utilisation de la file d'attente est souvent légèrement améliorée : quelle que soit l'insertion ou la suppression , une fois Lorsque le pointeur arrière est incrémenté de 1 ou que le pointeur avant est incrémenté de 1 et dépasse l'espace de file d'attente alloué, laissez-le pointer vers la position de départ de cet espace continu. Si vous passez réellement de MaxSize-1 de 1 à 0, vous pouvez utiliser les opérations restantes Rear%MaxSize et Front%MaxSize pour y parvenir. Cela imagine en fait l'espace de file d'attente comme un espace circulaire, et les unités de stockage dans l'espace circulaire sont utilisées de manière cyclique. La file d'attente ainsi gérée est également appelée file d'attente circulaire. En plus de quelques applications simples, la file d'attente vraiment pratique est la file d'attente circulaire.

Dans une file d'attente circulaire, lorsque la file d'attente est vide, il y a avant=arrière, et lorsque tout l'espace de la file d'attente est plein, il y a aussi avant=arrière. Afin de distinguer les deux situations, il est stipulé que la file d'attente circulaire ne peut contenir au maximum que des éléments de file d'attente MaxSize-1. Lorsqu'il ne reste qu'une seule unité de stockage vide dans la file d'attente circulaire, la file d'attente est pleine. Par conséquent, la condition pour que la file d'attente soit vide est front=rear et la condition pour que la file d'attente soit pleine est front=(rear+1)%MaxSize. La situation des files d'attente vides et pleines est la suivante :

Quelle structure de données est une file dattente ?

Recommandé : "Vidéo de programmation"

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
2 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Repo: Comment relancer ses coéquipiers
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
3 Il y a quelques semaines By DDD

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Deque en Python : implémentation de files d'attente et de piles efficaces Deque en Python : implémentation de files d'attente et de piles efficaces Apr 12, 2023 pm 09:46 PM

deque en Python est un deque de bas niveau hautement optimisé, utile pour implémenter des files d'attente et des piles Pythoniques élégantes et efficaces, qui sont les types de données basés sur des listes les plus courants en informatique. Dans cet article, Yun Duojun apprendra ce qui suit avec vous : Commencez à utiliser deque pour afficher et ajouter efficacement des éléments. Accédez à n'importe quel élément de deque. Utilisez deque pour créer une file d'attente efficace. une liste Python et des éléments contextuels. Les opérations sont généralement très efficaces. Si la complexité temporelle est exprimée en Big O, alors on peut dire qu'ils sont O(1). Et lorsque Python doit réallouer de la mémoire pour augmenter la liste sous-jacente afin d'accepter de nouveaux éléments, ces

Comment utiliser Supervisor pour gérer la file d'attente ThinkPHP6 ? Comment utiliser Supervisor pour gérer la file d'attente ThinkPHP6 ? Jun 12, 2023 am 08:51 AM

À mesure que les applications Web continuent de se développer, nous devons gérer un grand nombre de tâches pour maintenir la stabilité et la disponibilité de l'application. Utiliser un système de file d’attente est une solution. ThinkPHP6 fournit un système de file d'attente intégré pour gérer les tâches. Cependant, gérer un grand nombre de tâches nécessite une meilleure gestion des files d'attente, ce qui peut être réalisé à l'aide de Supervisor. Cet article explique comment utiliser Supervisor pour gérer les files d'attente ThinkPHP6. Avant cela, nous devons comprendre quelques concepts de base : le système de file d'attente est

Application de la technologie de file d'attente au délai de message et aux nouvelles tentatives de message en PHP et MySQL Application de la technologie de file d'attente au délai de message et aux nouvelles tentatives de message en PHP et MySQL Oct 15, 2023 pm 02:26 PM

Application de la technologie de file d'attente au délai de message et aux nouvelles tentatives de message dans PHP et MySQL Résumé : Avec le développement continu des applications Web, la demande de traitement hautement simultané et de fiabilité du système devient de plus en plus élevée. En tant que solution, la technologie de file d'attente est largement utilisée dans PHP et MySQL pour implémenter des fonctions de délai de message et de nouvelle tentative de message. Cet article présentera l'application de la technologie de file d'attente dans PHP et MySQL, y compris les principes de base des files d'attente, les méthodes d'utilisation des files d'attente pour implémenter le délai de message et les méthodes d'utilisation des files d'attente pour implémenter les nouvelles tentatives de message, et donnera

Stratégies d'analyse et d'optimisation des performances des files d'attente Java Queue Stratégies d'analyse et d'optimisation des performances des files d'attente Java Queue Jan 09, 2024 pm 05:02 PM

Analyse des performances et stratégie d'optimisation de JavaQueue Résumé de la file d'attente : La file d'attente (file d'attente) est l'une des structures de données couramment utilisées en Java et est largement utilisée dans divers scénarios. Cet article abordera les problèmes de performances des files d'attente JavaQueue sous deux aspects : l'analyse des performances et les stratégies d'optimisation, et donnera des exemples de code spécifiques. Introduction La file d'attente est une structure de données premier entré, premier sorti (FIFO) qui peut être utilisée pour implémenter le mode producteur-consommateur, la file d'attente des tâches du pool de threads et d'autres scénarios. Java fournit une variété d'implémentations de files d'attente, telles que Arr

En Java, quelle est la différence entre la méthode add() et la méthode offer() dans la file d'attente ? En Java, quelle est la différence entre la méthode add() et la méthode offer() dans la file d'attente ? Aug 27, 2023 pm 02:25 PM

La file d'attente en Java est une structure de données linéaire avec plusieurs fonctions. La file d'attente a deux points de terminaison et suit le principe premier entré, premier sorti (FIFO) pour insérer et supprimer ses éléments. Dans ce didacticiel, nous découvrirons deux fonctions importantes des files d'attente en Java, à savoir add() et Offer(). Qu'est-ce qu'une file d'attente ? Queue en Java est une interface qui étend les packages util et collection. Les éléments sont insérés dans le backend et supprimés du frontend. Les files d'attente en Java peuvent être implémentées à l'aide de classes telles que les listes chaînées, DeQueue et les files d'attente prioritaires. Une file d'attente prioritaire est une forme étendue d'une file d'attente normale, dans laquelle chaque élément a une priorité. La méthode add() de la file d'attente est utilisée pour insérer des éléments dans la file d'attente. Il définira l'élément (comme

Plan d'implémentation de la surveillance des tâches de file d'attente et de la planification des tâches en PHP et MySQL Plan d'implémentation de la surveillance des tâches de file d'attente et de la planification des tâches en PHP et MySQL Oct 15, 2023 am 09:15 AM

Implémentation de la surveillance des tâches de file d'attente et de la planification des tâches dans PHP et MySQL Introduction Dans le développement d'applications Web modernes, la file d'attente de tâches est une technologie très importante. Grâce aux files d'attente, nous pouvons mettre en file d'attente certaines tâches qui doivent être exécutées en arrière-plan et contrôler le temps d'exécution et l'ordre des tâches grâce à la planification des tâches. Cet article présentera comment implémenter la surveillance et la planification des tâches dans PHP et MySQL, et fournira des exemples de code spécifiques. 1. Principe de fonctionnement de la file d'attente La file d'attente est une structure de données premier entré, premier sorti (FIFO) qui peut être utilisée pour

Méthodes d'optimisation des files d'attente et du traitement asynchrone dans le système de vente flash PHP Méthodes d'optimisation des files d'attente et du traitement asynchrone dans le système de vente flash PHP Sep 19, 2023 pm 01:45 PM

Méthodes d'optimisation des files d'attente et du traitement asynchrone dans le système de vente flash PHP Avec le développement rapide d'Internet, diverses activités préférentielles sur les plateformes de commerce électronique, telles que les ventes flash et les ventes urgentes, sont également devenues le centre d'intérêt des utilisateurs. Cependant, cette demande élevée d’utilisateurs simultanés constitue un énorme défi pour les applications PHP traditionnelles. Afin d'améliorer les performances et la stabilité du système et de résoudre la pression causée par les demandes simultanées, les développeurs doivent optimiser le système de vente flash. Cet article se concentrera sur les méthodes d'optimisation obtenues grâce aux files d'attente et au traitement asynchrone dans le système de vente flash PHP, et donnera des exemples de code spécifiques.

Comment implémenter la confirmation des messages de file d'attente et la gestion des échecs de consommation en PHP et MySQL Comment implémenter la confirmation des messages de file d'attente et la gestion des échecs de consommation en PHP et MySQL Oct 15, 2023 pm 01:46 PM

Méthodes d'implémentation de confirmation des messages de file d'attente et de gestion des échecs de consommation dans PHP et MySQL. La file d'attente est un mécanisme de transmission de messages courant, qui peut aider à résoudre les problèmes de concurrence élevée dans le système et à réaliser un traitement et un découplage asynchrones. Dans la conception de la file d'attente, la confirmation des messages et la gestion des échecs de consommation sont des liens très importants. Cet article explique comment utiliser PHP et MySQL pour implémenter la confirmation des messages de file d'attente et la gestion des échecs de consommation, et fournit des exemples de code spécifiques. La confirmation du message est dans la file d'attente. La confirmation du message signifie qu'une fois que le consommateur a traité avec succès le message, il l'envoie à la file d'attente.