Existe-t-il un moyen d’appliquer le mélange aléatoire de Knuth à une structure de données Stack?

Question

Pour un cours de programmation, je crée un programme de blackjack pour le premier devoir. Le professeur nous a donné un exemple de classe de cartes, qui inclut la méthode pour les ajouter à un jeu de cartes. Pour son deck, elle utilise une ArrayList, que vous pouvez facilement Knuth Shuffle avec la méthode Collections.shuffle ().

Bien que cette méthode ne fonctionne pas pour Stacks (évidemment), mais je pense qu’une structure Stack fonctionnerait mieux pour ce programme car vous pouvez insérer et sortir des cartes dans le paquet.

Answer 1

Les deux java.util.ArrayList<E> et < a href = "http://java.sun.com/javase/6/docs/api/java/util/Stack.html" rel = "noreferrer"> java.util.stack<E> implémente le java.util.List<E> , et Collections.shuffle() prend une java.util.List<?> en paramètre. Vous devriez pouvoir passer un Stack dans java.util.list<E>, à moins que vous n'utilisiez une implémentation de pile différente qui n'implémente pas <=>. Si tel est le cas, je vous conseillerais de passer à une implémentation de pile différente.

Answer 2

Je suppose qu'il est beaucoup plus facile de faire des opérations d'empilement sur un ArrayList.

Answer 3

Une pile est une liste, vous pouvez donc appeler Collections.shuffle () sur votre pile.

Cela dit, Stack est une classe ancienne, comme Vector et un peu démodée. De nos jours, vous utiliseriez un Attente . file d'attente double qui fonctionne soit comme une file d'attente, soit comme une pile) plutôt que comme une pile mais , les files d'attente ne sont pas des listes, elles ne peuvent donc pas être mélangées.

En outre, vous pouvez toujours mettre vos cartes dans une liste, les mélanger et les ajouter ensuite à une file d'attente

.

Answer 4

Il n’ya aucune raison pour qu’une structure de pile ne soit pas également un accès aléatoire (java.util.Stack le fait, bien que cela pose des problèmes en soi). En dehors de cela, vous pouvez insérer les éléments de la pile dans une liste de tableaux, les mélanger, puis les replacer dans votre pile.

Answer 5

Non, le shuffle de Fisher-Yates repose sur un accès aléatoire à l'ensemble de données. Vous avez besoin d'une collection qui permet d'obtenir (int index). Si vous avez besoin d'une pile, utilisez simplement une liste. push and pop suffit d'appeler get (0) et d'ajouter (0). C'est mieux que d'implémenter une classe de pile personnalisée. Utilisez ce que vous avez, n'inventez pas de nouvelles classes.

Answer 6

La réponse d'Adam est la meilleure pour une pile. Pour les jeux de cartes, j’utilise habituellement un simple arraylist et supprime des éléments aléatoires. Aucun brassage requis.

Answer 7

Mélangez juste avant / pendant que vous mettez les cartes sur la pile. Dans la mesure où un mélange de Knuth correctement mis en œuvre ne permet pas le remplacement de cartes dans la partie du jeu déjà traversée, vous pouvez simplement les placer sur la pile au fur et à mesure de votre progression ...

Etant donné que Java ne vous laissera pas traiter une pile comme une liste à accès aléatoire, copiez-la simplement dans une ArrayList pour effectuer la phase de mélange (une liste ArrayList supplémentaire de 52 éléments n’est pas un problème)

Answer 8

la méthode Collections.shuffle () fait cela pour vous, vous n'avez pas à le faire explicitement.

& ";" Si la liste spécifiée n'implémente pas l'interface RandomAccess et qu'elle est volumineuse, cette implémentation de shuffle () vide la liste spécifiée dans un tableau avant de le mélanger, puis réachemine le tableau mélangé dans la liste. Cela évite le comportement quadratique résultant du brassage d'un & "Accès séquentiel &"; liste en place. "

voici ce que dit la documentation Java sur l'implémentation de la méthode Collections.shuffle () donc passer un java.util.Stack (une implémentation de l'interface java.util.List) devrait marcher ...