Stacking the Deck: An Introduction to Data Structures

After CS1 you will take a course on Data Structures (CS2027C). A course that involves constructing efficient ADTs and classes and popular, important patterns of storing data in a structured way.

The Stack ADT
A stack or LIFO (last in, first out) is an abstract data type that serves as a collection of elements, with three principal operations:

1. push adds an element to the collection;
2. pop removes the last element that was added.
3. is_empty returns a boolean value for testing if any elements in collection

class Stack:
   def __init__(self,maxsize):
       self.data = [None]*maxsize
       self.size = 0

   def push(self,item):
      self.data[self.size] = item
      self.size = self.size + 1    

   def pop(self):
      self.size = self.size - 1
      return self.data[self.size]    

   def is_empty(self):
      return self.size == 0

   def is_full(self):
      return self.size == len(self.data)

Stacks can be useful for many applications. Let’s build a deck of cards based on the stack abstraction. Not only will we store all the cards in a stack, but we will shuffle a deck by breaking up the cards into two stacks, and then rebuild the deck stack by selecting cards at random off the tops of the two stacks – thus simulating a hand rifle shuffle.

Data Analysis-Card Patterns:
There is a lazy dealer at the casino who only rifle shuffles a couple of times before dealing cards in blackjack. We would like to see if there are any patterns to exploit given that we know the original ordering. In other words, how many rifle shuffles do you need to remove any patterns in the original ordering?

import random
class DeckofCards():
    def __init__(self):
        self.cards = Stack(52)
        for i in xrange(52):
            self.cards.push(i)

    def __str__(self):
        s = ""
        for i in xrange(52):
           s += str(self.cards.data[i])  + " "
        return s
      

    def rifleShuffle(self):
        first=Stack(26)
        second=Stack(26)
        for i in range(26):
            first.push(self.cards.pop())
        for i in range(26):
            second.push(self.cards.pop())
        assert self.cards.is_empty()
        while (not (first.is_empty() or second.is_empty())):
            if (random.randint(1,2) == 1):
                self.cards.push(first.pop())
            else:
                self.cards.push(second.pop())
        while (not (first.is_empty())):
            self.cards.push(first.pop())
        while (not (second.is_empty())):
            self.cards.push(second.pop())

#Client Code to look for patterns in shuffled deck of cards
d = DeckofCards();
print d
for i in range(7):
    d.rifleShuffle()
    print "Shuffle", i
    print d

Lab Exercises (Due Friday April 10):

Task 0.
In this initial part you will download and execute the code for the Card Dealing Simulation and the DeckOfCards. A copy of this code is found above.

Task1.
Create a class called Card that will store using two instance variables (suit and facevalue). Write a constructor that converts an numeric value argument to appropriate suit and facevalue. Test your Card class by running the following loop:

for i in range(52):
    print Card(i),

#=> Output
Ace of Clubs
Ace of Diamonds
Ace of Hearts
Ace of Spades
2 of Clubs
2 of Diamonds
2 of Hearts
2 of Spades
3 of Clubs......etc.....

Task 2:
In this part you will modify and add a member function to the DeckOfCards class. Modify the DeckOfCards class so that an instance object stores a collection of Card objects instead of integers. Add a member function called dealNextCard(), which returns the next card on top of the deck. You will also need to keep track of the top of the deck. The member function dealNextCard() should return a Card object.

Test your code by creating an application that shuffles the deck several times and deals and prints the top 5 cards.

Task 3.
In this part you will create a new class called Hand that is used for objects that model a 5-card poker hand. Thus, a Hand object should store 5 arbitrary card objects. Modify your test application so that it shuffles and deals two 5-card hands, alternating cards between hands as the cards are dealt.

Task 4.
Write a member function called evaluate() for the Hand class. This function should return a boolean value and determine whether or not a hand object contains a pair of cards with the same face value. Test this code by evaluating each of the hands that are dealt.

Task 5. (Homework extra credit)
Write an auxiliary function that takes two hand objects as parameters and returns the better of the two hands using standard rules of poker (i.e., pair beats no pair, three-of-kind beats two pairs, etc.) A full version of this function is quite challenging. See how accurate you can make it in the time permitted.

Inheritence

Inheritence like Class Composition is another technique for sharing code. Inheritence is more complex but gives flexibility by allowing the override of functions in child classes. This gives the methods of the child class priority, and is an important part of well-designed polymorphism.

Here is a short example. Notice that the Child class is using the same constructor function, but it’s override function has priority.

class Parent(object):
    def __init__(self,pname):
        self.name = pname
    def override(self):
        print "PARENT override()", self.name

class Child(Parent):
    def override(self):
        print "CHILD override()", self.name

dad = Parent("Oscar")
son = Child("Ernie")

dad.override()
son.override()

Here is an image of a UML diagram that shows how inheritance may be used in an automobile application.

Here is a UML diagram using Class Composition for a Card Dealing Program:

Here is a key to UML diagram symbols: