| Dispensers | |
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.
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.
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.
|
Copyright © 1999-2001, Eric
Bezault mailto:ericb@gobosoft.com http://www.gobosoft.com Last Updated: 31 March 2001 |
  |