Let us have a quick look into our cupboard at our best plates. What do we see? We have stacked them one above the other there. If we need a plate before a feudal meal, which one then do we take? We always take the topmost plate from the stack, never one from the middle, let alone one from the bottom. When we put back a plate after the dishes into the cupboard again, where do we put it there? We always put it as the topmost plate on top of the stack.
Such structures, in which elements are stored in a linear sequence and which allow insertion and deletion on one side of the sequence only, do not only occur in daily life quite frequently, but also in algorithmics. They are called stacks, and inserting and deleting elements is called push and pop, respectively.
Because elements are always inserted and deleted on and from the top of the stack only, the last element that was brought into the structure is always the first one that is got out again. One therefore says that stacks work according to the LIFO principle (“last in first out”).
LEDA offers the classes
an implementation for stacks. Objects of the former class are
stacks that can hold an arbitrary number of elements. The latter
class is particularly useful if we know in advance that only a
certain bounded number of elements is ever pushed on the stack
The attentive reader will say now:
“What for do I need these special classes at all, then? I
really can do all this with a
I master thanks to this tutorial now so well. I really simply
can insert or delete something with
pop() at the beginning of the list; it
then behaves exactly like a stack anyway! So what for should I
burden myself now with superfluous stacks? I don't need no beast
These objections are definitely justified if
we look only on the functionality.
But there are at least three good reasons for the use of a
A program becomes more readable and errors become easier to find therein if explicit use of specialized data structures is made.
Simpler interfaces (like in the case of the class
stack) make specialized
implementations possible that are particularly time or
space efficient. For example, the class
stack is implemented with the help
of the particularly space-efficient class
The use of a specialized data structure often leads
to more insight into the problem definition, from which
further improvements in the implementation can arise
then. To give an example: That a given stack will store
only a certain number of elements known in advance during
the overall runtime could be noticed by the programmer only
by explicit use of a stack. A
b_stack then would be the structure
of choice and its use would imply an improvement of
the space efficiency.
This should now be incentive enough for us to devote ourselves to the good old stacks for a little while.