Stacks Implementations and Variations

NB: This post is intended for use within our class. It serves as a rough guide for our discussion on the implementation and use of a stack.

For this post there are 2 important requirements:

1. The prerequisite post which was an exercise in creating a stack from previously supplied code. It is imperative that you complete the tasks from that post found here: Stack Operations (Exercise)
2. A Code Packet that you must scrutinize. You can download it from the file link : U2 M1 S02 – Stack Implementations-CodeBackup.zip

Step 1

Assumption: Attempts were made to complete the tasks in Stack Operations (Exercise)

We now look at a sample attempt in flowgorithm (Flowcharting graphical programming language) found within 02 Flowgorithm Stack Exercise of the code packet labeled U2 M1 S2 – StackOperations-01 using size to keep track of top.

Note that this attempt does not use a pointer to the top of the stack; instead we keep track of the size of the stack , much like our implementation found here : Stacks.

It is important to recognize that keeping track of the size of a stack is NOT THE MOST POPULAR implementation.

Still, take some time (~10-15 mins) to observe how the operations for push, pop and peek are accomplished

Step 2

Look at a sample attempt in flowgorithm (Flowcharting graphical programming language) found within 02 Flowgorithm Stack Exercise of the code packet labeled U2 M1 S2 – StackOperations-02 using top instead of size.

In this attempt, we keep track of the index of the item stored at the top of the stack.

Keeping track of top is the most popular accepted way to implement a stack.

Take some time (~10-15 mins) to observe how the operations for push, pop and peek are accomplished, and observe the differenced from the previous sample attempt.

Step 3 – Coded attempt in C (Sample)

Scrutinize the code and run the program found in 03 U2 M1 S2 Stack SimpleExercise. Note that error checking is minimal, and when edge cases are encountered dummy values are returned, e.g as in when we try pushing to an already full stack ( see the push function from more detail )

Although this method works, it’s not the most elegant solution.

Step 4 – Simple Error checking/handling based on Step 3

If we scrutinize the code found in 03.1 U2 M1 S2 Stack SimpleExerciseErrorChecks we find that error messages are added to our push operation and we added the ability for our push operation to return a boolean value. Previously no values were returned, push was void.

However, we now return true if a successful push was made and false (along with an error message) if a failed push was made (e.g our stack was already full when push is called).

Note that peek and pop will always need to return data, and in this case dummy values in error conditions will suffice , but we ensure that error messages are also displayed.

Step 5

Moving on from our exercise we consider the following problem:

Create a program which demonstrates a function which reverses a string (character array) in place , i.e the data of the character array is directly manipulated. Prompt the user to enter a string and output the string in reverse.

The solution to this problem can be found in 04 U2 M1 S2 Stack-String Reversal.

Examine how the code in the main function works. Note that it uses push and pop only to achieve it’s task.

The stack used to implement the solution to this problem is similar to our simple stack with minimal error handling ; only this time our datatype is set to char.

Step 6

if we observe the code in 05 U2 M1 S2 Stack-String ReversalErrorChecks we see that the overall logic for data processing remains the same , only this time we implement some basic error handling techniques.