Stack Variations

Summary: This reading gives background for several stack variants you will compare in the project.

Introduction

The example libraries for this project (detailed below) show four different approaches for implementing a stack based on an underlying array structure. In particular, each approach uses a fixed size array to store strings on a stack. When all items in the array are in use, the stack is full and further push operations will fail.

The variations among the stack implementations involve what is actually stored during a push operation and what is returned during a pop operation. In brief, some possibilities are:

• push operation (given a pointer to a string)
  • the stack contains a reference to the original string pushed
  • the stack contains a new copy of the string being pushed
  • push operation makes a copy of the string being pushed, and the stack contains a reference to the new copy
• pop operation (returns a pointer to a string)
  • the string reference returned identifies a reference stored in the stack
  • the string reference returned identifies the location of a string located within the stack itself
  • the pop operation makes a new copy of the string reference in the stack and returns a reference to this new copy

The main program in the reading pushes several items onto several stacks and then pops the stacks and prints the results. All four stack approaches work fine in this simple context.

Details

In this project, you will compare four stack implementations. The main client program stack-lab.c uses a variety of stack operations conforming to a uniform interface (albeit with slightly different semantics).

Interface

The interface is given by stack.h. The function signatures across the various approaches are the same. The primary difference from the approaches we have seen before is that the initialize function allocates a new stack struct from the heap with malloc. Because the ADT in C requires an incomplete type definition of struct string_stack, we can only use pointers in the client code.

Shared Implementation

Despite the implementation differences described below, the general stack library file stack.c contains functions whose implementations are identical for all stack ADTs.

Approach 1: Passing Pointers

In the first library stack-1.c, the stack is simply an array of pointers to the strings as pushed; returned strings are the same pointers. It uses the header stack-pointer.h to complete the definition of a struct string_stack.

Approach 2: Copying Strings

In the second library stack-2.c, the stack contains an array of the strings themselves and strings are copied as pushed; returned strings are copied to new buffers. It uses the header stack-buffer.h to complete the definition of a struct string_stack.

For illustration, the size of each string on the stack is limited to just a few characters.

Approach 3: Allocating and Copying Strings

In the third library stack-3.c, the stack contains an array of pointers to strings which are freshly allocated and copied as pushed; returned strings are these same buffer copies. It uses the header stack-pointer.h to complete the definition of a struct string_stack.

Approach 4: Referencing Copied Strings

In the fourth library stack-4.c, the stack contains an array of the strings themselves and strings are copied as pushed; strings returned by top and pop are simply references to the buffers in the stack. It uses the header stack-buffer.h.

Using ADTs: Makefile

The Makefile illustrates how the four different library files above can share only two different headers (corresponding to the storage mechanisms) and how the same client program (stack-lab.c) can be linked with each of these four libraries to produce executables with slighty varying implementations, but largely the same stack semantics.