A stack is a data structure that works like a stack of items, such as plates. Items can be placed onto the stack, and the most recently added item can be removed at any point. This principle is sometimes referred to as LIFO (which stands for Last In First Out) because the last item onto the stack is the first one off it.
Stacks have a number of uses. One of them is recursion: although the compiler usually hides the details for you, the arguments to procedures as well as the return addresses are placed on a stack and removed when the procedure exits. You might need a stack if you are simulating recursion.
Another use is to evaluate expressions in postfix or Reverse Polish notation (used by old HP calculators). Basically place numbers on the stack as they are encountered, and whenever an operator is found, pop the top two numbers off the stack, apply the operator to them and push the result back on the stack.
Stacks are easier to implement that queues because you only ever work at one end. The simplest method is to keep an array that contains the items (with the bottom stack element at the start of the array) and a count of how many items there are. To push an item onto the stack, increase the count and write it into the array. To pop an item off the stack, copy the data from the array and decrease the count.
The only disadvantages of this approach are the limits imposed by arrays in some environments such as the 64K limit on data structures in real mode environments (e.g. Turbo Pascal) and the inability to easily resize an array (although you can get around this in Pascal with dynamic allocation). It is possible to implement a stack using a linked list, but it is a lot more complicated.
Last updated Sun Nov 28 22:04:38.0000000000 2004. Copyright Bruce Merry (bmerry '@' gmail dot. com).