Lors des entretiens, les piles et les files d'attente apparaissent souvent par paires à examiner. Cet article contient le contenu des tests suivants pour la pile et les files d'attente:
(1) Création de pile
(2) Création de file d'attente
(3) Deux piles implémentent une file d'attente
（4）两个队列实现一个栈
(5) Concevez une pile avec la fonction minimale min (), et nécessite que la complexité temporelle de Min, Push, Pop et tous soient O (1)
(6) Déterminez si les séquences push et pop de la pile sont cohérentes
1. Création de pile:
Ensuite, nous créons une pile sous la forme d'une liste liée pour faciliter l'expansion.
Implémentation du code:
Classe publique Stack {Public Node Head; Current de nœud public; // Méthode: Empilement Public Void push (int) {if (head == null) {head = new nœud (data); Node Node = nouveau nœud (données); Node.pre = Current; // Le nœud actuel sera utilisé comme le nœud prédécesseur du nœud actuel. } Node public POP () {if (current == null) {return null;} nœud nœud = current; nœud étant mis sur la pile, actuel un nœud de retour;} nœud de classe {int data; nœud pré; }} public static void main (String [] args) {stack stack = new Stack (); stack.push (1); pop (). Data);Lors de la saisie de la pile, 14 ou 15 lignes de code sont la clé.
Effet de course:
2、队列的创建：
Il existe deux formes de création de files d'attente: basée sur l'implémentation de la structure du tableau (file d'attente séquentielle), et basée sur l'implémentation de la structure de liste liée (file d'attente de chaîne).
Ensuite, nous créerons une file d'attente sous la forme d'une liste liée, afin que la file d'attente soit plus pratique lors de l'expansion. Lorsque la file d'attente est désactivée, commencez à partir du début de la tête de nœud.
Implémentation du code:
Lors de la saisie de la pile, c'est la même chose que l'ajout de nœuds dans une liste liée ordinaire;
Public Class Queue {Public Node Head; Node public Current; // Méthode: Ajouter des nœuds dans la liste liée Public Void Add (ints) {if (head == null) {head = new nœud (data); } else {current.next = nouveau nœud (data); "La file d'attente est vide");} nœud nœud = head; Data; i = 0; i <5; i ++) {queue.add (i);} // .out.println (queue.pop ());}}Effet de course:
3. Deux piles implémentent une file d'attente:
Idées:
La pile 1 est utilisée pour stocker des éléments, la pile 2 est utilisée pour faire éclater des éléments, négatifs et négatifs est positif.
Pour le dire simplement, mettez maintenant les données 1, 2 et 3 dans la pile un, puis sortez de la pile un (3, 2, 1) et mettez-la dans la pile deux, puis les données de la pile deux (1, 2.3) Il est conforme aux règles de la file d'attente, c'est-à-dire négatives et négatives.
Version complète de l'implémentation du code:
Importer java.util.stack; / *** Créé par Smyhvae le 2015/9/9. * / Public Class Queue {Private Stack <Integer> Stack1 = new Stack <> (); // Stack Pr pour effectuer une opération d'agitation iVate Stack <Integer> stack2 = new Stack <> (); // pile pour exécuter le fonctionnement de DeQueue // Méthode: ajoutez une opération d'enquille à la file d'attente publique void push (ints) {stack1.push (data);} / / méthode : Donnez à la file d'attente une opération de désir publique int pop () lève une exception {if (stack2.empty ()) {// Avant de mettre les données dans Stack1 dans Stack2, vous devez vous assurer que Stack2 est vide (ou il est vide au début, Soit les données de Stack2 ont été publiées), sinon l'ordre de désactivation sera gâché, ce qui est facile à oublier while (! stack1.empty ()) {stack2.push (stack1.pop ()); // Ouvrez le Données dans Stack1 et mettez-les dans Stack2 [CODE CODE]}} if (Stack2.Empty ()) {// Lorsque la pile est vide, il y a deux possibilités: 1. Au début, deux piles toutes les données sont vides; 2. Les données de Stack2 sont terminées une nouvelle exception ("Quédik push (1); ));Faites attention à l'ordre du code sur la ligne 22 et la ligne 30, ainsi que les commentaires, et vous devez comprendre attentivement sa signification.
Effet de course:
4. Deux files d'attente implémentent une pile:
Idées:
Mettez 1, 2 et 3 dans la file d'attente 1, puis laissez le top 3 dans la file d'attente 1, mettez les 2 et 3 inférieurs dans la file d'attente 2, et mettez 3 de la file d'attente 1. À ce moment, la file d'attente est vide, puis tout La file d'attente 2 est laissée en file d'attente. . . Circuler tour à tour.
Implémentation du code:
import java.util.arraydeque; import java.util.queue; / *** créé par smyhvae le 2015/9/9. * / public class stack {queue <Integer> queue1 = new Arr AyDeque <Integer> (); <Integer> queue2 = new ArrayDeque <Neger> (); // Méthode: Empilement Public void push (int data) {queue1.add (data); int data; if (queue1.size () == 0) {lancez une nouvelle exception ("Stack est vide"); {data = queue1.poll (); queue1.poll ());} lance une nouvelle exception ("pile est vide"); // je ne sais pas ce que le code signifie} public static void main (String [] args) lance l'exception {pile st ack = new Stack (); stack.push (1); )); Stack.push (4);Effet de course:
5. Concevez une pile avec la fonction minimale min (), et nécessite que la complexité temporelle de Min, Push, Pop et tous soient O (1). Le but de la méthode MIN est: il peut renvoyer la valeur minimale dans la pile. 【WeChat Interview Questions】
Idées ordinaires:
De manière générale, nous pouvons penser de cette façon: en utilisant la variable min, chaque fois que nous ajoutons un élément, il est comparé à l'élément min, afin qu'il puisse garantir que la valeur minimale stockée en min peut être garantie. Mais dans ce cas, il y aura un problème: si le plus petit élément est hors de la pile, comment pouvez-vous savoir lequel des éléments restants est le plus petit élément?
Idées d'amélioration:
Ici, vous devez ajouter une pile auxiliaire pour échanger un espace contre le temps. Dans la pile auxiliaire, le haut de la pile enregistre toujours la plus petite valeur dans la pile actuelle. Il est spécifique: chaque fois qu'un nouvel élément est ajouté dans la pile d'origine, il est comparé à l'élément supérieur de la pile auxiliaire. L'élément est grand, puis copiez l'élément supérieur de la pile auxiliaire en haut de la pile auxiliaire;
Implémentation complète du code:
Importer java.util.stack; / *** Créé par Smyhvae le 2015/9/9. * / classe publique Minstack {Private Stack <Integer> Stack = new Stack <Integer> (); Nouvelle pile <Integer> (); / Dans le Auxiliary if (minstack.size () == 0 || Data <Minstack.Peek ()) {minstack.push (data);} else {minstack.add (minstack.peek ()); Code] La méthode PEEK renvoie l'élément en haut de la pile}} public int pop () lève une exception {if (stack.size () == 0) {lancer une nouvelle exception ("vide dans la pile"); data = stack.pop (); Hollow ");} return minstack.Peek ();} public static void main (String [] args) lève une exception {minstack stack = new Minstack (); stack.push (4); stack.pus h (3); pile .push (5); System.out.println (stack.min ());Effet de course:
6. Déterminez si les séquences push et pop de la pile sont cohérentes:
Pour le dire simplement: il est connu qu'un ensemble de données 1, 2, 3, 4 et 5 est placé dans la pile en séquence, il existe donc de nombreuses façons de l'éteindre. ?
Par exemple:
données:
1, 2, 3, 4, 5
出栈1：
5, 4, 3, 2, 1 (correct)
Sortie 2:
4, 5, 3, 2, 1 (correct)
Sortie 3:
4, 3, 5, 1, 2 (erreur)
Code de version complète:
Importer java.util.stack; / *** créé par Smyhvae le 2015/9/9.
* /
classe publique StackTest {
// Méthode: l'ordre des tableaux de données1 indique l'ordre d'empilement. Maintenant, jugez si l'ordonnance d'empilement des données2 est correcte.
Séquence booléen statique publique (int [] data1, int [] data2) {
Stack <Integer> pile = new Stack <Integer> ();
pour (int i = 0, j = 0; i <data1.length; i ++) {
stack.push (data1 [i]);
while (stack.size ()> 0 && stack.Peek () == data2 [j]) {
stack.pop ();
j ++;
}
}
return stack.size () == 0;
}
public static void main (String [] args) {
Stack <Integer> stack = new Stack <Integer> ();
int[] data1 = {1, 2, 3, 4, 5};
int[] data2 = {4, 5, 3, 2, 1};
int[] data3 = {4, 5, 2, 3, 1};
System.out.println(sequenseIsPop(data1, data2));
System.out.println (Sequenseispop (data1, data3));
}
}
Le code est relativement concis, mais il est également difficile à comprendre, vous devez donc le comprendre attentivement.
Effet de course:
Ce qui précède sont des questions d'entrevue classiques sur Java Stack et les files d'attente.