Stacks
The primary characteristic of a stack is that the last thing out
is the first thing in. This is called LIFO. In real life, this is
the way that a stack of cafeteria trays work. The topmost one is the one
that will be taken next. Its definition is independent of the way it is
implemented as are all the data structures more complex than an array.
There are four operations used on a stack; push, pop,
is_stk_empty and is_stk_full . There is also a pointer to a
location on the stack. This is the top of stack (TOS) pointer and
it indicates the place where the next item will be added or removed.
- pop
return to the caller the top item on the stack and remove it
- push(item)
put the item on the top of the stack
- is_stk_empty,full
return true if the condition holds, false otherwise
Only the item at the top of the stack can be referred to. Any reference
to the underlying data structure is illegal. By always using the routines
described above, the LIFO characteristic of the stack is preserved. The
routines below use lists but it is vital that you not confuse stacks and
lists. Here is code that is built from the list classes defined above to
implement a stack. I developed an interface to define what it means to be
a stack and to show one way to use interfaces.
The code is also here
First. here is the interface.
This describes the operations that are allowed on, in fact, define,
a stack.
This is the main stack class
that uses the list code to implement the interface. It also adds one
method not in the interface.
A small driver class
and the output.
The stack is empty
There are 0 elements in the stack
There are 3 elements in the stack
Stack Contents
x= 3 y= 24
x= 2 y= 24
x= 1 y= 23
starting chop
Popped element: x= 3 y= 24
Stack Contents
x= 2 y= 24
x= 1 y= 23