CODEWITHSUNDEEP
javadata-structuresstackshuffle
Logan Serman
Logan Serman

Reputation: 29880

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

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.

Upvotes: 4

Views: 8621

Answers (8)

Thiyagarajan
Thiyagarajan

Reputation:

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...

Upvotes: 0

ShuggyCoUk
ShuggyCoUk

Reputation: 36476

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)

Upvotes: 0

EBGreen
EBGreen

Reputation: 37800

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.

Upvotes: 0

Chad Okere
Chad Okere

Reputation: 4578

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

Upvotes: 2

raupach
raupach

Reputation: 3102

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.

Upvotes: 0

Adam Rosenfield
Adam Rosenfield

Reputation: 400572

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.

Upvotes: 20

Joao da Silva
Joao da Silva

Reputation: 7639

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

Upvotes: 2

Tom Hawtin - tackline
Tom Hawtin - tackline

Reputation: 147154

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.

Upvotes: 0

Related Questions