Python代写：CP164 Stacks

发表于   |   分类于

Introduction

这次需要代写的是一个关于Stack的Lab作业，由于是Lab作业，工作量并不大，都是基本的Stack操作。

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:

  • No matter what the underlying implementation of the stack programs should access a stack only through these methods.
  • As a corollary to the first point, the stack can be implemented in any number of ways so long as any given implementation follows the ADT function requirements. The implementation must invisible to the program using the Stack ADT.
  • A stack may store any type of data, although all the data it stores should be of the same type.

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

1
2
3
4
5
from stack_array import Stack
from food import Food

s = Stack()
 ...

The line:

1
from stack_array import 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:

1
from food import Food

gives access to the methods in the food.py library file as above.
The line:

1
s = Stack()

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

Project References

As we work through the term we will be creating a number of different data structures and adding more functionality to the Food library already written. Making sure that each new project has the latest version of a data structure or Food library is difficult to do if we are reduced to copying and pasting our pydev modules into each new project. Fortunately, Eclipse provides a much better mechanism to reference code. Setting up Project References allows you to link one Pydev project to another, and to use the code from one project in another with the import and from … import * statements already shown. Nothing needs to be changed in your source code.
To make a reference from one project to another in Eclipse, right click on a project name in the Navigator pane. From the resulting pop-up menu click on Properties and then on Project References in the resulting dialog box.
Click on the check box of all projects that you wish to reference from the current project. In this example the project album is already selected, and the project data_structures will be added as a reference. Once this is done all of the classes in both album and data_structures will be available through import statements.
A few things to keep in mind when using project references:

  • All referenced projects must be open when attempting to run a program.
  • Submit all referenced projects as part of your Eclipse archive (.zip) file when submitting exercises or the markers will not be able to run your programs. You may select multiple projects to include in an Eclipse archive file.
  • Do not use the same Pydev module names in two different referenced projects or Eclipse will not know which one an import statement is supposed to be referring to.
  • Project references go one way only. If the project stacks references the project data_structures, then data_structures should not reference stacks. Circular references are a very bad idea.
  • Upon occasion referenced projects may become ‘out of sync’ with the project that references them. To fix this, right-click on the project and choose Refresh to update Eclipse from the file system.

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 (where login is your Network login). Thus, a student with the Network login barn4520 should name their projects barn4520_Food and barn4520_data_structures.) The Lab Instructor will walk you through this library and discuss its inner workings.

Tasks

(If you were unable to complete Lab 1 correctly, you may use these files: food.py, food_utilities.py, and foods.txt as the basis for your lab. These files will not be available until after the labs for the previous week are completed.)
For the appropriate tasks you may download and use the Food class definition in food.py from Lab 1.
For all of your data structures (stacks, queues, BSTs, etc.), put your code into libraries in your Pydev project login_data_structures.

  • For the stack_array library complete the implementations of the is_empty, pop, and peek methods. These methods extend the Stack ADT.
  • Write and test the following function:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    def array_to_stack(s, a):
        """
        -------------------------------------------------------
        Pushes contents of a onto s.
        Use: array_to_stack(s, a)
        -------------------------------------------------------
        Preconditions:
            s - a Stack object (Stack)
            a - a Python list (list)
        Postconditions:
            The contents of a are moved into s, a is empty.
        -------------------------------------------------------
        """

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

  • Write and test the following function:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    def stack_to_array(s, a):
        """
        -------------------------------------------------------
        Pops contents of s into a.
        Use: stack_to_array(s, a)
        -------------------------------------------------------
        Preconditions:
            s - a Stack object (Stack)
            a - a Python list (list)
        Postconditions:
            Contents of s are moved into a, s is empty.
        -------------------------------------------------------
        """

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

  • Write and test the following function:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def stack_test(a):
        """
        -------------------------------------------------------
        Tests 
        Use: stack_test(a)
        -------------------------------------------------------
        Preconditions:
            a - list of data (list of ?)
        Postconditions:
            the methods of Stack are tested for both empty and 
            non-empty stacks using the data in a:
            is_empty, push, pop, peek
        -------------------------------------------------------
        """
        s = Stack()

        # tests for the stack methods go here
        # print the results of the method calls and verify by hand

        return

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.

  • Re-use stack_test, but this time pass it a list of Food data. (Use the data in foods.txt).