John’s Data Structures Week 8

Chapter 6: Stacks

1 . State three more axioms about the stack of T ADT .

For any stack s and element e, pop(push(s,e)) = s .
For any stack s and element e, top(push(s,e)) = e .
For any stack s, and element e, empty?(push(s,e)) = false .

2. Suppose that an ArrayStack is implemented so that the top elements is always stored at store[0] . What are the advantages or disadvantages of this approach?

Using ArrayStack implementation is simple, straight forward and efficient. Disadvantages of an ArrayStack is that if your array gets too big it will use an expensive reallocation technique to expand the array. To avoid this arraystacks are often made to big and then space is wasted.

3 . What should happen if a precondition of a Stack operation is violated?

If a precondition of a Stack operation is violated then an error should be raised.

4 . How can a programmer who is using an ArrayStack or a LinkedStack make sure that his code will not fail because it violates a precondition?

You can create an error class that is a subclass of StandardError and raise this error if a precondition is violated.

5 . Should a LinkedStack have a count attribute? Explain why or why not .

A LinkeStack does not need a count attribute because the topNode will always be stored at the head of the list so if you ever need to know how many items are in the LinkedStack you can just check where the topNode is stored and this will be equal to the count.

6 . Suppose a LinkedStack has a count attribute . State a class invariant relating the count and topNode attributes .

The count and the topNode reference number will always be equal.

7 . Could the top element be stored at the tail of a LinkedStack? What consequences would this have for the implementation?

The top element could not be stored at the tail of a LinkedStack because then the references would be incorrect.

8 . A LinkedStack could be implemented using a doubly-linked list . What are the advantages or disadvantages of this approach?

Pros:

More efficient iteration because you can iterate from both sides, and more efficient deletion and locating of specific nodes.

Cons:

More complex implementation and more memory use.

9 . As noted before, every Ruby value is an object, so every Ruby value has the same type (in a broad sense) . What consequences does this have in implementing the stack of T ADT?

This makes it harder to sort or search nodes by value type because every Ruby value has the same type.

10 . Implement the Stack interface and the ArrayStack and LinkedStack classes in Ruby .