Pile et file d'attente:
Il est généralement utilisé comme un outil pour les programmeurs pour aider à la conception des algorithmes, avec un cycle de vie court et est créé uniquement au moment de l'exécution;
L'accès est restreint et à un certain moment, une seule données peut être lue ou supprimée;
Il s'agit d'une structure abstraite, avec un mécanisme de mise en œuvre interne qui est invisible pour les utilisateurs, tels que l'utilisation de tableaux et de listes liées pour implémenter la pile.
Simuler la structure de la pile
Dans le même temps, une seule données est autorisée à être accessible, et la complexité temporelle du plus tard pour la première place pour la pile et la sortie est O (1), c'est-à-dire qu'elle ne dépend pas du nombre d'éléments de données dans la pile. L'opération est relativement rapide, en utilisant un tableau comme structure de stockage de la pile
Stacks de classe publique <T> {private int max; Privé T [] ary; Top int privé; // pointeur, indice de l'élément supérieur des piles publiques de pile (int taille) {this.max = size; ary = (t []) nouvel objet [max]; top = -1; } // Stack public void push (t data) {if (! Isull ()) ary [++ top] = data; } // pile public t pop () {if (isEmpty ()) {return null; } return ary [top--]; } // Affichez le haut de la pile public t peek () {return ary [top]; } // est la pile booléenne publique vide iSEmpty () {return top == -1; } // est la pile Full public booléan isull () {return top == max - 1; } // size public int size () {return top + 1; } public static void main (String [] args) {stacks <Integer> stack = new Stacks <Integer> (3); pour (int i = 0; i <5; i ++) {stack.push (i); System.out.println ("Size:" + Stack.size ()); } pour (int i = 0; i <5; i ++) {Integer peek = stack.Peek (); System.out.println ("Peek:" + peek); System.out.println ("Size:" + Stack.size ()); } pour (int i = 0; i <5; i ++) {entier pop = stack.pop (); System.out.println ("pop:" + pop); System.out.println ("Size:" + Stack.size ()); } System.out.println ("----"); pour (int i = 5; i> 0; i--) {stack.push (i); System.out.println ("Size:" + Stack.size ()); } pour (int i = 5; i> 0; i--) {Integer peek = stack.Peek (); System.out.println ("Peek:" + peek); System.out.println ("Size:" + Stack.size ()); } pour (int i = 5; i> 0; i--) {entier pop = stack.pop (); System.out.println ("pop:" + pop); System.out.println ("Size:" + Stack.size ()); }}} Dans l'exemple ci-dessus, il existe un règlement MaxSize, car le tableau doit être dimensionné. Si vous souhaitez ne pas avoir de limite, vous pouvez utiliser d'autres structures pour le stockage, et bien sûr, vous pouvez également nouveau une gamme de nouvelles longueurs.
Exemple, utilisez le stockage LinkedList pour implémenter la pile
classe publique StackSSS <T> {Datas privé LinkedList <T>; public stackss () {dataS = new LinkedList <T> (); } // Mettez la pile publique void push (t data) {datas.addlast (data); } // Mettez la pile publique t pop () {return dataS.Removelast (); } // Vérifiez le haut de la pile public t peek () {return dataS.getLast (); } // si la pile est vide publique booléen isEmpty () {return dataS.Isempty (); } // size public int size () {return datas.size (); } public static void main (String [] args) {stacks <Integer> stack = new Stacks <Integer> (3); pour (int i = 0; i <5; i ++) {stack.push (i); System.out.println ("Size:" + Stack.size ()); } pour (int i = 0; i <5; i ++) {Integer peek = stack.Peek (); System.out.println ("Peek:" + peek); System.out.println ("Size:" + Stack.size ()); } pour (int i = 0; i <5; i ++) {entier pop = stack.pop (); System.out.println ("pop:" + pop); System.out.println ("Size:" + Stack.size ()); } System.out.println ("----"); pour (int i = 5; i> 0; i--) {stack.push (i); System.out.println ("Size:" + Stack.size ()); } pour (int i = 5; i> 0; i--) {stack.push (i); System.out.println ("Size:" + Stack.size ()); } pour (int i = 5; i> 0; i--) {Integer peek = stack.Peek (); System.out.println ("Peek:" + peek); System.out.println ("Size:" + Stack.size ()); } pour (int i = 5; i> 0; i--) {entier pop = stack.pop (); System.out.println ("pop:" + pop); System.out.println ("Size:" + Stack.size ()); }}}Exemple, Ordre inverse du mot, en utilisant la structure STATCK
classe publique WordReverse {public static void main (String [] args) {reverse ("co., Ltd."); } static void reverse (String word) {if (word == null) return; Stackss <actocarac> stack = new StackSS <Caracter> (); char [] chararray = word.tocharArray (); int len = chararray.length; for (int i = 0; i <len; i ++) {stack.push (chararray [i]); } StringBuilder sb = new StringBuilder (); while (! stack.isempty ()) {sb.append (stack.pop ()); } System.out.println ("After Inversion:" + sb.toString ()); }}Imprimer:
Après le renversement: style social
Fixe de simulation (file d'attente générale, file d'attente à double extrémité, file d'attente prioritaire)
file d'attente:
Tout d'abord, faites face aux problèmes de file d'attente. Première file d'attente, premier processus, première rangée, deuxième rangée, etc. Le processus précédent est terminé et la complexité temporelle des opérations d'insertion et de suppression est O (1). Insérez de l'arrière et retirez la file d'attente à double extrémité de l'avant:
C'est-à-dire que vous pouvez insérer et retirer aux deux extrémités de la file d'attente: insertleft, insertright, removeleft, Removeright
Fonctions contenant de la pile et des files d'attente. Si vous supprimez l'insertleft et la suppression, ce sera la même chose que la pile; Si vous supprimez l'insertleft et le removeright, ce sera le même que la file d'attente. Généralement, la fréquence d'utilisation est faible et la complexité temporelle O (1)
File d'attente prioritaire:
Maintenez une séquence interne triée par priorité. Lors de l'insertion, vous devez comparer et trouver la position d'insertion, complexité temporelle O (n), supprimer o (1)
/ * * La file d'attente en premier dans First Out, un pointeur indique la position d'insertion et un pointeur indique la position de l'élément de données supprimé * / classe publique queueq <T> {private int max; Privé T [] ary; Front privé; // Le chef de l'équipe indique la position de l'élément de données supprimé dans l'arrière privé; // La queue de l'équipe indique que la position de l'élément de données est inséré int nitems; // le nombre réel d'éléments de données publics queueq (int taille) {this.max = size; ary = (t []) nouvel objet [max]; front = 0; arrière = -1; nitems = 0; } // Insérez la queue de l'insert de vide public de file d'attente (t t) {if (arrière == max - 1) {// Il a atteint la fin de la file d'attente réelle, à partir du début, arrière = -1; } ary [++ arrière] = t; Nitems ++; } // Supprimez la tête de l'équipe publique T Remove () {t temp = ary [front ++]; if (front == max) {// La file d'attente a atteint la fin, commencez depuis le début, commencez depuis le début, commencez depuis le début, commencez depuis le début, 0; } nitems--; Tempère de retour; } // Voir la tête de l'équipe publique t peek () {return ary [front]; } public boolean isEmpty () {return nitems == 0; } public boolean isfull () {return nitems == max; } public int size () {return nitems; } public static void main (String [] args) {queueq <Integer> queue = new queueq <Integer> (3); pour (int i = 0; i <5; i ++) {queue.insert (i); System.out.println ("Size:" + Queue.Size ()); } pour (int i = 0; i <5; i ++) {Integer peek = queue.Peek (); System.out.println ("Peek:" + peek); System.out.println ("Size:" + Queue.Size ()); } pour (int i = 0; i <5; i ++) {Integer retire = queue.Remove (); System.out.println ("Supprime:" + Supprimer); System.out.println ("Size:" + Queue.Size ()); } System.out.println ("----"); pour (int i = 5; i> 0; i--) {queue.insert (i); System.out.println ("Size:" + Queue.Size ()); } pour (int i = 5; i> 0; i--) {Integer peek = queue.Peek (); System.out.println ("Peek:" + peek); System.out.println ("Size:" + Queue.Size ()); } pour (int i = 5; i> 0; i--) {Integer retire = queue.Remove (); System.out.println ("Supprime:" + Supprimer); System.out.println ("Size:" + Queue.Size ()); }}} / * * File d'attente à double extrémité <span style = "blanc-espace: pre"> </span> insérer et supprimer aux deux extrémités * / classe publique queueqt <T> {Liste liée privée <T>; Public QueueQt () {list = new LinkedList <T> (); } // Insérez la tête de file d'attente public void insertleft (t t) {list.addFirst (t); } // insérer la queue de queue publique void insertright (t t) {list.addlast (t); } // Supprimez la tête de file d'attente publique t Removeleft () {return list.removeFirst (); } // Supprimez la fin de l'équipe publique T Removeright () {return list.removelast (); } // Voir la tête de l'équipe publique t peekleft () {return list.getFirst (); } // Affiche la fin de l'équipe publique t peekRight () {return list.getLast (); } public boolean isEmpty () {return list.isempty (); } public int size () {return list.size (); }} / * * La file d'attente de priorité est triée par priorité, et il s'agit d'une file d'attente commandée * / classe publique queueqp {private int max; privé int [] ary; Int nitems privé; // le nombre réel d'éléments de données public fitreQp (int size) {this.max = size; ary = new int [max]; nitems = 0; } // Insérez la fin de l'insert de la file d'attente publique (int t) {int j; if (nitems == 0) {ary [nitems ++] = t; } else {for (j = nitems - 1; j> = 0; j--) {if (t> ary [j]) {ary [j + 1] = ary [j]; // Attribuez le précédent à celui suivant équivalent à l'utilisation du tri de l'insertion. La séquence donnée est à l'origine ordonnée, donc l'efficacité o (n)} else {Break; }} ary [j + 1] = t; Nitems ++; } System.out.println (arrays.tostring (ary)); } // Supprimer la tête de l'équipe public int dis do dans () {return ary [- nitems]; // supprime la petite priorité} // Voir la priorité la plus basse de l'équipe publique int peekmin () {return ary [nitems - 1]; } public boolean isEmpty () {return nitems == 0; } public boolean isfull () {return nitems == max; } public int size () {return nitems; } public static void main (String [] args) {queueqp fitre = new QueueQp (3); queue.insert (1); queue.insert (2); queue.insert (3); int dis do dans = queue.remove (); System.out.println ("Supprime:" + Supprimer); }}