Stacks

Picture yourself in line at a cafeteria. The plates are stacked up in a big stainless steel housing, which is spring-loaded. Only one plate is visible, but when you pick it up, the next one pops up. You can always get the top plate (until you run out of plates), but you can't reach down and get the third one from the top.

A stack of data elements works the same way. You can add an element at the top, or you can remove one from the top. You can't reach one at the bottom, or in between, except by removing the ones above it first.

Stack Operations

• Push -- add an element to the stack;
• Pop -- remove an element from the stack.

For example, the application may need to examine the top of the stack, without removing it. It could do so by popping and then immediately pushing. However, a separate top operation would be more efficient and easy to implement.

Implementing a Stack

• Arrays. Declare an array of data elements and use an index or subscript to keep track of the top of the stack. Make sure you don't overflow the array.
• Linked lists. Allocate a data element whenever you push, and deallocate it whenever you pop. Maintain a pointer to the top of the stack (NULL when the stack is empty).

Uses for Stacks

• Reversing a Sequence

  A stack operates on the LIFO principle: last-in-first-out. Sometimes you can put this fact to use.

  For example, JOCKEY uses the JK025 routines to store lines of a service order, and having stored them, to read them one character at a time, using the JKBLREAD routine.

  You can read some characters and then back up -- in effect, unreading them -- by calling JKBLPUSH. When you start reading forwards again, you want to reread the same characters in the original sequence -- which is the reverse of the sequence in which you called JKBLPUSH.

  Internally, JKBLPUSH pushes the characters onto a stack. Later calls to JKBLREAD pop the characters back off the stack, until the stack is empty.

• Implementing a language.

  In most computer languages, a subroutine call involves stack operations. The runtime system pushes a return address onto a stack, along with any parameters. It may also allocate space on the stack for temporary variables which are local to the subroutine being called. Somewhere it also stores the amount of stack being allocated, or the address of the previous top-of-stack. This whole chunk of stack is called a stack frame.

  When the subroutine exits, it pops the entire stack frame and transfers control to the return address previously stored there.

  If one subroutine calls a second subroutine, it pushes a second stack frame on top of the first one, and so on. Many processors provide hardware support to make these stack operations efficient.

  COBOL does not usually follow this paradigm. That's why it doesn't support recursion, which requires multiple stack frames to be piled on top of each other for the same routine.

• Simulating recursion

  Sometimes the best algorithm is inherently recursive, especially when dealing with branching structures such as trees and graphs. For example, the most natural way to traverse a binary tree is to apply the following procedure to the root node:

  • Do something with the node
  • Traverse the left child
  • Traverse the right child

  Although COBOL does not support recursion, you can fake it with iteration. As you traverse the tree (or whatever) you maintain a stack of data elements, each of which contains whatever information you need at that level of recursion. Each push corresponds to a recursive call, and each pop corresponds to a return from a recursive call.

  If you think this approach sounds awkward and obscure -- you're right. Recursion is much simpler and more elegant in a language that supports it directly, such as C or Pascal. But sometimes a programmer's just gotta do what a programmer's gotta do.

COBOL Home

Data Structures