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