The purpose of this assignment is to learn about the Go programming language, with an emphasis on interfaces — one of its most distinctive features.

The following questions refer to this interface called Stacker:

type Stacker interface {
    // Pre-condition:
    //    none
    // Post-condition:
    //    returns true if this stack has no elements, and false otherwise
    // Performance:
    //    runs in O(1) time
    isEmpty() bool

    // Pre-condition:
    //    none
    // Post-condition:
    //    returns the number of elements in this stack
    // Performance:
    //    runs in O(1) time
    size() int

    // puts x on the top of the stack (increasing size by 1)
    // Pre-condition:
    //    none
    // Post-condition:
    //    puts a copy of x on top of the stack (and the size of the stack
    //    increases by 1)
    // Performance:
    //    runs in O(1) time most of the time; can occasionally run in O(n)
    //    time if memory re-organization is needed
    push(x int)

    // Pre-condition:
    //    none
    // Post-condition:
    //    If the stack is empty, returns 0 and a non-nil error value (with a
    //    helpful error message).
    //    If the stack is not empty, returns a copy of the top element of the
    //    stack, and a nil value for the error.
    //    In both cases, the stack has the same value after calling peek() as
    //    before.
    // Performance:
    //    runs in O(1) time
    peek() (int, error)

    // Pre-condition:
    //    none
    // Post-condition:
    //    If the stack is empty, returns 0 and a non-nil error value (with a
    //    helpful error message). The stack remains empty.
    //    If the stack is not empty, returns, and removes, the top element of
    //    the stack, and a nil value for the error. In this case, the size of
    //    the stack decreases by 1.
    // Performance:
    //    runs in O(1) time
    pop() (int, error)

    // Pre-condition:
    //    none
    // Post-condition:
    //    Returns a copy of this stack.
    // Performance:
    //    runs in O(n) time, where n is the size of the stack
    copy() Stacker
} // Stacker

Don’t change this interface in any way! It is vital that it remain exactly as given.

Note: Testing is an important part of this assignment, and even though it appears as individual questions below, it would be wise to do the testing as you go, e.g. implement a function and write some tests for it at the same time.

Create a new struct called StackSlice that implements Stacker, and uses an int slice as its internal representation.

In addition to implementing all of the methods in Stacker, write a makeStackSlice() function (not method!) with this header:
```
// returns a new empty stack using an int slice representation
func makeStackSlice() Stacker {
   // ...
}
```
You can use it like this:
```
s := makeStackSlice()
s.push(4)
// ...
```
Create a new struct called StackLinked that implements Stacker, and uses a singly (or doubly) linked list as its internal representation. In addition to implementing all the methods in Stacker, write a makeStackLinked() function (not method!) with this header:
```
// returns a new empty stack using a linked list representation
func makeStackLinked() Stacker {
   // ...
}
```
You can use it like this:
```
s := makeStackLinked()
s.push(4)
// ...
```
Go’s fmt package has a useful interface called Stringer that looks like this:
```
type Stringer interface {   // already defined in fmt
    String() string
}
```
Anything that implements Stringer can be printed with fmt print functions, such as Println and Printf.

Make StackSlice and StackLinked both implement the Stringer interface so that they can be easily printed to the screen to help with debugging.
Put all of your Stacker testing into a single testing function with this header:
```
// s is assumed to be empty
func stackerTest(s Stacker) {
    // ... Stacker test code goes here ...
}
```
stackerTest(s) should be able to test any Stacker s, no matter its implementation. Thus, you only need to write one set of tests that will work for both your slice-based and link-based implementations like this:
```
func stackSliceTest() {
    s := makeStackSlice()
    stackerTest(s)
    fmt.Println("all StackSlice tests passed")
}

func stackLinkedTest() {
    s := makeStackLinked()
    stackerTest(s)
    fmt.Println("all StackLinked tests passed")
}
```
Test thoroughly! Call every function at least once and check that return values are correct. Pay special attention to stacks with 0, 1 or 2 elements, as errors often arise in those extreme cases.

Please note that the very last question below asks you to format the testing code in a particular way. You may want to read that question now so that you can implement the testing the required way from the start.

Implement, and thoroughly test, the following function:

// Pre-condition:
//    none
// Post-condition:
//    s.isEmpty()
func popAll(s Stacker) {
    // ...
}

Implement, and thoroughly test, the following function:

// Pre-condition:
//    none
// Post-condition:
//    returns true if s and t have the same elements in the same order;
//    both s and t have the same value after calling stackEquals as before
// Annoying constraint:
//    Use only Stackers in the body of this functions: don't use arrays,
//    slices, or any container other than a Stacker.
func stackEquals(s, t Stacker) bool {
    // ...
}

Among the interesting features of Go is the set of standard tools it provides for doing things beyond just compiling. One of those tools is go test, which automatically runs test functions that you write.

Structure your assignment so that all the testing can be run by typing “go test”. To do this, you should use two files:
- a1.go contains all the implementation code
- a1_test.go contains all the testing code, in the format needed for go test; the testing package documents all the technical details, but it lacks clear examples of basic test functions, so you might want to look for examples elsewhere (yes, we want you to figure out how to get this working on your own!)
Both of these files should be in a package named a1.

You should assume that the marker will add their own testing file to your project.

What to Submit

Please submit just two files, a1.go and a1_test.go with those exact names. Both should be in a package named a1.

Compress those two files into a .zip archive file (no other formats, please), and submit that .zip file on Canvas.

What to Submit

Related Posts