2.4. Stacks

2.4. Stacks
	Chapter 2. Simple data types and simple container types

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?^[20] 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”).

Figure 2.17. A stack

LEDA offers the classes stack and b_stack as 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 (“bounded stack”).

What for shall we use a stack at all?

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 list, which I master thanks to this tutorial now so well. I really simply can insert or delete something with push() and 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 of burden!” These objections are definitely justified if we look only on the functionality.^[21] But there are at least three good reasons for the use of a “real” stack:

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 slist.
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.

^[20]Of course we do not eat alone at a feudal meal, as a rule. Then we take the topmost plates of the stack.

^[21]And many LEDA users indeed do not pay attention to the classes stack and b_stack nor to the related classes queue and b_queue, and simply use always the class list.


2.3.8. Singly linked lists (class slist)		2.4.1. Stacks with an unbounded number of elements (class stack)