Stack - Linked-List Implementation

Abstract idea of a stack:
The stack is a very common data structure used in programs. By data structure, we mean something that is meant to hold data and provides certain operations on that data.
One way to describe how a stack data structure behaves is to look at a physical analogy, a stack of books...
Now, a minimal set of things that we might do with the stack are the following:

Place a book on the top... Take one off the top... See if the stack is empty... NOT Empty, there are books on the stack!

We'll consider other, more complex operations to be inappropriate for our stack. For example, pulling out the 3rd book from the top cannot be done directly because the stack might fall over.
How might you get the 3rd book from the top using only the simple operations?
Abstraction

Now, let's think about a stack in an abstract way. I.e., it doesn't hold any particular kind of thing (like books) and we aren't restricting ourselves to any particular programming language or any particular implementation of a stack.
Stacks hold objects, usually all of the same type. Most stacks support just the simple set of operations we introduced above; and thus, the main property of a stack is that objects go on and come off of the top of the stack.
Here are the minimal operations we'd need for an abstract stack (and their typical names):
- Push: Places an object on the top of the stack.
- Pop: Removes an object from the top of the stack and produces that object.
- IsEmpty: Reports whether the stack is empty or not.
Because we think of stacks in terms of the physical analogy, we usually draw them vertically (so the top is really on top).
Order produced by a stack:

Stacks are linear data structures. This means that their contexts are stored in what looks like a line (although vertically). This linear property, however, is not sufficient to discriminate a stack from other linear data structures. For example, an array is a sort of linear data structure in which you can access any element directly. In contrast, in a stack, you can only access the element at its top.
One of the distinguishing characteristics of a stack, and the thing that makes it useful, is the order in which elements come out of a stack. Let's see what order that is by looking at a stack of letters...
Suppose we have a stack that can hold letters, call it stack. What would a particular sequence of Push and Pops do to this stack?
We begin with stack empty:
```
-----
stack
```
Now, let's perform Push(stack, A), giving:
```
-----
| A |  <-- top
-----
stack
```
Again, another push operation, Push(stack, B), giving:
```
-----
| B |  <-- top
-----
| A |
-----
stack
```
Now let's remove an item, letter = Pop(stack), giving:
```
-----              -----
| A |  <-- top     | B |
-----              -----
stack              letter
```
And finally, one more addition, Push(stack, C), giving:
```
-----
| C |  <-- top
-----
| A |
-----
stack
```
You'll notice that the stack enforces a certain order to the use of its contents, i.e., the Last thing In is the First thing Out. Thus, we say that a stack enforces LIFO order.
Now we can see one of the uses of a stack...To reverse the order of a set of objects.
Implementing a stack with an array:
Since a stack usually holds a bunch of items with the same type, we could implement a stack as an array.
Consider how we could have an array of characters, contents, to hold the contents of the stack, and an integer top that holds the index of the element at the top of the stack.
We choose the array to be of size 4 for now.
Starting with an empty stack, we have:
```
-----------------    -----
|   |   |   |   |    | -1|
-----------------    -----
  0   1   2   3      top
contents
```
Now, the same sequence of operations we used before, namely:
```
1. Push(stack, 'A')
2. Push(stack, 'B')
3. ch = Pop(stack)
4. Push(stack, 'C')
```
produce the following effects:
```
1.
-----------------    -----
| A |   |   |   |    | 0 |
-----------------    -----
  0   1   2   3      top
contents

2.
-----------------    -----
| A | B |   |   |    | 1 |
-----------------    -----
  0   1   2   3      top
contents

3.
-----------------    -----
| A |   |   |   |    | 0 |
-----------------    -----
  0   1   2   3      top
contents

4.
-----------------    -----
| A | C |   |   |    | 1 |
-----------------    -----
  0   1   2   3      top
contents
```
If we were actually coding this, we would have to decide what data types are needed for this stack data structure.
Since for the array implementation, we need to keep track of the array contents and a top index, how could we combine the 2 into a single C construct called a stack?
What is the disadvantage of using an array to implement a stack?
Implementing a stack with a linked list:
Using a linked list is one way to implement a stack so that it can handle essentially any number of elements.
Here is what a linked list implementing a stack with 3 elements might look like:
```
list
 |
 v
--------   --------   ---------
| C | -+-->| B | -+-->| A | 0 |
--------   --------   ---------
```
Where should we consider the top of the stack to be, the beginning or end of the list, and why?
How will we represent an empty stack?
C implementation:
Now, think about how to actually implement this stack of characters in C.
It is usually convenient to put a data structure in its own module, thus, we'll want to create files stack.h and a stack.c.
The operations needed for our stack are mainly determined by the operations provided by an abstract stack, namely:
```
StackPush()
StackPop()
StackIsEmpty()
```
We may need to add a few other operations to help implement a stack. These will become apparent as we start to implement the stack.
Before we ponder the details of the stack operations, what must we decide on?
Data types for a stack:
In order to determine what data types we'll need, let's think about how someone will use our stack:
```
1.  type-of-a-stack stack1, stack2;
2.  StackPush(ref-to-stack1, 'A');
3.  StackPush(ref-to-stack2, 'B');
4.  ch = StackPop(ref-to-stack1);
```
First, stack variables must be defined (e.g., stack1 and stack2). Then, stack operations may be called. Those operations will need to know which stack to operate on.
Thus, our goal is to get some kind of type that we can use to keep track of a stack.

Let's start bottom-up from the simplest type and work our way up through types that use the simpler types...
First, we want to write a stack that is very generic. The fact that this stack holds a character is only particular to this program. It should be easy to change the type of things held in the stack.
Let's introduce a type name for the type of thing held in the stack:
```
typedef char stackElementT;
```
Now, elements of the stack are being stored in a linked list. Recall that linked lists are made up of nodes that contain both an element and a pointer to the next node.
How do we define the type for a node?
```
typedef struct stackTag {
  stackElementT element;
  struct stackTag *next;
} stackNodeT;
```
Finally, we need something that holds all the information needed to keep track of the stack. Since elements will be held in nodes, we only need a pointer to keep track of the beginning of the list (which will be our top of the stack).
We suggest that this single pointer be put in a structure, so that we can give it a descriptive field name and so that we can add more fields easily in the future (if needed):
```
typedef struct {
  stackNodeT *top;
} stackT;
```
Filling in stack operations:

Now that we've decided on the data types for a stack, we think we'd like to add 2 extra operations:
```
StackInit()
StackDestroy()
```
They are not part of the abstract concept of a stack, but they are necessary for setup and cleanup when writing the stack in C.
Now, let's think about the StackInit() function. It will need to set up a stack stackT structure, so that we have an empty stack.
What does the prototype for StackInit() look like? What do we do in its body?
Now, what about putting an element in the stack. What should the prototype for StackPush() look like?
The steps needed to push an element onto the stack are:
1. Allocate a new node.
2. Put the element in the node.
3. Link the element into the proper place in the list.
Let's fill in the body of StackPush().
Last, fill in the prototypes for the rest of the stack operations:
```
void        StackInit(stackT *stackPtr);
return-type StackDestroy(parameters);
void        StackPush(stackT *stackPtr,
                      stackElementT element);
return-type StackPop(parameters);
return-type StackIsEmpty(parameters);
```
Under some circumstances, you may be able to pass a stackT and not need a pointer. We prefer to always pass a pointer so that users call all stack functions in the same way.
Testing your implementation:
Here's a sample program stacktest.c and a Makefile for you to test your stack module once you've filled it in.
The program demonstrates one use of the ordering produced by a stack...What is it?

Stack - Linked-List Implementation

Abstraction