- Prof. Dancy's Site - Course Site -

Stack Practice #1

We are going to practice using Stacks to solve a problem. This will be somewhat similar to lab in that you will have to complete some methods for our Stack class. You will eventually also have to use this stack to create a Delimiter class that we can use to judge whether every open delimiter has a matching close delimiter in any given file (We're going to hold off for now and just focus on completing the Stack class first).

A note on collaboration/group help

I do not mind working together to understand the answers if your having a bit of trouble. Realize that this is meant to be a practice a assignment for you to use to practice a bit with the Stack ADT and Linked Lists. If you straight up copy stuff, you're really only hurting yourself.

Let's kill the lights and jump into some Stack code

Developing a Stack Class

For your lab, you had to develop methods for a Stack class using an Array as your underlying data structure.
For this exercise, we'll use Linked Nodes (a linked list) to as our underlying data structure.

Create a new file called StackExercise.py. You will put the code below (and the code you develop) into this file and submit the file on Google Classroom.

Stack Node Helper class

We'll create a _StackNode helper class. Notice that we use the underscore ("_") to denote that it is a hidden classn (meaning that only our Stack actually should/will use it)

class _StackNode :
def __init__( self, item, link ) :
	self.item = item
	self.next = link

Stack class

For our Stack class, we want to create several methods:

I'm going to give you the constructor (__init__) and the peek method

The constructor

We start by creating a construtor that simply initializes an empty stack, with the _top of the stack being pointed to None and the _size of our stack being initially 0.

class Stack :
	def __init__( self ):
		self._top = None
		self._size = 0

The peek method

The peek method allows us to "see" what is on the top of the stack. It returns the item being pointed to by the _top attribute. In addition, our assert statement assures that the stack is not empty.

def peek( self ):
	assert not self.is_empty(), "Cannot peek at an empty stack"
	return self._top.item

The remaining methods

Your job is to complete the remaining methods

The push method

This method will push an item to the top of your Stack. This method takes in an item, it is up to you to create StackNode to encapsulate (hold) the item and point to the next Node (i.e., using the _next attribute of your new StackNode that will be at the _top_ of your Stack).

def push( self, item ):
	''' Method to push an item to the top of a Stack
	'''
The pop method

This method will pop an item from the top of your Stack. This method should return the item at the top of the stack (not the entire StackNode.) Your pop method will need to change the pointer of the _head so that it is not pointing to the _StackNode at the top of the Stack, but instead the StackNode _next to the previous top StackNode. Don't forget to update your size!

def pop(self):
	''' Method to pop an item from the top of a Stack
	'''
The __len__ method

This method will return the number of items currently in your Stack

def __len__(self):
	''' Overrides the Python len() method for Stack objects
	'''
The is_empty method

This method will return a boolean that tells us whether the Stack is (or is not empty)

def is_empty(self):
	''' Used to tell us whether the Stack is empty (returns a True or False)
	'''

Once you have completed these methods, test your Stack class (the lab might be helpful for this, or you can just write a main function that creates a stack and uses all of the methods you've created).
After you're sure it works, submit your file on Google Classroom.