Comment implémenter la pile et la file d'attente Java

Stack and Queue

1. Stack (Stack) est une structure de données dernier entré, premier sorti (LIFO)

2. Queue (Queue) est une structure premier entré, premier sorti (premier entré, premier sorti, FIFO)

Pile (Stack)

La pile est une structure linéaire Par rapport au tableau, les opérations correspondant à la pile sont un sous-ensemble du tableau.

Il ne peut ajouter des éléments qu'à une extrémité et supprimer des éléments d'une extrémité (cette extrémité est appelée le haut de la pile).

La pile est une structure de données largement utilisée. Dans l'utilisation des ordinateurs, les piles sont largement utilisées, comme les analyseurs lexicaux dans les compilateurs, les machines virtuelles Java, les opérations d'annulation (Undo) dans les logiciels et les opérations de retour dans les navigateurs. implémentation des appels de fonction dans le compilateur, etc.

Implémentation de la pile

E See More pop()Pop l'élément supérieur de la pileO(1) E peek()Afficher l'élément supérieur de la pileO(1)int getSize()Obtenir le nombre d'éléments dans la pileO(1)boolean isEmpty()Jugez si la pile est videO(1)

Interface	Description	Complexité
void push(E e)	Ajouter des éléments à la pile	O(1)
		Répartir également

Explication : push et les opérations pop sont effectuées à la fin, il est possible de déclencher le redimensionnement, mais la répartition uniforme est O(1).

Si vous souhaitez en savoir plus sur l'analyse de la complexité temporelle, veuillez prêter attention à l'article que l'auteur mettra à jour ultérieurement :
Quel problème O(n) explique-t-il ?

L'implémentation de la pile peut être implémentée via un tableau ou une liste chaînée. Ici, nous utilisons un tableau pour implémenter l'interface ci-dessus.

Dans la conception de la pile, l'utilisateur ne fait attention qu'à l'accès à l'élément supérieur et à la longueur de la pile, le code de conception est donc le suivant :

Les lecteurs peuvent utiliser la

stack cette structure de données pour résoudre le problème Non .20 sur LeetCode : Pour les parenthèses valides, voir aussi Décompte quotidien : Parenthèses valides.

Queue

La file d'attente est également une structure de données linéaire Par rapport aux tableaux, les opérations correspondant aux files d'attente sont un sous-ensemble de tableaux.

Les éléments ne peuvent être ajoutés que depuis une extrémité (la fin de la file d'attente) et les éléments ne peuvent être supprimés que depuis l'autre extrémité (la tête de la file d'attente).

L'application de la file d'attente peut être reflétée dans la playlist sur le lecteur, l'objet de flux de données, la structure de transmission de données asynchrone (fichier IO, communication pipe, socket, etc.). Bien sûr, la file d'attente est la plus intuitive.

Mise en œuvre de la file d'attente

InterfaceDescriptionComplexitévoid enqueue(E e)enqueueO(1) sharedE sortir de la file d'attente( ) E getFront()int getSize()boolean isEmpty()La saisie de la file d'attente commence à la fin de la file d'attente et le redimensionnement peut être déclenché, de sorte que le l'amortissement est O(1). La suppression de la file d'attente est en tête de la file d'attente et l'implémentation du tableau nécessite de déplacer tous les éléments à chaque fois, O(n).

Dequeue	O(n)
Obtenir le premier élément de la file d'attente	O(1)
Obtenir le nombre d'éléments de la file d'attente	O( 1)
Détermine si la file d'attente est vide	O(1)

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!