CP164 Lab 2 : Stacks

Week of

Using Versus Extending an ADT

Note: In this and future labs we make a distinction between using an ADT and extending an ADT. You must be clear on this distinction:

using an ADT

When asked to use an ADT write a program that is implementation independent, i.e. the program uses only ADT methods (such as those for a stack) and works for either the array or linked implementation of a data structure. Do not change any code in the ADT implementation files such as Stack_array.py.

extending an ADT

When asked to extend an ADT you are going to add new methods to an ADT, meaning that you are going to add code to one or both of the array or linked implementation of a data structure, such as Stack_array.py.


The Stack ADT (Abstract Data Type)

A stack is a data structure that follows LIFO (Last In, First Out) rules. Data is added to the top of a stack and removed from the top of a stack. The Stack ADT provides methods for manipulating data in a stack.

A reminder of some important points of ADT use are:

The following code imports a stack class and the Movie class then initializes a stack variable:

from Stack_array import Stack
from Movie import Movie

s = Stack()
 ...

imports the Stack class from the library file Stack_array.py . This library file can be replaced by any other file that implements the Stack ADT methods.

The line:

from Movie import Movie

gives access to the methods in the Movie.py library file as above.

The line:

s = Stack()

creates a stack named s . The stack is now ready to accept data.


Array-based Stacks

The file Stack_array.py is a text file containing the basic outline of the array-based Stack class. Copy this code into the PyDev module Stack_array.py in your login_data_structures project. The Lab Instructor will walk you through this library and discuss its inner workings.

For all of your data structures (stacks, queues, BSTs, etc.), put your code into libraries in your PyDev project login_data_structures .

  1. For the Stack_array library complete the implementations of the is_empty , pop , and peek methods. These methods extend the Stack ADT.

    Test Stack_array.py:


  2. Write and test the following function:

    def array_to_stack(stack, source):
        """
        -------------------------------------------------------
        Pushes contents of source onto stack. At finish, source is empty.
        Last value in source is at bottom of stack,
        first value in source is on top of stack.
        Use: array_to_stack(stack, source)
        -------------------------------------------------------
        Parameters:
            stack - a Stack object (Stack)
            source - a Python list (list)
        Returns:
            None
        -------------------------------------------------------
        """
    

    Add this function to a PyDev module named utilities in your login_data_structures project so that you have easy access to it later.

    Test utilities.py:


  3. Write and test the following function:

    def stack_to_array(stack, target):
        """
        -------------------------------------------------------
        Pops contents of stack into target. At finish, stack is empty.
        Top value of stack is at end of target,
        bottom value of stack is at beginning of target.
        Use: stack_to_array(stack, target)
        -------------------------------------------------------
        Parameters:
            stack - a Stack object (Stack)
            target - a Python list (list)
        Returns:
            None
        -------------------------------------------------------
        """
    

    Add this function to the PyDev module named utilities in your login_data_structures project.

    Hint: running array_to_stack followed by stack_to_array should reverse the contents of the array.

    Test utilities.py:


  4. Write and test the following function:

    def stack_test(source):
        """
        -------------------------------------------------------
        Tests the methods of Stack for empty and
        non-empty stacks using the data in source:
        is_empty, push, pop, peek
        (Testing pop and peek while empty throws exceptions)
        Use: stack_test(source)
        -------------------------------------------------------
        Parameters:
            source - list of data (list of ?)
        Returns:
            None
        -------------------------------------------------------
        """
    

    Add this function to the PyDev module named utilities in your login_data_structures project.

    Use a list of integers to test your stack code.

    Test utilities.py:


  5. Re-use stack_test , but this time pass it a list of Movie objects. (Use the data in movies.txt).