Gardez 2 stacks, appelons-les inbox et inbox outbox .

Enqueue :

• Poussez le nouvel élément dans la inbox

Dequeue :

• Si la inbox outbox est vide, remplissez-la en extrayant chaque élément de la inbox de inbox et en le poussant sur la inbox outbox

• Pop et renvoyer l’élément supérieur de la outbox d’ outbox

En utilisant cette méthode, chaque élément sera dans chaque stack exactement une fois – ce qui signifie que chaque élément sera poussé deux fois et sauté deux fois, donnant des opérations à temps constant amorti.

Voici une implémentation en Java:

 public class Queue { private Stack inbox = new Stack(); private Stack outbox = new Stack(); public void queue(E item) { inbox.push(item); } public E dequeue() { if (outbox.isEmpty()) { while (!inbox.isEmpty()) { outbox.push(inbox.pop()); } } return outbox.pop(); } } 

A – Comment inverser une stack

Pour comprendre comment construire une queue à l’aide de deux stacks, vous devez comprendre comment inverser la transparence d’une stack. Rappelez-vous comment la stack fonctionne, elle est très similaire à la stack de vaisselle dans votre cuisine. Le dernier plat lavé sera sur le dessus de la stack propre, appelée en tant que première informatique (LIFO) en informatique.

Imaginons notre stack comme une bouteille comme ci-dessous;

Si nous poussons les entiers 1,2,3 respectivement, alors 3 seront sur le dessus de la stack. Comme 1 sera poussé en premier, alors 2 sera mis en haut de la liste. Enfin, 3 seront placés en haut de la stack et le dernier état de notre stack représenté comme une bouteille sera comme ci-dessous;

Maintenant, notre stack est représentée par une bouteille remplie de valeurs 3,2,1. Et nous voulons inverser la stack de sorte que l’élément supérieur de la stack soit 1 et que l’élément inférieur de la stack soit 3. Qu’est-ce que nous pouvons faire? On peut prendre la bouteille et la tenir à l’envers pour que toutes les valeurs s’inversent dans l’ordre?

Oui, nous pouvons le faire, mais c’est une bouteille. Pour faire le même processus, nous devons avoir une deuxième stack qui va stocker les premiers éléments de la stack dans l’ordre inverse. Mettons notre stack remplie à gauche et notre nouvelle stack vide à droite. Pour inverser l’ordre des éléments, nous allons extraire chaque élément de la stack de gauche et les pousser dans la stack de droite. Vous pouvez voir ce qui se passe comme nous le faisons sur l’image ci-dessous;

Nous soaps donc comment inverser une stack.

B – Utiliser deux stacks en queue

Dans la partie précédente, j’ai expliqué comment inverser l’ordre des éléments de la stack. C’était important, car si nous poussons et popons des éléments dans la stack, la sortie sera exactement dans l’ordre inverse d’une queue. En pensant à un exemple, passons le tableau d’entiers {1, 2, 3, 4, 5} à une stack. Si nous déplaçons les éléments et les imprimons jusqu’à ce que la stack soit vide, nous obtiendrons le tableau dans l’ordre inverse de l’ordre de poussée, qui sera {5, 4, 3, 2, 1} Déchargez la queue jusqu’à ce que la queue soit vide. La sortie sera {1, 2, 3, 4, 5} . Il est donc évident que pour un même ordre d’entrée d’éléments, la sortie de la file d’attente est exactement la même que celle d’une stack. Comme nous soaps inverser une stack en utilisant une stack supplémentaire, nous pouvons construire une queue à l’aide de deux stacks.

Notre modèle de queue sera composé de deux stacks. Une stack sera utilisée pour l’opération de mise en enqueue d’ enqueue (la stack n ° 1 à gauche sera appelée comme stack en entrée), une autre stack sera utilisée pour l’opération de dequeue (la stack n ° 2 à droite sera appelée stack de sortie). Regardez l’image ci-dessous;

Notre pseudo-code est comme ci-dessous;

Opération de mise en queue

 Push every input element to the Input Stack 

Opération Dequeue

 If ( Output Stack is Empty) pop every element in the Input Stack and push them to the Output Stack until Input Stack is Empty pop from Output Stack 

Lions les entiers {1, 2, 3} respectivement. Les entiers seront poussés sur la stack d’entrée ( stack n ° 1 ) située à gauche;

Alors, que se passera-t-il si nous exécutons une opération de retrait de la queue? Chaque fois qu’une opération de sortie de la queue est exécutée, la queue va vérifier si la stack de sortie est vide ou non (voir le pseudo-code ci-dessus). Si la stack de sortie est vide, la stack d’entrée sera extraite. de la stack d’entrée sera inversé. Avant de renvoyer une valeur, l’état de la queue sera le suivant;

Vérifiez l’ordre des éléments dans la stack de sortie (stack n ° 2). Il est évident que nous pouvons extraire les éléments de la stack de sortie pour que la sortie soit la même que si nous avions retiré une queue. Ainsi, si nous exécutons deux opérations de dequeue, nous obtiendrons d’abord {1, 2} respectivement. Ensuite, l’élément 3 sera le seul élément de la stack de sortie et la stack d’entrée sera vide. Si l’on met en queue les éléments 4 et 5, l’état de la queue sera le suivant;

Maintenant, la stack de sortie n’est pas vide, et si nous exécutons une opération de retrait de la queue, seules 3 seront extraites de la stack de sortie. Ensuite, l’état sera vu comme ci-dessous;

Encore une fois, si nous exécutons deux autres opérations de désenregistrement, lors de la première opération de désenregistrement, la queue vérifiera si la stack de sortie est vide, ce qui est vrai. Ensuite, sortez les éléments de la stack d’entrée et poussez-les dans la stack de sortie jusqu’à ce que la stack d’entrée soit vide, puis l’état de la queue sera le suivant;

Facile à voir, le résultat des deux opérations de dequeue sera {4, 5}

C – Implémentation d’une file construite avec deux stacks

Voici une implémentation en Java. Je ne vais pas utiliser l’implémentation existante de Stack, donc l’exemple ici va réinventer la roue;

C – 1) Classe MyStack: une implémentation simple de la stack

 public class MyStack { // inner generic Node class private class Node { T data; Node next; public Node(T data) { this.data = data; } } private Node head; private int size; public void push(T e) { Node newElem = new Node(e); if(head == null) { head = newElem; } else { newElem.next = head; head = newElem; // new elem on the top of the stack } size++; } public T pop() { if(head == null) return null; T elem = head.data; head = head.next; // top of the stack is head.next size--; return elem; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public void printStack() { System.out.print("Stack: "); if(size == 0) System.out.print("Empty !"); else for(Node temp = head; temp != null; temp = temp.next) System.out.printf("%s ", temp.data); System.out.printf("\n"); } } 

C – 2) Classe MyQueue: Implémentation de la queue à l’aide de deux stacks

 public class MyQueue { private MyStack inputStack; // for enqueue private MyStack outputStack; // for dequeue private int size; public MyQueue() { inputStack = new MyStack<>(); outputStack = new MyStack<>(); } public void enqueue(T e) { inputStack.push(e); size++; } public T dequeue() { // fill out all the Input if output stack is empty if(outputStack.isEmpty()) while(!inputStack.isEmpty()) outputStack.push(inputStack.pop()); T temp = null; if(!outputStack.isEmpty()) { temp = outputStack.pop(); size--; } return temp; } public int size() { return size; } public boolean isEmpty() { return size == 0; } } 

C – 3) Code de démonstration

 public class TestMyQueue { public static void main(Ssortingng[] args) { MyQueue queue = new MyQueue<>(); // enqueue integers 1..3 for(int i = 1; i <= 3; i++) queue.enqueue(i); // execute 2 dequeue operations for(int i = 0; i < 2; i++) System.out.println("Dequeued: " + queue.dequeue()); // enqueue integers 4..5 for(int i = 4; i <= 5; i++) queue.enqueue(i); // dequeue the rest while(!queue.isEmpty()) System.out.println("Dequeued: " + queue.dequeue()); } } 

C - 4) Sortie d'échantillon

 Dequeued: 1 Dequeued: 2 Dequeued: 3 Dequeued: 4 Dequeued: 5 

Vous pouvez même simuler une queue en utilisant une seule stack. La deuxième stack (temporaire) peut être simulée par la stack d’appels d’appels récursifs à la méthode d’insertion.

Le principe rest le même lors de l’insertion d’un nouvel élément dans la queue:

• Vous devez transférer des éléments d’une stack vers une autre stack temporaire pour inverser leur ordre.
• Poussez ensuite le nouvel élément à insérer sur la stack temporaire
• Transférez ensuite les éléments dans la stack d’origine
• Le nouvel élément sera en bas de la stack et l’élément le plus ancien en haut (le premier à apparaître)

Une classe de queue utilisant une seule stack est la suivante:

 public class SimulatedQueue { private java.util.Stack stack = new java.util.Stack(); public void insert(E elem) { if (!stack.empty()) { E topElem = stack.pop(); insert(elem); stack.push(topElem); } else stack.push(elem); } public E remove() { return stack.pop(); } } 

La complexité du temps serait pire, cependant. Une bonne implémentation de la queue fait tout en temps constant.

modifier

Je ne sais pas pourquoi ma réponse a été abaissée ici. Si nous programmons, nous nous soucions de la complexité du temps, et l’utilisation de deux stacks standard pour créer une queue est inefficace. C’est un point très valable et pertinent. Si quelqu’un d’autre ressent le besoin de céder plus, je serais intéressé de savoir pourquoi.

Un peu plus en détail : pourquoi l’utilisation de deux stacks est-elle pire qu’une simple queue: si vous utilisez deux stacks et que quelqu’un appelle dequeue alors que la boîte d’envoi est vide, vous avez besoin de temps linéaire pour dans le code de Dave).

Vous pouvez implémenter une queue en tant que liste à lien unique (chaque élément pointe vers l’élément inséré suivant), en conservant un pointeur supplémentaire sur l’élément inséré en dernier pour les pousser (ou en en faisant une liste cyclique). L’implémentation de la queue et du retrait de la queue sur cette structure de données est très facile à faire en temps constant. C’est le pire des cas, le temps constant, non amorti. Et, comme les commentaires semblent demander cette clarification, le temps constant le plus défavorable est ssortingctement meilleur que le temps constant amorti.

Soit la queue à implémenter soit q et les stacks utilisées pour implémenter q soit stack1 et stack2.

q peut être mis en œuvre de deux manières:

Méthode 1 (en rendant l’opération enQueue coûteuse)

Cette méthode garantit que l’élément nouvellement entré est toujours en haut de la stack 1, de sorte que l’opération deQueue ne s’affiche que dans la stack1. Pour mettre l’élément en haut de stack1, stack2 est utilisé.

 enQueue(q, x) 1) While stack1 is not empty, push everything from stack1 to stack2. 2) Push x to stack1 (assuming size of stacks is unlimited). 3) Push everything back to stack1. deQueue(q) 1) If stack1 is empty then error 2) Pop an item from stack1 and return it. 

Méthode 2 (en rendant l’opération deQueue coûteuse)

Dans cette méthode, lors d’une opération en queue, le nouvel élément est entré en haut de la stack1. Dans le cas d’une opération de mise en queue, si stack2 est vide, tous les éléments sont déplacés vers stack2 et finalement top of stack2 est renvoyé.

 enQueue(q, x) 1) Push x to stack1 (assuming size of stacks is unlimited). deQueue(q) 1) If both stacks are empty then error. 2) If stack2 is empty While stack1 is not empty, push everything from stack1 to stack2. 3) Pop the element from stack2 and return it. 

La méthode 2 est nettement meilleure que la méthode 1. La méthode 1 déplace tous les éléments deux fois dans l’opération enQueue, tandis que la méthode 2 (dans l’opération deQueue) déplace les éléments une fois et déplace les éléments uniquement si stack2 est vide.

Une solution dans c #

  public class Queue where T : class { private Stack input = new Stack(); private Stack output = new Stack(); public void Enqueue(T t) { input.Push(t); } public T Dequeue() { if (output.Count == 0) { while (input.Count != 0) { output.Push(input.Pop()); } } return output.Pop(); } } 

Deux stacks dans la queue sont définies comme stack1 et stack2 .

Enqueue: Les éléments euqueued sont toujours poussés dans la stack1

Dequeue: Le sumt de stack2 peut être extrait car il s’agit du premier élément inséré dans la queue lorsque stack2 n’est pas vide. Lorsque stack2 est vide, tous les éléments de stack1 sont déplacés et introduits dans la stack2 un par un. Le premier élément d’une queue est placé au bas de la stack1 . Il peut être sorti directement après avoir sauté et poussé des opérations puisqu’il se trouve en haut de la stack2 .

Voici le même exemple de code C ++:

 template  class CQueue { public: CQueue(void); ~CQueue(void); void appendTail(const T& node); T deleteHead(); private: stack stack1; stack stack2; }; template void CQueue::appendTail(const T& element) { stack1.push(element); } template T CQueue::deleteHead() { if(stack2.size()<= 0) { while(stack1.size()>0) { T& data = stack1.top(); stack1.pop(); stack2.push(data); } } if(stack2.size() == 0) throw new exception("queue is empty"); T head = stack2.top(); stack2.pop(); return head; } 

Cette solution est empruntée à mon blog . Une parsing plus détaillée avec des simulations d’opérations détaillées est disponible sur ma page Web de blog.

Vous devrez tout enlever de la première stack pour obtenir l’élément inférieur. Ensuite, remettez-les tous sur la deuxième stack pour chaque opération “dequeue”.

pour le développeur c # voici le programme complet:

 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace QueueImplimentationUsingStack { class Program { public class Stack { public int size; public Node head; public void Push(T data) { Node node = new Node(); node.data = data; if (head == null) head = node; else { node.link = head; head = node; } size++; Display(); } public Node Pop() { if (head == null) return null; else { Node temp = head; //temp.link = null; head = head.link; size--; Display(); return temp; } } public void Display() { if (size == 0) Console.WriteLine("Empty"); else { Console.Clear(); Node temp = head; while (temp!= null) { Console.WriteLine(temp.data); temp = temp.link; } } } } public class Queue { public int size; public Stack inbox; public Stack outbox; public Queue() { inbox = new Stack(); outbox = new Stack(); } public void EnQueue(T data) { inbox.Push(data); size++; } public Node DeQueue() { if (outbox.size == 0) { while (inbox.size != 0) { outbox.Push(inbox.Pop().data); } } Node temp = new Node(); if (outbox.size != 0) { temp = outbox.Pop(); size--; } return temp; } } public class Node { public T data; public Node link; } static void Main(ssortingng[] args) { Queue q = new Queue(); for (int i = 1; i <= 3; i++) q.EnQueue(i); // q.Display(); for (int i = 1; i < 3; i++) q.DeQueue(); //q.Display(); Console.ReadKey(); } } } 

 // Two stacks s1 Original and s2 as Temp one private Stack s1 = new Stack(); private Stack s2 = new Stack(); /* * Here we insert the data into the stack and if data all ready exist on * stack than we copy the entire stack s1 to s2 recursively and push the new * element data onto s1 and than again recursively call the s2 to pop on s1. * * Note here we can use either way ie We can keep pushing on s1 and than * while popping we can remove the first element from s2 by copying * recursively the data and removing the first index element. */ public void insert( int data ) { if( s1.size() == 0 ) { s1.push( data ); } else { while( !s1.isEmpty() ) { s2.push( s1.pop() ); } s1.push( data ); while( !s2.isEmpty() ) { s1.push( s2.pop() ); } } } public void remove() { if( s1.isEmpty() ) { System.out.println( "Empty" ); } else { s1.pop(); } } 

Une implémentation d’une queue utilisant deux stacks dans Swift:

 struct Stack { var items = [Element]() var count : Int { return items.count } mutating func push(_ item: Element) { items.append(item) } mutating func pop() -> Element? { return items.removeLast() } func peek() -> Element? { return items.last } } struct Queue { var inStack = Stack() var outStack = Stack() mutating func enqueue(_ item: Element) { inStack.push(item) } mutating func dequeue() -> Element? { fillOutStack() return outStack.pop() } mutating func peek() -> Element? { fillOutStack() return outStack.peek() } private mutating func fillOutStack() { if outStack.count == 0 { while inStack.count != 0 { outStack.push(inStack.pop()!) } } } } 

Bien que vous ayez beaucoup de messages liés à l’implémentation d’une queue avec deux stacks: 1. soit en rendant le processus enQueue beaucoup plus coûteux; 2. soit en rendant le processus deQueue beaucoup plus coûteux;

https://www.geeksforgeeks.org/queue-using-stacks/

Une des manières importantes que j’ai trouvé dans le post ci-dessus était la construction de la queue avec seulement la structure de données de la stack et la stack des appels de récursivité.

Bien que l’on puisse affirmer que littéralement, on utilise toujours deux stacks, mais idéalement, cela n’utilise qu’une seule structure de données de stack.

Voici l’explication du problème:

1. Déclarez une stack unique pour enQueuing et déQueing les données et poussez les données dans la stack.

2. tandis que deQueueing a une condition de base où l’élément de la stack est affiché lorsque la taille de la stack est 1. Cela garantira qu’il n’y aura pas de dépassement de stack pendant la récursivité deQueue.

3. Lors du deQueueing, commencez par afficher les données en haut de la stack. Idéalement, cet élément sera l’élément présent au sumt de la stack. Maintenant, une fois cela fait, appelez récursivement la fonction deQueue, puis repoussez l’élément sauté dans la stack.

Le code ressemblera à celui ci-dessous:

 if (s1.isEmpty()) System.out.println("The Queue is empty"); else if (s1.size() == 1) return s1.pop(); else { int x = s1.pop(); int result = deQueue(); s1.push(x); return result; 

De cette façon, vous pouvez créer une queue en utilisant une structure de données de stack unique et la stack d’appels de récursivité.

 public class QueueUsingStacks { private LinkedListStack stack1; private LinkedListStack stack2; public QueueUsingStacks() { stack1=new LinkedListStack(); stack2 = new LinkedListStack(); } public void Copy(LinkedListStack source,LinkedListStack dest ) { while(source.Head!=null) { dest.Push(source.Head.Data); source.Head = source.Head.Next; } } public void Enqueue(T entry) { stack1.Push(entry); } public T Dequeue() { T obj; if (stack2 != null) { Copy(stack1, stack2); obj = stack2.Pop(); Copy(stack2, stack1); } else { throw new Exception("Stack is empty"); } return obj; } public void Display() { stack1.Display(); } } 

Pour chaque opération de mise en queue, nous ajoutons en haut de la stack1. Pour chaque dequeue, nous vidons le contenu de stack1 dans stack2 et supprimons l’élément en haut de la stack. La complexité temporelle est O (n) pour dequeue, car nous devons copier la stack1 à stack2. la complexité temporelle de la mise en queue est identique à celle d’une stack régulière

Je vais répondre à cette question dans Go car Go n’a pas beaucoup de collections dans sa bibliothèque standard.

Puisqu’une stack est vraiment facile à mettre en œuvre, j’ai pensé que j’utiliserais deux stacks pour accomplir une queue double. Pour mieux comprendre comment je suis arrivé à ma réponse, j’ai divisé la mise en œuvre en deux parties, la première partie est plus facile à comprendre, mais elle est incomplète.

 type IntQueue struct { front []int back []int } func (q *IntQueue) PushFront(v int) { q.front = append(q.front, v) } func (q *IntQueue) Front() int { if len(q.front) > 0 { return q.front[len(q.front)-1] } else { return q.back[0] } } func (q *IntQueue) PopFront() { if len(q.front) > 0 { q.front = q.front[:len(q.front)-1] } else { q.back = q.back[1:] } } func (q *IntQueue) PushBack(v int) { q.back = append(q.back, v) } func (q *IntQueue) Back() int { if len(q.back) > 0 { return q.back[len(q.back)-1] } else { return q.front[0] } } func (q *IntQueue) PopBack() { if len(q.back) > 0 { q.back = q.back[:len(q.back)-1] } else { q.front = q.front[1:] } } 

Il s’agit essentiellement de deux stacks où nous permettons à la partie inférieure des stacks d’être manipulées l’une par l’autre. J’ai également utilisé les conventions de dénomination STL, où les opérations traditionnelles de type push, pop et peek d’une stack ont un préfixe recto / verso, qu’elles se rapportent au recto ou au verso de la queue.

Le problème avec le code ci-dessus est qu’il n’utilise pas très efficacement la mémoire. En fait, il pousse à l’infini jusqu’à ce que vous manquiez d’espace. C’est vraiment mauvais La solution consiste à réutiliser le bas de la stack autant que possible. Nous devons introduire un décalage pour suivre cela car une tranche dans Go ne peut pas croître à l’avant une fois rétrécie.

 type IntQueue struct { front []int frontOffset int back []int backOffset int } func (q *IntQueue) PushFront(v int) { if q.backOffset > 0 { i := q.backOffset - 1 q.back[i] = v q.backOffset = i } else { q.front = append(q.front, v) } } func (q *IntQueue) Front() int { if len(q.front) > 0 { return q.front[len(q.front)-1] } else { return q.back[q.backOffset] } } func (q *IntQueue) PopFront() { if len(q.front) > 0 { q.front = q.front[:len(q.front)-1] } else { if len(q.back) > 0 { q.backOffset++ } else { panic("Cannot pop front of empty queue.") } } } func (q *IntQueue) PushBack(v int) { if q.frontOffset > 0 { i := q.frontOffset - 1 q.front[i] = v q.frontOffset = i } else { q.back = append(q.back, v) } } func (q *IntQueue) Back() int { if len(q.back) > 0 { return q.back[len(q.back)-1] } else { return q.front[q.frontOffset] } } func (q *IntQueue) PopBack() { if len(q.back) > 0 { q.back = q.back[:len(q.back)-1] } else { if len(q.front) > 0 { q.frontOffset++ } else { panic("Cannot pop back of empty queue.") } } } 

Il y a beaucoup de petites fonctions, mais parmi les 6 fonctions, 3 ne sont que des miroirs de l’autre.

voici ma solution en Java en utilisant liste de liens.

 class queue{ static class Node{ private T data; private Node next; Node(T data){ this.data = data; next = null; } } Node firstTop; Node secondTop; void push(T data){ Node temp = new Node(data); temp.next = firstTop; firstTop = temp; } void pop(){ if(firstTop == null){ return; } Node temp = firstTop; while(temp != null){ Node temp1 = new Node(temp.data); temp1.next = secondTop; secondTop = temp1; temp = temp.next; } secondTop = secondTop.next; firstTop = null; while(secondTop != null){ Node temp3 = new Node(secondTop.data); temp3.next = firstTop; firstTop = temp3; secondTop = secondTop.next; } } 

}

Remarque: dans ce cas, l’opération pop prend beaucoup de temps. Je ne suggère donc pas de créer une queue en utilisant deux stacks.

Avec O(1) dequeue() , qui est identique à la réponse de pythonquick:

 // time: O(n), space: O(n) enqueue(x): if stack.isEmpty(): stack.push(x) return temp = stack.pop() enqueue(x) stack.push(temp) // time: O(1) x dequeue(): return stack.pop() 

Avec O(1) enqueue() (ce n’est pas mentionné dans cet article, alors cette réponse), qui utilise également le backtracking pour faire apparaître et retourner le dernier article.

 // O(1) enqueue(x): stack.push(x) // time: O(n), space: O(n) x dequeue(): temp = stack.pop() if stack.isEmpty(): x = temp else: x = dequeue() stack.push(temp) return x 

Évidemment, c’est un bon exercice de codage car il est inefficace mais élégant.

Implémentation de la queue à l’aide de deux objects java.util.Stack:

 public final class QueueUsingStacks { private final Stack iStack = new Stack<>(); private final Stack oStack = new Stack<>(); public void enqueue(E e) { iStack.push(e); } public E dequeue() { if (oStack.isEmpty()) { if (iStack.isEmpty()) { throw new NoSuchElementException("No elements present in Queue"); } while (!iStack.isEmpty()) { oStack.push(iStack.pop()); } } return oStack.pop(); } public boolean isEmpty() { if (oStack.isEmpty() && iStack.isEmpty()) { return true; } return false; } public int size() { return iStack.size() + oStack.size(); } }