06 - Stacks

Note: The following presentation is available on www.teachingcomputing.com

1. A CALL is made for a particular function or subroutine
2. The address of the line that made the call is stored in a stack (using a PUSH command)
3. The CPU executes the subroutine or function. 
4. Once the subroutine or function has been executed, the question is - "What do I do next?"
5. The original address is retreived from the stack with a ________________and the program
can then continue from wherever it had left off.

________________ is a general algorithm for finding all
(or some) solutions to some computational problems, 
notably constraint satisfaction problems, that incrementally 
builds candidates to the solutions, and abandons a 
candidate ("backtracks") as soon as it determines 
that the candidate cannot possibly be completed to a 
valid solution.

The classic textbook example of the use of ______________ is
the eight queens puzzle, that asks for all arrangements of
eight chess queens on a standard chessboard so that no queen
attacks any other. In the common _________________ approach, 
the partial candidates are arrangements of k queens in the
first k rows of the board, all in different rows and columns.
Any partial solution that contains two mutually attacking 
queens can be abandoned

mystack=[1,2,5]
mystack.pop()
mystack.append(7)
mystack.pop()
mystack.append(8)
mystack.append(9)
print(mystack)
#Note: The 'append' command is pushing an item on to the stack

#A stack lends itself to the creation of a new class
#Here we create a stack class, where stack operations are methods
class Stack:
     def __init__(self):
         self.items = []

     def isEmpty(self): #if the stack is empty then return True
         return self.items == []

     def push(self, item):
         self.items.append(item) #appending items

     def pop(self):
         return self.items.pop() #popping an item off the stack 

     def peek(self):
         return self.items[len(self.items)-1] #peek at the top most item (it remains in the stack)

     def size(self): #returns the size of the stack
         return len(self.items)

     def getStackItems(self):
          return self.items

s=Stack()
s.push("x")
print(s.isEmpty())
s.pop()
print(s.isEmpty())
s.push(1)
s.push(2)
s.push(3)
print(s.peek())

class Stack:
     def __init__(self):
         self.items = []

     def isEmpty(self): #if the stack is empty then return True
         return self.items == []

     def push(self, item):
         self.items.append(item) #appending items

     def pop(self):
         return self.items.pop() #popping an item off the stack 

     def peek(self):
         return self.items[len(self.items)-1] #peek at the top most item (it remains in the stack)

     def size(self): #returns the size of the stack
         return len(self.items)

     def getStackItems(self):
          return self.items


def mystery_function(mystr):
     s=Stack()
     holding_letters=[]#create a list that will store the string characters as they come in
     for i in range (len(mystr)): #for every element in the total length of the string
          holding_letters.append(mystr[i]) #append each character to the holding_letters list
     
     for i in range(len(holding_letters)):
          s.push(holding_letters[i]) 
     reversed_string=""
     #for every element in the stack, pop each one out
     for i in range(len(holding_letters)):
          reversed_string+=holding_letters.pop()
     print(reversed_string)


mystery_function("marvin")

def hanoi(n, P1, P2, P3):
    """ Move n discs from pole P1 to pole P3. """
    if n == 0:
        # No more discs to move in this step
        return

    global count
    count += 1

    # WHAT IS HAPPENING HERE?
    hanoi(n-1, P1, P3, P2)

    if P1:
        # move disc from P1 to P3
        P3.append(P1.pop())
        print(A, B, C)

    # move n-1 discs from P2 to P3
    hanoi(n-1, P2, P1, P3)

# Initialize the poles: all n discs are on pole A.
n = 3
A = list(range(n,0,-1))
B, C = [], []

print(A, B, C)
count = 0
hanoi(n, A, B, C)
print(count)

Consider the following commands and context:
--------------------------------------------

In this context, you are evaluating the 
following expression using a stack: 
(9 3 - 2 / ) would give a result of?

You would start off with the following:
Push(9) 
Push(3) 


,,,,in the given context, what would the
output be?