Inverser une liste à l'aide de deux files d'attente

Cette question est inspirée d'une question existante sur la possibilité de simuler une pile à l'aide de deux files d'attente en temps amorti par opération de pile. La réponse semble inconnue. Voici une question plus spécifique, correspondant au cas particulier dans lequel toutes les opérations PUSH sont effectuées en premier, suivies de toutes les opérations POP. Avec quelle efficacité une liste de N éléments peut-elle être inversée à l'aide de deux files d'attente initialement vides? Les opérations légales sont:$O(1)$$N$

1. Mettez en file d'attente l'élément suivant de la liste d'entrée (à la fin de l'une ou l'autre file d'attente).
2. Supprimez l'élément en tête de chaque file d'attente et remettez-le en file d'attente (à la fin de l'une ou l'autre file d'attente).
3. Retirez l'élément en tête de chaque file d'attente et ajoutez-le à la liste de sortie.

Si la liste d'entrée se compose d'éléments , comment le nombre minimum d'opérations nécessaires pour générer la liste de sortie inversée [ N , N - 1 , . . . , 2 , 1 ] se comportent-ils? Une preuve qu'il croît plus vite que O ( N ) serait particulièrement intéressante, car il résoudrait la question initiale par la négative.$[1,2,...,N-1,N]$$[N,N-1,...,2,1]$$O(N)$

Mise à jour (15 janvier 2011): Le problème peut être résolu dans , comme indiqué dans les réponses soumises et leurs commentaires; et une borne inférieure de Ω ( N ) est triviale. L'une ou l'autre de ces limites peut-elle être améliorée?$O(N \log N)$$\Omega(N)$

Si N est une puissance de deux, je pense que les opérations O (N log N) suffisent, même pour un problème un peu plus restreint dans lequel tous les éléments démarrent sur l'une des files d'attente et doivent finir dans l'ordre inverse sur l'une des files d'attente (sans les listes d'entrée et de sortie).

Dans les étapes O (N), il est possible de commencer avec tous les éléments d'une file d'attente, de jouer "un pour vous, un pour moi" pour les diviser en sous-ensembles alternés sur l'autre file d'attente, puis de les concaténer à nouveau dans une file d'attente. En termes de représentations binaires des positions des éléments, cela implémente une opération de rotation.

Dans les étapes O (N), il est également possible d'extraire des paires d'éléments d'une file d'attente, de les échanger, puis de les remettre, en inversant toutes les paires. En termes de représentations binaires des positions des éléments, cela complète le bit de poids faible de la position.

En répétant O (log N) fois un démêlage et un échange par paire, nous pouvons compléter tous les bits des représentations binaires des positions - ce qui revient à inverser la liste.

$\sum_{i=0}^{N/2-1}(N-2i-2)$

Permet de nommer deux files d'attente disponibles comme gauche et droite. Voici l'idée de base de cet algorithme avec l'hypothèse que N est pair:

1. Lire les valeurs de la liste initiale des éléments et pousser tous les nombres impairs dans la file d'attente gauche et les nombres pairs dans la file d'attente droite
2. L'une des premières étapes pour générer la valeur maximale est de transférer les éléments N / 2-1 de la file d'attente droite dans la file de gauche et de faire apparaître la valeur supérieure de la file d'attente droite dans la liste de sortie.
3. Maintenant, nous devons faire la même chose pour une autre file d'attente - transférer les éléments N / 2-1 de la file d'attente gauche vers la droite et insérer l'élément supérieur de la file d'attente gauche dans la liste de sortie
4. Échangez les files d'attente et répétez les étapes 2 et 3 pour N = N-2

Il est facile de voir comment l'algorithme devrait fonctionner pour un N impair.