Stack - Array 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):
1. push: Places an object on the top of the stack.
2. pop: Removes an object from the top of the stack and produces that object.
3. 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).
4. 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. However, you can access any element in an array--not true for a stack, since you can only deal with 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 stack.push(A), giving:
```
-----
| A |  <-- top
-----
stack
```
  Again, another push operation, stack.push(B), giving:
```
-----
| B |  <-- top
-----
| A |
-----
stack
```
  Now let's remove an item, letter = stack.pop(), giving:
```
-----              -----
| A |  <-- top     | B |
-----              -----
stack              letter
```
  And finally, one more addition, stack.push(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.
5. Implementing a stack with an array:
  Let's think about how to implement this stack in the C++ programming language.
  First, if we want to store letters, we can use type char. Next, since a stack usually holds a bunch of items with the same type (e.g., char), we can use an array to hold the contents of the stack.
  Now, consider how we'll use this array of characters, call it contents, to hold the contents of the stack. At some point we'll have to decide how big this array is; keep in mind that a normal array has a fixed size.
  Let's choose the array to be of size 4 for now. So, an array getting A, then B, will look like:
```
-----------------
| A | B |   |   |
-----------------
  0   1   2   3
contents
```
  Is this array sufficient, or will we need to store more information concerning the stack?
  Answer: We need to keep track of the top of the stack since not all of the array holds stack elements.
  What type of thing will we use to keep track of the top of the stack?
  Answer: One choice is to use an integer, top, which will hold the array index of the element at the top of the stack.
  Example
  Again suppose the stack has (A,B) in it already...
```
stack (made up of 'contents' and 'top')
-----------------   -----
| A | B |   |   |   | 1 |
-----------------   -----
  0   1   2   3      top
contents
```
  Since B is at the top of the stack, the value top stores the index of B in the array (i.e., 1).
  Now, suppose we push something on the stack, stack.push('C'), giving:
```
stack (made up of 'contents' and 'top')
-----------------   -----
| A | B | C |   |   | 2 |
-----------------   -----
  0   1   2   3      top
contents
```
  (Note that both the contents and top part have to change.)
  So, a sequence of pops produce the following effects:
  1. letter = stack.pop()
    stack (made up of 'contents' and 'top') ----------------- ----- ----- | A | B | | | | 1 | | C | ----------------- ----- ----- 0 1 2 3 top letter contents
  2. letter = stack.pop()
    stack (made up of 'contents' and 'top') ----------------- ----- ----- | A | | | | | 0 | | B | ----------------- ----- ----- 0 1 2 3 top letter contents
  3. letter = stack.pop()
    stack (made up of 'contents' and 'top') ----------------- ----- ----- | | | | | | -1| | A | ----------------- ----- ----- 0 1 2 3 top letter contents
  so that you can see what value top should have when it is empty, i.e., -1.
  Let's use this implementation of the stack with contents and top.
  
  What happens if we apply the following set of operations?
  1. stack.push('D')
  2. stack.push('E')
  3. stack.push('F')
  4. stack.push('G')
  giving:
```
stack (made up of 'contents' and 'top')
-----------------   -----
| D | E | F | G |   | 3 |
-----------------   -----
  0   1   2   3      top
contents
```
  and then try to add H with stack.push('H')?
  Thus, what is the disadvantage of using an array to implement a stack?
6. Dynamically-sized stack:
  Now, we will add one more choice to how we'll implement our stack. We want to be able to decide the maximum size of the stack at run-time (not compile-time).
  Thus, we cannot use a regular array, but must use a pointer to a dynamically-allocated array.
  Now, will we need to keep track of any more information besides the contents and top?
  Answer: Yes! We'll need to keep the size of this array, i.e., the maximum size of the stack. We'll see why this is necessary as we write the code.
7. C++ code:
  Now, let's think about how to actually code 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 stack.cpp.
  Now, there are 2 main parts to a C data structure: the data types needed to keep track of a stack and the functions needed to implement stack operations.
  1. The main data type we need is a type that people can use to declare new stacks, as in:
```
type-of-a-stack s1, s2;
```
  2. Some of the functions we'll need come directly from the operations needed for an abstract stack, like:
```
s1.push('A');
s2.pop();
```
    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. Remember that we need to put the class definition with data members and member function prototypes in stack.h and put the member function definitions (bodies) in stack.cpp.
  Before we ponder the details of the stack functions, we should decide on the types we need...
8. Data types for a stack:
  
  For the array implementation, we need to keep track of (at least) the array contents and a top index. What could be the data members for the class definition for a new data type Stack?
  So, our stack types become:
```
typedef char StackElementT;  /* Give it a generic name--makes  */
                             /* changing the type of things in */
                             /* the stack easy.                */

class Stack{
public:
  ...

private:
  StackElementT *contents;
  int top;
  /* Other fields? */
};
```
  Note that the contents is a pointer since it will be dynamically-allocated.
  Are any other fields needed? Well, remember that the maximum size of the array is determined at run-time...We'll probably need to keep that value around so that we can tell when the stack is full... The final type, thus, is:
```
class Stack {
  ...

private:
  StackElementT *contents;
  int top;
  int maxSize;
};
```
  These types should go in the interface, stack.h. Now that we've decided on the data types for a stack, let's think about the functions we need...
9. Filling in stack functions:
  
  First, we need a constructor and a destructor:
```
Stack()
~Stack()
```
  Next, we need the standard stack operations:
```
push()
pop()
isEmpty()
```
  Finally, while the array that holds the contents of the stack will be dynamically-allocated, it still has a maximum size. So, this stack is unlike the abstract stack in that it can get full. We should add something to be able to test for this state:
```
isFull()
```
10. Constructor
  
  When we instantiate a Stack object, it will need to set up the object so that it represents an empty stack.
  Here is what the prototype for the constructor looks like...
```
Stack(int maxSz);
```
  It needs to know what the maximum size of the stack will be (i.e., maxSz).
  Now, the body of the constructor must:
  1. Allocate space for the contents.
  2. Store the maximum size (for checking fullness).
  3. Set up the top.
    Here is the full definition:
```
Stack::Stack(int maxSz)
{
  /* Allocate a new array to hold the contents. */

  contents = new StackElementT[maxSz];

  if (contents == NULL) {
    cout << "Insufficient memory to initialize stack.\n";
    exit(1);  /* Exit, returning error code. */
  }

  maxSize = maxSz;
  top = -1;  /* I.e., empty */
}
```
    Note how we make sure that space was allocated (by testing the pointer against NULL).
    
    The constructor will be called when people create Stack objects. For example, when someone need stacks, they can declare stack variables:
```
Stack s1(10), s2(20);
```
  4. Destructor
    When we are done with a Stack object, the object should get rid of any dynamically-allocated memory and set itself to some reasonable state.
    The destructor will do that:
```
Stack::~Stack()
{
  /* Get rid of array. */
  delete [] contents;

  contents = NULL;
  maxSize = 0;
  top = -1;  /* I.e., empty */
}
```
    Remember that the destructor is automatically called when a Stack object goes out of scope (or when a dynamically-allocated stack is deleted).
  5. isEmpty() and isFull():
    Let's look at the functions that determine emptiness and fullness.
    Their prototypes are:
```
bool isEmpty() const;
bool isFull() const;
```
    Emptiness
    Testing for emptyness is an easy operation. We've said that the top field is -1 when the stack is empty. Here's a simple implementation of the function...
```
bool Stack::isEmpty() const
{
  return top < 0;
}
```
    Fullness
    Testing for fullness is only slightly more complicated. Let's look at an example stack.
    Suppose we asked for a stack with a maximum size of 1 and it currently contained 1 element (i.e., it was full)...
```
stack (made up of 'contents' and 'top')
-----    -----
| A |    | 0 |
-----    -----
  0       top
contents
```
    We can see from this example that when the top is equal to the maximum size minus 1 (e.g., 0 = 1 - 1), then it is full.
    You can write the full-ness function.
  6. push():
    Pushing onto the stack requires something to push. So, its prototype looks like:
```
void push(StackElementT element);
```
    The function should place an element at the correct position in the contents array and update the top. However, before the element is placed in the array, we should make sure the array is not already full...Here is the body of the function:
```
void Stack::push(StackElementT element)
{
  if (isFull()) {
    cout << "Can't push element on stack: stack is full.\n";
    exit(1);  /* Exit, returning error code. */
  }

  /* Put information in array; update top. */

  contents[++top] = element;
}
```
    Note how we used the prefix ++ operator. It increments the top index before it is used as an index in the array (i.e., where to place the new element).
    Also note how we just reuse the isFull() function to test for fullness.
  7. pop():
    Finally, popping from a stack does not require any parameter, but the value popped is typically returned. So, its prototype looks like:
```
StackElementT pop();
```
    The function should return the element at the top and update the top. Again, before an element is removed, we should make sure the array is not empty.
    You can write the pop() function.
  8. Stack module:
    Finally, The stack class definition with data members and function prototypes should go in stack.h. The member function definitions should go in stack.cpp.
    People that need to use the stack must include stack.h and link their code with stack.cpp (really, link their code with its object file, stack.o).
  9. Exercise:
    We've written much of the stack module (stack.h and stack.cpp) for you.
    Implement the pop() and isFull() member functions.
    Test the complete stack code with the sample main program stacktest.cpp. Compile and run the program. If you have time, add more member function calls for the stack in the main function.
  BU CAS CS - Stack - Array Implementation
  This page created by Jisook Youn <jisook@cs.bu.edu>.
  Material adapted for C++ from Stack - Array Implementation (C version by Robert I. Pitts <rip@bu.edu>).

Stack - Array Implementation

Abstraction

Example

Emptiness

Fullness