Nous avons déjà été exposés à plusieurs structures de données, notamment des tableaux, des listes liées, des tables de hachage et des arbres rouges et noirs (arbres de requête binaire). Aujourd'hui, regardons une autre structure de données: pile.
Qu'est-ce qu'une pile? Voyons d'abord un exemple: une pile équivaut à un baril en bois très étroit. Lorsque nous mettons les choses dans le baril en bois et que nous retirons les choses, nous constaterons que la chose que nous mettons en bas au début, et la première chose que nous avons retirée était celle que nous venons de mettre. Par conséquent, la pile est un tel conteneur que d'abord dans et hors (FirstInlastout, ou plus tard et premier). Il n'a qu'une bouche, met des éléments dans cette bouche et retire également des éléments dans cette bouche. Ensuite, apprenons la pile dans JDK ensuite.
1. Introduction de base et utilisation du vecteur et de la pile
Regardons d'abord la définition de JDK:
Stack de classe publique <E> étend Vector <e> {À partir de ce qui précède, nous pouvons voir que la pile est héritée du vecteur, nous devons donc également avoir une certaine compréhension du vecteur.
Vector: tableaux dynamiques en file
Stack: Vector héritage, une pile de filetage implémentée en fonction des tableaux dynamiques;
1. Caractéristiques du vecteur et de la pile:
Vector et ArrayList sont fondamentalement les mêmes. La différence est que le vecteur est fileté et ajoutera le mot-clé synchronisé avant les éventuelles méthodes de filetage;
Vector: vitesse d'accès aléatoire rapide, mauvaise insertion et performances d'élimination (caractéristiques du tableau); prend en charge les éléments nuls; a l'ordre; Les éléments peuvent être répétés; thread-saa;
Stack: After-in, First-Out, met en œuvre certaines méthodes d'opérations de pile de base (en fait, elle n'est pas seulement après-in, d'abord-out, car héritée du vecteur, il peut y avoir de nombreuses opérations, et en un sens, ce n'est pas une pile);
2.Vecteur et structure de pile:
Classe vectorielle
C'est fondamentalement la même chose que ArrayList, et les principales différences sont les suivantes:
1. Le vecteur est en file d'attente
2. La croissance de l'arraylist est incompatible avec la croissance des vecteurs
D'autres, si les méthodes de construction sont incohérentes, le vecteur peut initialiser la capacité de la capacité par la méthode de construction, et il existe d'autres méthodes, telles que l'indice de la méthode. Le vecteur prend en charge la recherche et la recherche à partir de l'emplacement spécifié; De plus, Vector a également quelques méthodes redondantes avec des fonctions en double, telles que la méthode AddElement et Settelementat. La raison en est due à des raisons historiques. Par exemple, la méthode AddElement est laissée auparavant. Lorsque le cadre de collection a été introduit, Vector a rejoint la famille de la collection et a changé pour implémenter l'interface de liste. Certaines méthodes définies dans l'interface de liste doivent être implémentées. Cependant, pour des raisons de compatibilité, les anciennes méthodes ne peuvent pas être supprimées, donc certaines anciennes méthodes avec redondance sont apparues. Maintenant, il a été remplacé par ArrayList et est essentiellement rarement utilisé, alors comprenez.
Classe de pile
Le fonctionnement de base de la pile est réalisé. La méthode est la suivante:
Public Stack ();
Créer une pile vide
public synchronisé e peek ();
Renvoie la valeur en haut de la pile;
public e push (e item);
Opération de pile;
public synchronisé e pop ();
Opération hors stock;
public booléen vide ();
Déterminer si la pile est vide;
Public synchronisé Int Search (objet O);
Renvoie la position de l'objet dans la pile;
Pour la pile ci-dessus, nous n'utiliserons que fréquemment la méthode ci-dessus. Bien qu'il hérite du vecteur et dispose de nombreuses méthodes, il ne sera pas utilisé, mais il est simplement traité comme une pile.
3. Utilisation de base
Certaines méthodes de vecteur sont utilisées comme suit. De plus, la méthode de traversée de vecteur est la même que celle de ArrayList. Vous pouvez utiliser ForEach, Iterator et pour la traversée de boucle;
import java.util.arrays; import java.util.iterator; import java.util.list; import java.util.listiterator; import java.util.vector; public class test {public static void main (String [] args) {vector <nteger> vector = new vector <Integer> (); pour (int i = 0; i <10; i ++) {vector.add (i); } // imprimer System.out.println (vector.toString ()); // size () System.out.println (vector.size ()); // contient System.out.println (vector.contains (2)); // iterator iterator <Integer> iterator = vector.iterator (); while (iterator.hasnext ()) {System.out.print (iterator.next () + ""); } // toArray Object [] objarr = vector.toArray (); System.out.println ("/ nobjarr:" + arrays.aslist (objarr)); Entier [] intarr = vector.toArray (nouveau entier [vector.size ()]); System.out.println ("intarr:" + arrays.aslist (intarr)); // ajouter vector.add (5); // Retirez Vector.Remove (5); System.out.println (vecteur); // contientAll System.out.println (vector.containsall (arrays.aslist (5,6))); // addall vector.addall (arrays.aslist (555 666)); System.out.println (vecteur); // Removeall vector.removeall (arrays.aslist (555 666)); System.out.println (vecteur); // Addall Method Vector.Addall (5, arrays.aslist (666 666, 6)); System.out.println (vecteur); // Get Method System.out.println (vector.get (5)); // Définir la méthode Vector.Set (5, 55); System.out.println (vector.get (5)); // ajouter la méthode vector.add (0, 555); System.out.println (vecteur); // supprimer la méthode Vector.Remove (0); System.out.println (vecteur); // indexof méthode System.out.println (vector.indexof (6)); // Méthode LastIndexof System.out.println (Vector.LastIndexof (6)); // Méthode ListIterator ListeTiterator <Integer> listIterator = vector.ListIterator (); System.out.println (listIterator.haspRevious ()); // ListIterator (index) Méthode ListeTiterator <Integer> iListIterator = vector.ListIterator (5); System.out.println (iListIterator.Previous ()); // Méthode sublilique System.out.println (Vector.Sublist (5, 7)); // Clector Vector.Clear (); System.out.println (vecteur); }}Certaines méthodes de pile sont utilisées comme suit. Étant donné que la pile hérite du vecteur, la pile peut également utiliser des méthodes que le vecteur peut utiliser. Ce qui suit répertorie quelques exemples de méthodes uniques de Stack. Il est très simple, qui sont des opérations de base de la pile. En plus de plusieurs méthodes de traversée de Vector, Stack a également ses propres méthodes de traversée uniques (en utilisant la méthode vide et la méthode POP pour atteindre la traversée du haut en bas de la pile):
import java.util.stack; public class test {public static void main (String [] args) {stack <Integer> stack = new Stack <Integer> (); pour (int i = 0; i <10; i ++) {stack.add (i); } System.out.println (pile); System.out.println (Stack.Peek ()); stack.push (555); System.out.println (pile); System.out.println (stack.pop ()); System.out.println (pile); System.out.println (Stack.Empty ()); System.out.println (Stack.Search (6)); System.out.println ("Stack Traversal:"); while (! stack.empty ()) {System.out.print (stack.pop () + ""); }}}Sous-section:
Le vecteur est en sécurité, mais a de mauvaises performances. Généralement, ArrayList est utilisé à moins qu'il n'y ait des exigences particulières;
Si vous prévoyez d'utiliser la pile comme pile, vous devez honnêtement et strictement suivre les plusieurs opérations de la pile. Sinon, il serait significatif d'utiliser la pile, et il serait préférable d'utiliser Vector;
2. Structure Vector & Stacke et stockage sous-jacent
Vector de classe publique <E> étend AbstractList <E> implémente List <e>, RandomAccess, Clonable, Java.io.Serializable
Vector est une classe d'implémentation de la liste. En fait, Vector est également un conteneur de liste basé sur l'implémentation du tableau. Ses fonctions et le code d'implémentation sont fondamentalement les mêmes que ArrayList. Alors, qu'est-ce qui est différent? La première est que lorsque le tableau est élargi, le vecteur est * 2 et que le ArrayList est * 1,5 + 1; L'autre est que le vecteur est en filetage, tandis que ArrayList ne l'est pas. L'approche du vecteur à filetage est d'ajouter un mot-clé synchronisé à chaque méthode pour l'assurer. Mais ici, le vecteur n'est plus officiellement (reconnu par tout le monde) et n'est pas recommandé. C'est officiellement parce que sa méthode de sécurité des fils est de verrouiller toute la méthode, ce qui conduit à une faible efficacité. Alors, y a-t-il une meilleure solution? En fait, on ne peut pas dire qu'il y en a un, mais il y a vraiment un, Collection.SynchronizedList ()
Étant donné que la pile est héritée et basée sur Vector, jetons un coup d'œil à certaines définitions et aux codes source de la méthode de Vector:
// La couche sous-jacente utilise un tableau pour stocker l'objet protégé des données [] elementData; // le nombre d'éléments protégés Int élémentCount; // Personnalisez l'expansion du conteneur et la taille de la taille de l'incrément protégée INT CAPACITION INCRÉMENT; Vector public (int initialCapacity, int CapacityIncrement) {super (); // des limites de sortie vérifiez si (initialCapacity <0) lance un nouveau IllégalArgumentException ("Capacité illégale:" + InitialCapacity); // initialise le tableau this.elementData = nouvel objet [initialCapacity]; this.capacityIncrement = CapaceIncrement; } // Utilisez la méthode de verrouillage des mots clés synchronisée pour s'assurer qu'un seul thread peut manipuler la méthode en même temps booléen synchronisé publique (e e) {modCount ++; // Elagement Check AssurecapacityHelper (ElementCount + 1); elementData [elementCount ++] = e; Retour Vrai; } private void assurecapacityHelper (int mincapacity) {// Nombre actuel d'éléments int oldcapacity = elementData .length; // est-il nécessaire d'élargir la capacité si (mincapacity> oldcapacity) {objet [] olddata = elementData; // Si l'expansion du conteneur est personnalisée, augmentez la capacité en fonction de CapacityIncrement, sinon augmenter la capacité de deux fois (* 2) int newcapacity = (CapacitéIncrement> 0)? (OldCapacity + CapacitéIncrement): (OldCapacity * 2); if (newCapacity <mincapacity) {newCapacity = mincapacity; } // Array Copy ElementData = arrays.copyof (elementData, newCapacity); }}Vector Voir simplement cela. Si l'autre méthode de pile n'est pas appelée, elle ne sera pas analysée. Si vous ne comprenez pas, vous pouvez vérifier l'analyse du code source ArrayList.
3. Analyse des méthodes principales
1.Peek () - Obtenez l'objet en haut de la pile
/ ** * Obtenez l'objet en haut de la pile, mais ne supprimez pas * / public synchronisé e peek () {// Le nombre actuel d'éléments de conteneur int len = size (); // S'il n'y a pas d'élément, lancez une exception directement si (len == 0) lance un nouveau videstacKexception (); // Call Elementat Méthode pour récupérer le dernier élément du tableau (le dernier élément est en haut de la pile) return elementat (Len - 1); } / ** * Obtenez l'élément à cette position Selon l'index de l'index, cette méthode est dans Vector * / public synchronisé e elementat (int index) {// quitte les limites if (index> = elementCount) {throw new ArrayIndexoutofBoundSexception (index + "> =" + elementCount); } // Obtenez l'élément return (e) elementData [index]; }2.Pop () - éclatez la pile (hors de la pile), obtenez l'objet en haut de la pile et supprimez l'objet du conteneur
/ ** * Bumble la pile, obtenez et supprimez l'objet en haut de la pile * / public synchronisé e pop () {// Enregistrez l'objet en haut de la pile e obj; // le nombre actuel d'éléments de conteneur int len = size (); // Obtenez l'objet en haut de la pile obj via Powek () méthode obj = peek (); // Appelez la méthode de devureelement pour supprimer l'objet en haut de la pile devayelementat (Len - 1); // retour à l'objet en haut de la pile return obj; } / ** * Supprimer l'élément en fonction de l'index index * / public synchronisé void devateElementat (int index) {modCount ++; // Exit Bounds if (index> = elementCount) {throw new ArrayIndexOfBoundSException (index + "> =" + elementCount); } else if (index <0) {throw new ArrayIndexoutofBoundSexception (index); } // Calculez le nombre d'éléments de tableau à déplacer int j = elementCount - index - 1; if (j> 0) {// Déplacez le tableau, supprimez-en un au milieu, alors déplacez l'élément suivant vers l'avant (en déplaçant ici directement l'élément de position d'index, ce qui équivaut à la suppression). ArrayCopy (élémentData, index + 1, elementData, index, j); } // moins 1 élémentCount--; // Définissez le dernier élément du conteneur à vide (car un élément a été supprimé, et les éléments derrière l'indice ont été avancés, donc le dernier était inutile) elementData [elementCount] = null; / * pour laisser GC faire son travail * /}3.Push (élément e) - Push (dans la pile), ajoutez l'objet dans le conteneur et renvoyez-le
/ ** * Ajoutez l'objet dans le conteneur et retournez * / public e push (e item) {// Appelez AddElement à AddElement (item); // renvoie l'élément de retour élément; } / ** * Ajoutez l'élément dans le conteneur. Cette méthode est dans le vecteur * / public synchronisé void adddelement (e obj) {modCount ++; // Elagement Check AssurecapacityHelper (ElementCount + 1); // Mettez l'objet dans le tableau, le nombre d'éléments +1 elementData [elementCount ++] = obj; }4.Search (objet O) - Renvoie la position de l'objet dans le conteneur, le haut de la pile est 1
/ ** * Renvoie la position de l'objet dans le conteneur, le haut de la pile est 1 * / public synchronisé Int Search (objet O) {// Trouvez l'élément du tableau, de la dernière occurrence de int i = LastIndexof (o); // Parce que le haut de la pile compte 1, vous devez utiliser size () - i pour calculer if (i> = 0) {return size () - i; } return -1; }5.Empty () - Le conteneur est-il vide
/ ** * Vérifiez si le conteneur est vide * / public boolean vide () {return size () == 0; }Sous-section:
À ce stade, la méthode de pile est analysée. Étant donné que Stack est finalement basé sur les tableaux, il est toujours facile à comprendre (car il est basé sur ArrayList).
Bien que le code source de Stack dans JDK ait été analysé, il est nécessaire de discuter de celui-ci ici. Je ne sais pas si j'ai trouvé que cette pile ici est très étrange.
(1) Pourquoi la pile est-elle implémentée sur la base des tableaux?
Nous connaissons tous les caractéristiques des tableaux: ils sont pratiques pour l'interrogation sur la base des indices (accès aléatoire), mais la mémoire est fixe et l'efficacité d'expansion de la capacité est faible. Il est facile de penser à la chose la plus appropriée à utiliser des listes liées.
(2) Pourquoi la pile hérite-t-elle?
L'héritage signifie que la pile hérite de la méthode vectorielle, ce qui rend la pile un peu inappropriée, à la fois une liste et une pile. Qu'est-ce qui devrait être une approche raisonnable si vous devez hériter du vecteur: la pile n'hérite pas du vecteur, mais a seulement une référence au vecteur lui-même, l'agrégation est-elle non?
La seule explication est que Stack a été créé par JDK1.0. À ce moment-là, les conteneurs de JDK n'avaient pas uniquement de vecteurs, tels que ArrayList, LinkedList, etc., et comme ils ont déjà un vecteur et peuvent implémenter des fonctions de pile, puis le faire. . . Puisqu'il est idéal d'implémenter la pile avec des listes liées, essayons-le:
import java.util.linkedlist; classe publique LinkedStack <e> {private LinkedList <e> Linked; public LinkedStack () {this.linked = new LinkedList <e> (); } public e push (e item) {this.Linked .AddFirst (item); return item; } public e pop () {if (this.linked.isempty ()) {return null; } return this.linked.removeFirst (); } public e peek () {if (this.linked.isempty ()) {return null; } return this.linked.getFirst (); } public int search (e item) {int i = this.linked.indexof (item); retour i + 1; } public boolean vide () {return this.linked.isempty (); }}La pile implémentée par LinkedList est utilisée ici. Rappelez-vous comme mentionné dans LinkedList, LinkedList implémente l'interface DEQI afin qu'il puisse être utilisé comme pile (premier dans et hors) et une file d'attente (premier dans et hors).
4. La différence entre Vector et ArrayList
Il existe trois classes d'implémentation dans l'interface de liste, à savoir ArrayList, Vector et LinkedList. La liste est utilisée pour stocker plusieurs éléments, peut maintenir l'ordre des éléments et permet la répétition des éléments.
Les différences pertinentes entre les trois classes de mise en œuvre spécifiques sont les suivantes:
1. ArrayList est la classe d'implémentation de liste la plus couramment utilisée, implémentée en interne via Arrays, qui permet un accès aléatoire rapide aux éléments. L'inconvénient des tableaux est qu'il ne peut pas être espacé entre chaque élément. Lorsque la taille du tableau n'est pas satisfaite, la capacité de stockage doit être augmentée. Il est nécessaire de dire que les données des déjà réduites sont copiées dans le nouvel espace de stockage. Lors de l'insertion ou de la suppression des éléments de la position centrale de la liste d'arraie, le tableau doit être copié, déplacé et le coût est relativement élevé. Par conséquent, il convient aux recherches et traversées aléatoires, et non à l'insertion et à la suppression.
2.Vector est également implémenté via des tableaux, la différence est qu'il prend en charge la synchronisation du thread, c'est-à-dire, à un certain moment, un seul thread peut écrire un vecteur pour éviter l'incohérence causée par plusieurs threads écrits en même temps, mais il en coûte beaucoup pour implémenter la synchronisation, donc l'accès est plus lent que l'accès à ArrayList.
3. LinkedList utilise une structure de liste liée pour stocker les données, ce qui est très adapté à l'insertion dynamique et à la suppression des données, et l'accès aléatoire et les vitesses de traversée sont relativement lents. De plus, il fournit également des méthodes qui ne sont pas définies dans l'interface de liste, qui sont spécifiquement utilisées pour faire fonctionner l'en-tête de table et les éléments de queue, et peuvent être utilisées comme piles, files d'attente et files d'attente bidirectionnelles.
5. Une brève compréhension de la file d'attente, de la file d'attente à double extrémité
1. Fitre
Une nouvelle interface java.util.queue a été ajoutée à Java5 pour prendre en charge les opérations de file d'attente communes. Cette interface étend l'interface java.util.collection.
La file d'attente d'interface publique <E> étend la collection <E>
En plus des opérations de collecte de base, les files d'attente fournissent d'autres opérations d'insert, d'extrait et de vérification.
Chaque méthode a deux formulaires: l'une lance une exception (lorsqu'une opération échoue) et l'autre renvoie une valeur spéciale (null ou false, selon l'opération).
Les files d'attente sont généralement (mais pas nécessairement) de trier les éléments individuels dans un FIFO (premier à la première sortie). Cependant, la file d'attente prioritaire et la file d'attente LIFO (ou pile) sont des exceptions. Le premier trie les éléments selon l'ordre naturel du comparateur ou des éléments fournis, et le dernier trie les éléments de LIFO (le plus récent en premier).
Dans la file d'attente FIFO, tous les nouveaux éléments sont insérés à la fin de la file d'attente, et l'élément de retrait est supprimé de l'en-tête de file d'attente.
Lorsque vous utilisez la file d'attente, essayez d'éviter les méthodes ADD () et de supprimer () de collecte, mais utilisez Office () pour ajouter des éléments et utiliser Poll () pour obtenir et supprimer les éléments. Leur avantage est qu'ils peuvent déterminer si le succès est obtenu en renvoyant la valeur, et les méthodes ADD () et Supprimer () lanceront des exceptions lorsqu'ils échouent. Si vous souhaitez utiliser l'extrémité frontale sans retirer l'élément, utilisez la méthode élément () ou peek ().
La méthode de l'offre peut insérer un élément, sinon il renvoie faux. Ceci est différent de la méthode Collection.Add, qui ne peut échouer à ajouter des éléments qu'en lançant une exception non contrôlée.
Les méthodes retire () et poll () suppriment et renvoient l'en-tête de la file d'attente. Quel élément est supprimé de la file d'attente est la fonction de la politique de tri de file d'attente, qui est différente dans diverses implémentations. Les méthodes retire () et poll () ne se comportent différemment que lorsque la file d'attente est vide: la méthode supprime () jette une exception, tandis que la méthode Poll () renvoie NULL.
element () et peek () retourne, mais ne supprimez pas, l'en-tête de file d'attente.
Les implémentations de la file d'attente ne permettent généralement pas l'insertion d'éléments nuls, bien que certaines implémentations (telles que LinkedList) n'interdisent pas l'insertion de Nulls. Même dans les implémentations qui permettent NULL, NULL ne doit pas être inséré dans la file d'attente, car NULL est également utilisé comme valeur de retour spéciale pour la méthode du scrutin, indiquant que la file d'attente ne contient pas d'éléments.
Il convient de noter que la classe LinkedList implémente l'interface de file d'attente, nous pouvons donc utiliser LinkedList comme file d'attente.
Importer Java.util.Queue; import java.util.linkedlist; classe publique TestQueue {public static void main (String [] args) {queue <string> queue = new LinkedList <string> (); queue.offer ("bonjour"); queue.offer ("World!"); queue.offer ("Hello!"); System.out.println (queue.size ()); String Str; while ((str = queue.poll ())! = null) {System.out.print (str); } System.out.println (); System.out.println (queue.size ()); }}2. Deque
L'interface publique Deque <E> étend la file d'attente <e>
Une collection linéaire qui prend en charge l'insertion et l'élimination des éléments aux deux extrémités.
Le nom deque est l'abréviation de la "file d'attente à double fin" et est généralement lue comme "pont".
La plupart des implémentations de Deque n'ont pas de limite fixe sur le nombre d'éléments qu'ils peuvent contenir, mais cette interface prend en charge les files d'attente limitées et les files d'attente à double extrémité sans limites de taille fixe.
Cette interface définit une méthode pour accéder aux éléments aux deux extrémités d'une file d'attente à double extrémité. Fournit des méthodes pour insérer, supprimer et inspecter les éléments. Étant donné que cette interface hérite de la file d'attente de la file d'attente, il existe deux formulaires pour chacune de ses méthodes: l'une jette une exception lorsque l'opération échoue, et l'autre renvoie une valeur spéciale (null ou false, selon l'opération).
un. Lorsque vous utilisez une file d'attente à double extrémité comme file d'attente, vous obtiendrez un comportement FIFO (premier-in, première sortie). Ajoutez un élément à la fin de la file d'attente à double extrémité et retirez l'élément du début de la file d'attente à double extrémité. Les méthodes héritées de l'interface de file d'attente sont entièrement équivalentes à la méthode DEQI, comme indiqué dans le tableau suivant:
né Utilisé comme pile LIFO (Last in First Out). Cette interface doit être utilisée en premier plutôt que des classes de pile héritée. Lorsque vous utilisez une file d'attente à double extrémité comme pile, l'élément est poussé dans le début de la file d'attente à double extrémité et apparaît à partir du début de la file d'attente à double extrémité. La méthode de pile est entièrement équivalente à la méthode DEQI, comme indiqué dans le tableau suivant: