Abstract Data Structures 2 - Stacks

Introduction

In the first section, we saw how to make a basic array, a static data structure to hold a number of similar items. Arrays are useful if you have a lot of items with the same qualities and behaviour; stick them in an array, and you can then treat the array as one variable instead of having many separate variables to worry about! In fact, anywhere where you would have a list of similar files or data items, can lend itself to an array.

But there is much more to arrays than simply acting as containers. We can build more complicated abstract structures, for holding and manipulating data, out of an array. It's an Array-Plus, if you like. We can build these structures as separate entities or units, then incorporate these units into any software that can use them. In Delphi or Pascal, it's normal to build them as separate units; in Java, you can make them into their own classes.

If you have already studied some Object Oriented technology, you will know that your units should be reusable wherever possible; if we build our structure correctly, it should work seamlessly in any program, with no modifications. (This is one of the purposes of encapsulation.)

The simplest structure of all, and probably the most commonly found in a modern computer system, is the stack. It is a simple matter to make a stack out of a basic array, and that is what we are going to start with. Before we begin, though, I am going to explain how a stack works, where you would use one, and where you will find one in a modern computer system.

How a Stack works

A stack, like an array, is simply a list of similar data items, but with the restriction that items can only be added to, or removed from, the end of the list. And... that's it, really! The term stack arises from the analogy with a stack of plates; new plates can only be added to the top of the stack, and plates can only be removed from the top too. This is why you will sometimes see a stack called a LIFO (last one in, first one out) structure.

Stacks were originally used by system programmers, especially when writing compiler or interpreter programs. They are used to manage memory. A stack in memory needs not only the actual memory space, but also three counters, or pointers, commonly called SB (Stack Base), SP (Stack Pointer) and SL (Stack Limit). Stack base is the address in memory that the stack starts from; stack limit is the address that signifies the end of the stack space; and stack pointer shows where the last item was actually entered. Obviously that has to be somewhere between the stack base and the stack limit, otherwise the item is trespassing on space that does not "belong" to the stack.

Whenever we want to access our stack, we always look at the pointer value first. If it's at the stack limit, we are not allowed to add anything else, as that would result in an overflow. If the pointer is at the base, we are not allowed to take anything away, as that would result in an underflow.

Stack Operations

As our stack will be implemented as a separate unit, we can include several procedures or methods that the stack can use. Although this is a software stack, it is conventional to keep the operation names that originated from hardware stacks. The two basic operations your stack will need are called PUSH and POP.

Stack PUSH

Increment the Stack Pointer.
Check that this is not now beyond the Stack Limit.
If it isn't, put the new item on the stack.

Stack POP

Check that the Stack Pointer isn't below the base of the stack.
If it isn't, remove the item at the Stack Pointer position.
Decrement the Stack Pointer.

Some other uses of a stack

Stacks are used in subroutine linkage - calling a procedure, a function, or a method. The main program code is pushed on a stack, byte by byte, while the processor goes off and deals with the subroutine; once control is due to be returned to the main program, the stack is popped and the instructions restored in their original order.

Stacks are also used within the ALU for evaluating arithmetic or boolean expressions. Consider this equation -

Q = (A + B ) * C + D / E

Remembering your BODMAS, anything in brackets gets evaluated first. Then division, multiplication, addition and subtraction, in that order. This is how the routine would work at processor level -

• Load A
• Add B
• Mul C #At this point we PUSH result so far
• PUSH
• Load D
• Div E #At this point the working register contains D divided by E
• POP #We now POP the stack with the earlier result and add it on
• Add
• Out Q #And output the result!

Implementing a Stack

In Delphi, we can implement a stack as a record. The record will contain an array, a stack base, a stack pointer and a stack limit. (The Stack Base will usually be zero; the Stack Limit will be the max-size as defined in the CONST section of the main program.) In Java, we can implement the stack as an object, with four attributes; the array part, the stack base, the stack pointer and the stack limit.

In your unit or class, you should implement the two operations PUSH and POP. It is also an idea to add a couple of functions, StackEmpty and StackFull, which return boolean values. These come in handy later on!

You can download an example of a Delphi stack here, and a Java stack here.

Make sure that you understand the implementations and workings of the stack before you proceed onto the next topic. Once we have built a stack, we can use the same techniques to build two new structures - a Queue and a DEQueue.