Mettre en place de la pile à l’aide de deux files d’attente

Question

Une question similaire a été posée tout à l'heure là, mais la question ici est l'inverse de cela, à l'aide de deux files d'attente comme une pile. La question...

Compte tenu de deux files d'attente avec leurs opérations standard (à la file, file d'attente, isempty, taille), de mettre en œuvre une pile avec ses opérations standard (pop, push, isempty, taille).

Il devrait y avoir DEUX versions de la solution.

• Version A: La pile doit être efficace lorsque l'on pousse un élément.
• Version B: La pile doit être efficace quand popping un élément.

Je suis intéressé par l'algorithme plus que n'importe quelle langue spécifique implémentations. Toutefois, je vous souhaite la bienvenue solutions exprimées dans des langues que je connais bien (Java, C#, Python, VB, Javascript, Php). Merci à l'avance.

Answer 1

Version A:

• push:
  • mettre en file d'attente dans queue1
• pop:
  • bien que la taille de queue1 est plus grand que 1, tuyau retiré des éléments de queue1 en queue2
  • retirer et à retourner le dernier élément de queue1, puis passer les noms de queue1 et queue2

Version B:

• push:
  • mettre en file d'attente dans queue2
  • mettre en file d'attente tous les éléments de queue1 dans queue2, puis passer les noms de queue1 et queue2
• pop:
  • deqeue de queue1

Answer 2

La méthode la plus simple (et peut-être la seule) façon de le faire est de pousser de nouveaux éléments dans le vide la file d'attente, puis la file d'attente de l'autre et enqeuing dans le vide la file d'attente. Avec cette façon, la dernière est toujours à l'avant de la file d'attente. Ce serait la version B, pour la version Un vous juste inverser le processus en file d'attente les éléments de la deuxième file d'attente, sauf pour le dernier.

Étape 0:

"Stack"
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
|   |   |   |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Étape 1:

"Stack"
+---+---+---+---+---+
| 1 |   |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 1 |   |   |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Étape 2:

"Stack"
+---+---+---+---+---+
| 2 | 1 |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
|   |   |   |   |   |  | 2 | 1 |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Étape 3:

"Stack"
+---+---+---+---+---+
| 3 | 2 | 1 |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 3 | 2 | 1 |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Answer 3

Nous pouvons faire cela avec une file d’attente :

Push :

1. nouvel élément de file d’attente.
2. Si est le nombre d’éléments dans la file d’attente, puis retirer et insérer l’élément fois.

Pop :

1. Dequeue

.

Exemple d’implémentation :

Answer 4

import java.util.*;

/**
 *
 * @author Mahmood
 */
public class StackImplUsingQueues {

    Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();

    public int pop() {
        if (q1.peek() == null) {
            System.out.println("The stack is empty, nothing to return");
            int i = 0;
            return i;
        } else {
            int pop = q1.remove();
            return pop;
        }
    }

    public void push(int data) {

        if (q1.peek() == null) {
            q1.add(data);
        } else {
            for (int i = q1.size(); i > 0; i--) {
                q2.add(q1.remove());
            }
            q1.add(data);
            for (int j = q2.size(); j > 0; j--) {
                q1.add(q2.remove());
            }

        }
    }

    public static void main(String[] args) {
        StackImplUsingQueues s1 = new StackImplUsingQueues();
        //       Stack s1 = new Stack();
        s1.push(1);
        s1.push(2);
        s1.push(3);
        s1.push(4);
        s1.push(5);
        s1.push(6);
        s1.push(7);
        s1.push(8);
        s1.push(9);
        s1.push(10);
        // s1.push(6);
        System.out.println("1st = " + s1.pop());
        System.out.println("2nd = " + s1.pop());
        System.out.println("3rd = " + s1.pop());
        System.out.println("4th = " + s1.pop());
        System.out.println("5th = " + s1.pop());
        System.out.println("6th = " + s1.pop());
        System.out.println("7th = " + s1.pop());
        System.out.println("8th = " + s1.pop());
        System.out.println("9th = " + s1.pop());
        System.out.println("10th= " + s1.pop());
    }
}

Answer 5

queue<int> q1, q2;
int i = 0;

void push(int v) {
  if( q1.empty() && q2.empty() ) {
     q1.push(v);
     i = 0;
  }
  else {
     if( i == 0 ) {
        while( !q1.empty() ) q2.push(q1.pop());
        q1.push(v);
        i = 1-i;
     }
     else {
        while( !q2.empty() ) q1.push(q2.pop());
        q2.push(v);
        i = 1-i;
     }
  }
}

int pop() {
   if( q1.empty() && q2.empty() ) return -1;
   if( i == 1 ) {
      if( !q1.empty() )
           return q1.pop();
      else if( !q2.empty() )
           return q2.pop();
   }
   else {
      if( !q2.empty() )
           return q2.pop();
      else if( !q1.empty() )
           return q1.pop();
   }
}