Java: Knuth shuffle on a Stack?

Question

Hi,

For a programming class I am creating a blackjack program for the first homework assignment. The professor has given us a sample Card class, which includes the method to add them to a deck. For her deck, she uses an ArrayList, which you can easily Knuth Shuffle with the Collections.shuffle() method.

That method does not work for Stacks though (obviously), but I think a Stack structure would work best for this program because you may pop and push cards into and out of the deck.

Is there a way to apply the Knuth shuffle to a Stack data structure?

Answer 1

There is no reason why a stack structure should not be random access as well (java.util.Stack does, although that has problems of its own). Other than that, you can pop the elements of the stack into an ArrayList, shuffle and then push them back on to your stack.

Answer 2

I guess it's much easier to do stack operations on an ArrayList.

Answer 3

Both java.util.ArrayList<E> and java.util.stack<E> implement the java.util.List<E> interface, and Collections.shuffle() takes a java.util.List<?> as a parameter. You should be able to pass a Stack into Collections.shuffle(), unless you're using a different stack implementation that does not implement java.util.list<E>. If you are, I would advise you to switch to a different stack implementation.

Answer 4

No, Fisher-Yates shuffle relies on random access to the dataset. You need some Collection which allows get(int index). If you need a stack just use a list. push and pop just call get(0) and add(0). This is better than implementing some custom stack class. Use what you have, don't invent new classes.

Answer 5

A stack is a list, so you can call Collections.shuffle() on your stack.

That said, Stack is an old class, like Vector and kind of outmoded. Nowadays you would use a Dequeue (a double ended queue which works as either a queue or a stack) rather then a stack but, Dequeues are not lists, so they can't be shuffled.

Also, you can always put your cards in a List, shuffle them, and then add all of them to a Dequeue

Answer 6

Adam's answer is best for a stack. For card games, what I usually use is a simple arraylist and remove random elements. No shuffling required.

Answer 7

Just shuffle before/as you put the cards onto the stack. Since a properly implemented Knuth shuffle does not allow replacement of cards in the part of the deck already traversed you can simply place them onto the stack as you go along...

Since java will not let you treat a stack as a random access list just copy from the stack into an ArrayList to do the shuffling phase (an extra 52 element ArrayList knocking around is no big deal)

Answer 8

the Collections.shuffle() method does that for you you dont have to explicitly.

"If the specified list does not implement the RandomAccess interface and is large, this implementation of shuffle() dumps the specified list into an array before shuffling it, and dumps the shuffled array back into the list. This avoids the quadratic behavior that would result from shuffling a "sequential access" list in place."

this is what the java documentation says about Collections.shuffle() method implementation so passing a java.util.Stack (an implementation of java.util.List interface) should work...