Continuing on yesterday's topic of Abstract Data Types, this evening I will be explaining what is probably the most common ADT – the Stack. ActionScript 2.0 source code is included in the examples.
As stated yesterday, an ADT is the declaration and the specifications (interface). Because of this, the ADT itself is actually language independent. A Stack is a Stack regardless of the language it is implemented in (Java, C#, or even ActionScript).
The specifications of any ADT should only focus on "public" operations because the users of the ADT are unaware of any private variables. This includes documentation – do not include private variable information in an ADT specification. Instead, document ADTs with"“preconditions" and "postconditions." Preconditions are statements that are assumed to be true before an operation executes. Postconditions are statements that will be true after an operation has completed. It is the ADT user's responsibility to ensure that the preconditions are true before calling an operation, not the responsibility of the ADT programmer. If a precondition is not satisfied unexpected results will occur. Whenever possible, try to define the preconditions and postconditions in terms of the parameters of the operation.
Operations on an ADT, as stated yesterday, fall into four categories. These categories are:
- Constructors - create an instance of the ADT
- Interrogators - return information about an instance without modifying the instance
- Manipulators - modify the properties of an instance without returning any information about it
- Destructors - de-allocate storage space, close any open documents, and release system resources
IMPORTANT: After an instance is created it can be interrogated and manipulated, but not by the same operation.
Please note is that an ADT constructor is not the same as a class constructor. This is because ADTs are language independent and not every programming language has a "new" operator. Rather, the constructor is invoked just like any operation by a simpe method call.
Another thing to note: in our example, there is no destructor. This is because the Flash Player uses a garbage collector that automagically cleans up resources of an object that has been deleted or fallen out of scope.
Additionally, before I get into the Stack ADT specification, there are few points yet to be made. Because access and modifiers are separate, we normally do not need to give postconditions for access functions. Likewise, postconditions should describe how the object has changed in terms of the access functions. If this cannot be done, then the ADT needs to be re-designed until it has all the access functions required. All of this may seem a little confusing at first, but it should become clearer as we step through an example.
And finally, the part you've all been waiting for…
The Stack ADT
A Stack is a concept that you’re all familiar with whether you realize it or not. Think about a pile of papers. You can put a paper on top of the pile, determine if there are papers in the pile, inspect the top paper to see what it contains, and remove the top-most paper from the pile. Ok, well, if you work hard enough you can probably remove other papers besides the top one, but for examples sake let’s say only the top paper can be removed from the pile.
The Stack ADT is exactly this. It is a LIFO data structure because the "Last In" the stack is the "First Out" out of the stack. It is a linear structure where insertions and deletions always occur at the same end. This end is called the "top" of the stack and contains the element most recently inserted. The top of the stack is also the only element that can be inspected.
When we "push" an element on the stack, we insert an item on the top. Likewise, we can "pop" the element that is on the top to remove it. The "top" operation will let us inspect the element on the top, provided the stack is not empty. Note that top and pop are two different operations. Traditionally, pop will return the top element and remove it from the stack, but this violates the rule of one category per operation.
Without further ado, here is the pseudocode for the Stack ADT (real code will be made available further down the page). Note that I'm using the ActionScript 2.0 convention of declaring the return type after the function.
create() : StackPrecondition: none
Postconditions: if s = create() then:
- s is a newly created object
- isEmpty(s) returns true
isEmpty(Stack s) : Boolean
Precondition: s is not null
top(Stack s) : Object
Precondition: isEmpty(s) returns false
push(Stack s, Object o) : Void
Precondition: s is not null
Postconditions:
- top(stack) returns o
- isEmpty(s) returns false
pop(Stack s) : Void
Precondition: isEmpty(s) returns false
Postconditions: See Explanation that follows
Explanation: A push immediately followed by a pop has no effect on the stack. This is the Stack Axiom. Any sequence of pushes and pops (after create has been called) will yield the same result as a certain sequence of only push operations.
destroy(Stack s) : Void
Precondition: s is not null
Postcondition: s is null
The above is The Stack ADT. This is what a Stack is, independent of any implementation, and exactly the same in every programming language. We have met the criteria of an ADT by only defining the declaration and interface. It is at this point that someone can start using a Stack in their application because the implementation is a detail that can be worried about later. We know how a Stack functions and we can start using it.
To continue on with the example, click here to download my commented ActionScript 2.0 implementation of the Stack, complete with Stack class, IStack interface, and an example use-case
i need a stack implementation on how to evaluate a postfix expression. The class should have 2 methods;one to store numbers and the other to store operations(+-*/).
that's good though i don't really understand it i mean kinda lang