I can't seem to figure how to pop an item of a stack using the elemental feature. Can someone please tell me how to do so?
Relevant code:
Stack<Cards> stackOfCards = new Stack<Cards>();
I have previously put items into this stack.
Random random = new Random();
int randomNumber = random.Next(0, 52);
for (int i = 0; i < 200; i++)
{
stackOfCards.ElementAt(randomNumber);//how do i pop this?
}
P.S. Do stacks start at 0 or 1? So for a deck of cards would it be 0-51 or 1-52?
The whole point of a stack is to not pop random elements. If you need to remove random items from a collection, use a collection that supports that such as List<T>
.
Stack is a last-in, first-out (LIFO) collection, not a random access collection.
I'd suggest reading: http://en.wikipedia.org/wiki/Stack_(abstract_data_type)
If you need to put something on the stack in random order, I'd suggest something like this:
List<Cards> wholeDeck = new List<Cards> { // initialize with a complete deck }
Random r = new Random();
Stack<Cards> stackOfCards = new Stack<Cards>();
while (wholeDeck.Count > 0) {
var aCard = wholeDeck[r.Next(0,wholeDeck.Count)]; // grab a random card
stackOfCards.Push(aCard); // push it on the stack
wholeDeck.Remove(aCard); // remove it from the original list
}
A note on efficiency (since Servy bought it up): Servy is absolutely correct that this is not the most efficient way to shuffle. Why? Well because removal of an item from a list is O(n) and you'd have to do it n times so overall it's O(n2). while swapping items in a list (as in the Fisher-Yates algorithm) is O(1) which you'd do n times, so overall it's O(n). Of course, you'd still need to add the items from your shuffled list to the stack which is going to be O(n), so O(2n). With 52 items this probably makes very little difference (which is why I chose not to worry about it), but if you have a millions items, or you are shuffling a million decks of cards, then this might be something to worry about.
Now I assume that the OP's original question is for some kind of class and the objective is to learn something about collections, how they work and what they are good for and I think this does actually bring up an important comparison. Different collection types are good for different things. List
gives you very fast, O(1) random access to any item in the list which makes it a great general purpose collection type. But this comes at a cost. The cost is that removal (and insertions, and sometimes additions) to the list are much slower. When you remove an item from a list the list has to be reorganized to move every item after the one you removed down one position so you can still index it quickly. When you insert (at some arbitary index) you have to move items up the list to make room. When you add to the end of the list, you might need to resize the backing store (in .NET it's an array) to make room (actually the same might be true of insertion) which requires copying the entire collection (the .NET list class gets around this by setting an initial capacity and when you hit that capacity it doubles the capacity rather than just adding one more element). So if you have a need for a collection where you are going to be inserting and removing items a lot, then List might not be the best choice.
So what about Stack? Stack gets around the insertion and removal problem by only letting you add (push) and remove (pop) from one spot in the collection. That way addition and removal is O(1) (for a fixed size stack at least). Which is great. But the cost is that you now lose the ability to access items in your collection in random order. Hence why the OP had difficulty figuring out how to shuffle on the stack. If you need the nth item on a stack you have to pop every item above it into a temporary stack, then look at the item you want, and then push all the items you remove back on.
Another collection type is the linked list. This collection has very fast removal (if you have a reference to the node) and insertion, and you can quickly find the next (and last in the case of a doubly linked list) node. But finding the nth node is O(n) because you have to walk the collection, counting nodes to find it.
Other collections have other properties and it's important to understand what you need from a collection before choosing the right one.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments