home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 5 / 05.iso / a / a009 / 6.ddi / SAMPLE.LIF / STACK.PRG < prev    next >
Encoding:
Text File  |  1991-04-14  |  3.8 KB  |  150 lines
  1. /***
  2. *  Stack.prg
  3. *  Functions to implement stacks.
  4. *  Copyright (c) 1990 Nantucket Corp.  All rights reserved.
  5. *
  6. *  NOTE: compile with /n/w/a/m
  7. */
  8.  
  9. /***
  10. *    What Is a Stack?
  11. * 
  12. *    A stack is a common Last-In-First-Out (LIFO) data structure.
  13. *    An analogy would be a stack of books on a table. If you
  14. *    place Book A on the table, then place Book B on top of Book
  15. *    A, then place Book C on top of Book B, you have created a
  16. *    stack with three members. Book C is the "top" of the stack;
  17. *    Book A is the "bottom" of the stack.
  18. *
  19. *    Adding a new item to a stack is referred to as "pushing"
  20. *    the item onto the stack. Thus we have "pushed" three items
  21. *    onto our stack of books.  Removing the top item of the
  22. *    stack is called "popping" the item. Unlike a stack of books,
  23. *    you can't pull something out of the middle of a stack data
  24. *    structure -- the items are always popped in reverse order.
  25. *    That is, the last item in is the first item out (LIFO).
  26. *
  27. *    Using the functions in this file, we could model our stack
  28. *    of books like this:
  29. *
  30. *    // Create an empty stack
  31. *    aStack := StackNew()
  32. * 
  33. *    // "Push" each item onto the stack
  34. *    StackPush( aStack, "Book A" )
  35. *    StackPush( aStack, "Book B" )
  36. *    StackPush( aStack, "Book C" )
  37. *
  38. *    // Now "pop" them off
  39. *    ? StackPop( aStack )      // Prints "Book C"
  40. *    ? StackPop( aStack )      // Prints "Book B"
  41. *    ? StackPop( aStack )      // Prints "Book A" (the stack is now empty)
  42. *
  43. *
  44. *    A real example might be a stack of color settings:
  45. *
  46. *    aColors := StackNew()
  47. *
  48. *    StackPush( aColors, SETCOLOR() )  // Save current color setting
  49. *    SETCOLOR( .... )                  // Change color setting
  50. *    ....                              // Call other functions doing same
  51. *                                      // thing
  52. *
  53. *    SETCOLOR( StackPop( aColors ) )   // Restore color on way out
  54. *
  55. */
  56.  
  57.  
  58. /***
  59. *  Functions:
  60. *
  61. *    StackNew() --> aStack
  62. *    Create a new stack
  63. *
  64. *    StackPush( <aStack>, <exp> ) --> aStack
  65. *    Push a new value onto the stack
  66. *
  67. *    StackPop( <aStack> ) --> value
  68. *    Pop a value from the stack, return NIL is stack is empty
  69. *
  70. *    StackIsEmpty( <aStack> ) --> lEmpty
  71. *    Determine if a stack has no members
  72. *
  73. *    StackTop( <aStack> ) --> value
  74. *    Return top stack member without removing from stack
  75. *
  76. */
  77.  
  78.  
  79. /***
  80. *   StackNew() --> aStack
  81. *   Create a new stack
  82. */
  83. FUNCTION StackNew()
  84.    RETURN {}
  85.  
  86.  
  87. /***
  88. *   StackPush( <aStack>, <exp> ) --> aStack
  89. *   Push a new value onto the stack
  90. */
  91. FUNCTION StackPush( aStack, exp )
  92.    // Add new element to the stack array and then return the array
  93.    RETURN AADD( aStack, exp )
  94.  
  95.  
  96. /***
  97. *   StackPop( <aStack> ) --> value
  98. *   Pop a value from the stack
  99. *
  100. *   Return NIL if nothing is on the stack.
  101. */
  102. FUNCTION StackPop( aStack )
  103.    LOCAL valueLast, nLen := LEN( aStack )
  104.  
  105.    // Check for underflow condition
  106.    IF nLen == 0
  107.       RETURN NIL
  108.    ENDIF
  109.  
  110.    // Get the last element value
  111.    valueLast := aStack[ nLen ]
  112.  
  113.    // Remove the last element by shrinking the stack
  114.    ASIZE( aStack, nLen - 1 )
  115.  
  116.    // Return the last element's value
  117.    RETURN valueLast
  118.  
  119.  
  120. /***
  121. *  StackIsEmpty( <aStack> ) --> lEmpty
  122. *  Determine if a stack has no members
  123. *
  124. */
  125. FUNCTION StackIsEmpty( aStack )
  126.    RETURN EMPTY( aStack )
  127.  
  128.  
  129. /***
  130. *  StackGetTop( <aStack> ) --> value
  131. *  Retrieve top stack member without removing
  132. *
  133. */
  134. FUNCTION StackGetTop( aStack )
  135.    //
  136.    // Return the value of the last element in the stack array
  137.    RETURN ATAIL( aStack )
  138.  
  139.  
  140. /***
  141. *  StackTop( <aStack> ) --> value
  142. *  Retrieve top stack member without removing
  143. *
  144. */
  145. FUNCTION StackTop( aStack )
  146.    //
  147.    // Return the value of the last element in the stack array
  148.    RETURN ATAIL( aStack )
  149.  
  150.