Dispensers |

## Class `DS_DISPENSER`

A dispenser is called that way because of the analogy with drinks machine in which there is only one button. If you press the button and the dispenser is not empty, you get one can of drink in the exit tray at the bottom, but you cannot choose that can: the machine does. There is also an input slot at the top into which you may deposit new cans. But you have no control over the order in which successive button press operations will retrieve these cans.

Class `DS_DISPENSER` provides facilities such as `item` to get an item from the container (without removing it), `remove` to get rid of this item and `put` to add a new item to the container. Other routines are also available in `DS_DISPENSER`, but they are provided for convenience only since they are all based on these three basic features. See their flat-short forms for details.

## Class `DS_STACK`

A stack is a dispenser with a last-in first-out (LIFO) access policy: the items come out in reverse order of their insertion. Class `DS_STACK` provides more or less the same interface as `DS_DISPENSER`. This may look unusal at first to programmers used to routine names `push` and `pop` instead of `put`, `item` and `remove`. The reasons for this approach are the consistency with the naming conventions used in other containers, as already discussed in the Terminology section of this documentation, and the programming style of Eiffel not to use functions with side-effects.

Two implementations of stacks are provided: one based on arrays, class `DS_ARRAYED_STACK`, and the other using linkable cells, class `DS_LINKED_STACK`. Note that contrary to lists, there is no need for a stack implementation using doubly linkable cells thanks to the property of stacks. All features of `DS_LINKED_STACK` are already optimal and providing a new class`DS_BILINKED_STACK` would not bring anything new apart from a waste of memory space (for the second link in the cells) and of execution time (for managing this second link). Furthermore, since there is only one way to insert and access items in stacks, the difference of performance and the implementation tradeoff between features of the same class that we observed between `DS_LINKED_LIST` and `DS_ARRAYED_LIST` is not relevant for stacks. All basic features of `DS_LINKED_STACK` and `DS_ARRAYED_STACK` are in O(1), which means that their execution time is bounded by a constant regardless of the number of items in the stack. You may want to use `DS_ARRAYED_STACK` if you know in advance the number of items that will be stored in the stack, and `DS_LINKED_STACK` if this number may vary greatly during the execution of the program.

## Class `DS_QUEUE`

A queue is a dispenser with a first-in first-out (FIFO) access policy: the items come out in the order of their insertion. Class `DS_QUEUE` provides the same interface as `DS_DISPENSER`. One implementation of queue using linkable cells is provided: class `DS_LINKED_QUEUE`. All basic features of `DS_LINKED_QUEUE` are already optimal, so as already explained for stacks, there is no need for a new class `DS_BILINKED_QUEUE`. Note that there is no class `DS_ARRAYED_QUEUE` neither. This is because the only optimal way to use arrays is to insert and remove items at the same end of the array. This worked fine with stacks but it is in contradiction with the queue abstraction where items should be inserted at one end and removed at the other end of the data structure.