Stacks

Summary: This reading introduces the concept of an Abstract Data Type (ADT) and describes a stack as a specific example.

Contents

• Abstract Data Types
• Stacks
• Array-based Stack Implementation
• List-based Stack Implementation

Abstract Data Types

When we want to work with data on a general level, we often need to describe two basic characteristics: the data we will be storing, and the operations we will want to perform on these data. In computer science, these two characteristics combine to give the concept of an abstract data type or ADT, which allows us to work with data on a conceptual level without worrying about various programming details.

The stack discussed in this reading provides one example of an abstract data type. The queue, discussed in a forthcoming reading, provides a second example.

Stacks

A stack mimics the information that we might keep in a pile on our desk. For example, on our desk, we may keep separate piles for

• bills that need paying;
• magazines that we plan to read; and
• notes we have taken.

(Some of us have more and taller stacks than others.)

These piles have several properties. First, each pile contains the same type of information (e.g., bills, magazines, or notes). In addition, for each pile, we can do several tasks.

1. We can add to the pile by putting information on the top.
2. We can take the top item off of our pile.
3. We can read the item on the top.
4. We can tell whether a pile is empty. (There may be nothing at the spot where the pile should be.)

These operations allow us to do all of our normal processing of data at our desk. For example, when we receive bills in the mail, we add them to our pile of bills until payday comes. Then, we take our bills, one at a time, off the top of our pile and pay them until our money runs out.

When discussing these operations, it is customary to call the addition of an item to the top of the pile a Push operation and the deletion of an item from the top a Pop operation. These semantics correspond to the feel (and perhaps sound) of operations on another familiar stack: the Pez candy dispenser.

More formally, a stack is defined as an abstract data type that can store data and that has the following operations:

Empty

Empty returns true or false, depending upon whether the stack contains any items or not.

Full (optional)

Full returns true or false, depending upon whether the stack contains as much data as it can hold.

Push

If the stack is not full, Push adds the specified item to the top of the stack.
If the stack is full, nothing is added, and an error is reported.

Pop

If the stack is not empty, Pop removes the top item from the stack, and this item is returned.
If the stack is empty, nothing is returned, and an error is reported.

Top

If the stack is not empty, the top item is returned, but the contents of the stack are not changed.
If the stack is empty, nothing is returned, and an error is reported.

This specification says nothing about how we will program the various stack operations; rather, it tells us how stacks can be used. We can also infer some limitations on how we can use the data. For example, stack operations allow us to work with only the top item on the stack. We cannot look at other pieces of data lower down in the stack without first using Pop operations to clear away items above the desired one.

A Push operation always puts the new item on top of the stack, and this is the first item returned by a Pop operation. Thus, the last piece of data added to the stack will be the first item removed. For these functions (along with initialize), you have to pass a pointer to the top of the stack and cannot pass in the actual element, because you need the ability to modify the stack itself, not just a copy of the element on top. For other functions which deal with the stack, you can generally pass in either a pointer to the top of the stack, or the actual element itself.

Array-based Stack Implementation

Stacks in C

One common implementation of a stack involves the use of an array.

More precisely, we store each piece of data as an element of an array. We place the first data item at one end of the array. Then, for a push operation, we add a data item to the next array element. For a pop operation, we return the item at the top of our data, and we record that the top has moved down. This processing requires several parts, including an array (stackArray) of data to store our data items, a variable (topPosition) to keep track of our top element, and a constant (MAX_STACK_SIZE) to keep track of the size of our array. Conceptually, this setup fits together as shown in the figure at right. Note that a stack implementation may have the topPosition as either the index of top element in the stack, or the index of the first empty element (where the next-pushed item would go). Both implementations of stacks are valid.

With this figure, we trace what happens in our stack operations. We start with topPosition equal to -1, because we have no data in the array. Then, we perform a push, we increment topPosition by one, and we store our new item in this new topPosition. Similarly, for a pop operation, we return the item at the topPosition, and we move the topPosition down by one. Finally, for isFull or isEmpty functions, we compare the topPosition with MAX_STACK_SIZE-1 or -1, respectively.

Additional details arise because we must check whether the stack is full or empty before actually performing a push or pop operation, respectively.

Finally, we note that sometimes it is convenient to package the elements together in a struct, perhaps with a typedef. For example, the following declarations might be used when the stack is to store strings.

#define MAX_STACK_SIZE 50
/* Size of all stack arrays */

typedef struct {
  int topPosition;
  char * stackArray[MAX_STACK_SIZE];
} stringStack;      /* Type for a stack of strings */

Complete Stack ADT

The previous section on stacks described the use of arrays to implement this abstract data type. That section utilized the following declarations and function prototypes:

#define MAX_STACK_SIZE 50
/* Size of all stack arrays */

typedef struct {
  int topPosition;
  char * stackArray[MAX_STACK_SIZE];
} stringStack;      /* Type for a stack of strings */


bool
isEmpty (const stringStack * stack);

bool
isFull (const stringStack * stack);

void
initialize (stringStack * stack);

char *
pop (stringStack * stack);

bool
push (stringStack * stack, char * item);

char *
top (const stringStack * stack);

Two comments about this interface are in order. First, several functions do not change the stack; instead, they return properties of the stack (e.g., the top element or whether it is empty). It is possible for these functions to behave correctly by having them take an actual stack as a parameter, rather than a pointer to a stack. For example, we could have used an interface like the following:

bool
isEmpty (stringStack stack);

bool
isFull (stringStack stack);

void
initialize (stringStack * stack);        /* unchanged */

char *
pop (stringStack * stack);               /* unchanged */

bool
push (stringStack * stack, char * item); /* unchanged */

char *
top (stringStack stack);

Note that instead of taking (const) pointers to a stringStack, the functions isEmpty, isFull, and top take simply a stringStack as a parameter.

So why might we opt for the first interface, which solely uses pointers? There are two plausible reasons. First, having all functions take pointers leads to a memorable consistency in the interface; a client programmer does not need to remember, think about, or search the documentation for whether a particular function takes a stack or a pointer to a stack. Second, passing a pointer is more efficient than passing than actual stack, which must be copied in its entirety for each call to these methods. While the strings in the stack are not copied, all the pointers to them are, and this work can be quite excessive in a high-performance operation.

How do we ensure that such functions do not inadvertently change the stacks being given via pointer? The const modifier applied to the parameter signals to the compiler that the struct should not be involved in any assignment operations that change it. Doing so would generate a compiler error.

List-based Stack Implementation

In this section, we implement the same operations using lists and node pointers. Further, because applications should often consider only the conceptual operations of an abstract data type, not the implementation details, we will be careful that the new code we develop still uses exactly the same procedure and function headers as defined earlier for arrays.

When describing this new approach to a stack, we focus on the specification of the top of the stack, and we consider how to locate subsequent items in the stack after we perform a Pop operation. The following figure shows how such a structure could be organized.

In this picture, we store a stack Item in a struct along with a pointer to the next lower Item on the stack. The stack itself is represented with a struct, which specifies the top node and keeps track of the number of items in the stack.

typedef struct {
  unsigned int size;
  stackNode * top;
} stringStack;

We now face at least two choices to store the string data:

• The node could store a pointer to a string, in which case the appropriate declarations for a stack with string data are:

  typedef struct node {
    char * string;
    struct node * next;
  } stackNode;

• The node could contain a copy of the data, leading to these declarations for string data.

  typedef struct node {
    char string[MAX_STRING_LENGTH];
    struct node * next;
  } stackNode;

  In this case, we would copy an original string into the node for a push operation. A top or pop operation would allocate new space (with malloc) for a new string to be returned; then after the new space is allocated, the string stored at the top of the stack would be copied into this new space.

With these declarations, we declare a stringStack variable, which is initialized by setting the size field to zero. We should also set the top field to NULL just to be sure we don't accidentally use a random memory address. Inadvertently dereferencing a NULL pointer will cause a segmentation fault, but inadvertently dereferencing any other memory value could cause all sorts of unpredictable behavior, without anyone necessarily detecting it.

Testing for an empty stack simply involves checking the value of this field. Then the push, pop, and top operations involve inserting, deleting, and reading items at the beginning of the list structure referred to by top. With the use of dynamic storage allocation, the isFull operation is not needed. However, for compatibility with the earlier array implementation of stacks, this function is still included and will always return false. The outlines of these operations are quite similar to the work in the earlier ones. Also, in the pop operation, we free the list item once we have returned the appropriate information. The coding details for these operations will be implemented in the lab.

Once these functions and procedures are defined, we can use them just as we did before. In a program, we must include the appropriate stack declaration (shown earlier in this section); we must write out these procedures; and we must call the initialization procedure. However, once these details are completed, the compatibility of the procedure and function headers allows us to use isEmpty, push, pop, and top without change to the code. Thus, while the implementation of stacks has changed dramatically, the use of stacks in applications is identical.

Hence, we have finally achieved a more abstract data type. The implementation (stack versus array) has been abstracted away as a largely detail of the client program's code.