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 program stack-lab.c uses a variety of stack operations conforming to a uniform interface (albeit with slightly different semantics).

Approach 1: Passing Pointers

In the first library program stack-lab-1.c, the stack is simply an array of pointers to the strings as pushed; returned strings are the same pointers.

Approach 2: Copying Strings

In the second library program stack-lab-2.c, the stack contains an array of the strings themselves and strings are copied as pushed; returned strings are copied to new buffers.

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 program stack-lab-3.c, the stack contains an array pointers to strings which are freshly allocated and copied as pushed; returned strings are these same buffer copies.

Approach 4: Referencing Copied Strings

In the fourth library program stack-lab-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.