home *** CD-ROM | disk | FTP | other *** search
/ Deutsche Edition 1 / Deutsche Edition 1.iso / amok / 001-010 / amok07 / stack / stack.doc < prev    next >
Encoding:
Text File  |  1993-11-04  |  4.8 KB  |  199 lines
  1.                          S t a c k
  2.                          =========
  3.  
  4. Documentation for module Stack
  5.  
  6. Author: Michael Frieß [mif]
  7.         Kernerstr. 22a
  8.         7000 Stuttgart 1
  9.  
  10. Copyright remarks
  11. -----------------
  12.  
  13. (C) Copyright 1988 by Michael Frieß. All rights reserved.
  14. The whole package (see chapter package) is public domain.
  15. All (source, documentation and code) is freely redistributable,
  16. as long as my name and the copyright notices remain intact, and
  17. only for non-commercial use. That means you can give it away, but
  18. don´t sell it.
  19. Commercial use without my explicit, written permission is not
  20. allowed. Contact me to get it and, perhaps, to pay some fee.
  21.  
  22. Improvements and new ideas are welcome, as long as the changes are
  23. good documented inline and in the documentation files. I´would like
  24. to know, if you make major changes and repost it.
  25.  
  26.  
  27. Contents
  28. --------
  29.  
  30.  Package
  31.  Introduction
  32.  New Data Type "Stack"
  33.  Stack-Operators
  34.  Example of Use
  35.  Further generic types
  36.  Referenced Literature
  37.  
  38.  
  39. Package
  40. -------
  41.  
  42. The whole package "Stack" consist of following files:
  43.  
  44.   Stack.doc        This documentation file
  45.   Stack.dok        German documentation
  46.   Stack.def        Definition module
  47.   Stack.mod        Implementation module
  48.   Stack.sym        Symbol file
  49.   Stack.obj        Compiled object code
  50.   TestOfStack.mod  Test module (source)
  51.   TestOfStack      Test module in executable form
  52.  
  53.  
  54. Introduction
  55. ------------
  56.  
  57. Often you need basic data structures and operations on
  58. them, which are not implemented in Modula-II.
  59. But Modula-II supports development of generic data types.
  60. The best known example of generic data type is "File".
  61. You can import File and procedures operating on it from
  62. system module "FileSystem".
  63. The one thing, you have to know, is the abstract concept
  64. of files, not the realization.
  65. This module offers a generic type "Stack". So you have not
  66. to reinvent wheel, e.g. program your own stack by pointers,
  67. every time, you need one. You just have to know the
  68. abstract concept of stacks.
  69. You find more description about generic data types and
  70. other stuff in the document written for the module "List".
  71.  
  72.  
  73. New Data Type "Stack"
  74. --------------------
  75.  
  76. The generic type "Stack" is a simple LIFO-list. LIFO means
  77. last-in-first-out, so the last element put into the stack
  78. is the first get out.
  79.  
  80.  
  81. Stack-Operators
  82. ---------------
  83.  
  84. In following operators and their abstract intention are listed.
  85. You can find more details in definition module.
  86.  
  87. o Init
  88.   initializes a new empty stack for further use.
  89.  
  90. o Discard
  91.   discards a stack and frees memory allocation.
  92.  
  93. o Write
  94.   puts a new element at the top of the stack.
  95.  
  96. o Read
  97.   gets top element of stack and removes it from stack.
  98.  
  99. o Empty
  100.   determines, whether a stack is empty or not.
  101.  
  102.  
  103. Example of Use
  104. --------------
  105. Using the type stack is very simple:
  106.  
  107. 1) Import stack and needed operators:
  108.  
  109.    FROM Stack IMPORT stack, Init, Read, Write, Empty, Discard;
  110.  
  111. 2) Define your element type:
  112.    (for example:)
  113.  
  114.    TYPE name = ARRAY [1..30] OF CHAR;
  115.  
  116. 3) Define a stack variable and a variable containing your data:
  117.  
  118.    VAR s       : stack;
  119.        Name    : name;
  120.  
  121. 4) Initialize stack s:
  122.  
  123.    Init (s);
  124.  
  125.    (or with qualified export/import:)
  126.  
  127.    Stack.Init (s);
  128.  
  129. 5) Put first person into stack:
  130.  
  131.    Name    := "Kant";
  132.    Write (s, Name);
  133.  
  134.    inserting further person for example by reading from file or user
  135.    input
  136.  
  137. 6) Get toppest person in stack (probably not Mr. Kant, because he
  138.    is at the bottom of the stack!):
  139.  
  140.    Read (s, Name);
  141.  
  142. 7) Get all persons of stack:
  143.  
  144.    WHILE NOT Empty(s) DO
  145.      Read(s, Name);
  146.      - Display Name -
  147.    END;
  148.  
  149. 8) Discard the stack after use:
  150.  
  151.    Discard (s);
  152.  
  153.  
  154. Easy, isn´t it?
  155.  
  156.  
  157. Further generic types
  158. ---------------------
  159.  
  160. I have implemented other generic data types:
  161.  
  162.   o queue
  163.     a simple FIFO-list
  164.  
  165.   o list
  166.     a more powerful linear list
  167.  
  168.   o AVL-Tree
  169.     See [1] for detailed description
  170.  
  171. Surely there are a lot of other possible generic types:
  172.  
  173.   o pipe
  174.     There is a pipe-handler at a fish-disk (I don´t know the number).
  175.     I would enjoy an implementation of a pipe-handler with whole
  176.     Modula-II support as a generic type.
  177.     The great advantage of a pipe is the simultaneous use by multiple
  178.     processes. For example two processes write data into the pipe and
  179.     one process reads data simultaneous.
  180.     (I´m looking forward the module for fully support of amiga´s multi-
  181.      tasking operating system!)
  182.  
  183.   o BTree
  184.     Another sort of tree also described in [1].
  185.  
  186.   o Hash-Table
  187.     Perhaps a hash-table is also a candidat for generic data type -
  188.     I haven´t thought about it yet.
  189.  
  190. I´m looking forward a lot of other implementations of generic data
  191. types. For free distribution on AMOK-Disks send your implementations
  192. to my address or just to any address of an AMOK-member.
  193.  
  194. Referenced literature
  195. ---------------------
  196.  
  197. [1] N.Wirth "Algorithmen und Datenstrukturen mit Modula-II"
  198.     Teubner, Stuttgart 1986
  199.