What is a stack?

The best example that anyone can give for a stack is certainly this; picture that you are at your favorite all you can eat buffet (mmmmmm....). It is time to choose a plate for the salad (well ham) bar and you notice there are none. So the busboy comes to the rescue.

He then places a "stack" of dishes on the holder. Notice what you do next. You take the plate that is at the top. You do not take the plate all the way at the bottom! You would be a fool to do that.

So in truth, the first dinner plate on the stack will be the last dinner plate off the stack. Conversely, the last dinner plate on the stack will be the first off the stack. The acronymn we use is LIFO (Last In First Out). This is the same with all stacks.

So as an example below, we have the following stack. The top most item is the only one available and is the last in. The bottom most item is the first in and not accessible.

5. Apples  <--
4. Oranges
3. Pears
2. Mangos
1. Peaches

Stacks and Arrays

In many ways, an array can be seen as a stack. The index zero will be the first element in the stack and the most recent index will be the last in. You use a 1-D array for the stack.

So look at the example below. We will use a 1D array of characters to represent a stack.

Index 0 will be the bottom of the stack while
Index 9 (so far) will be the top of the stack.

 0   1   2   3   4   5   6   7   8   9
'a'|'b'|'c'|'d'|'e'|'f'|'g'|'h'|'i'|'j'


The above array will look like:

'j'  <-- TOP
'i'
'h'
'g'
'f'
'e'
'd'
'c'
'b'
'a'  <-- BOTTOM

Putting it together

Here is the stack class now. An explination will certainly follow.

template< class T >
class Stack {

private:
   int MAX;
   int top;
   T* items;

public:
	Stack(int size){
		MAX = size;
		top = -1;
		items = new T[MAX];
	}

	~Stack(){ delete [] items; }

	void push(T c){
		if(full()){
			cout << "Stack Full!" << endl;
			exit(1);
		}

		items[++top] = c;
	}

	T pop(){
		if(empty()){
			cout << "Stack Empty!" << endl;
			exit(1);
		}

		return items[top--];
	}

	int empty(){ return top == -1; }

	int full(){ return top+1 == MAX; }
};

Wow! A complete stack in just a short program. Here is the breakdown.

In the private section, we have 3 variables. The variable MAX will be the size of the stack and in turn the size of the array. The variable top will be the index of the array that will act as the top of the stack. The variable items will be the dynamically declared array of the type T (from the template).

The public section contains the rest of the functions needed for the stack. First, the constructor. This will take the needed size of the stack as the parameter and set MAX equal to that. Then, set the top equal to -1 since you have not added data yet, and allocate the array of type T of the size.

The destructor will delete the dynamic array. This is needed as you will have a memory leak if you do not do this.

The function push() will add the data to the stack. It first checks if the stack is full() and if so, no more data can be added so the program exits. If it is not full, it places the data in the array.

The function pop() will return the data to you and decrement the counter. It first checks if the stack is empty by calling the empty() function. It then returns the data.

Below is an example that will contain a main function to add and remove data from a stack.

#include <iostream>
using namespace std;

template< class T >
class Stack {

private:
   int MAX;
   int top;
   T* items;

public:
	Stack(int size){
		MAX = size;
		top = -1;
		items = new T[MAX];
	}

	~Stack(){ delete [] items; }

	void push(T c){
		if(full()){
			cout << "Stack Full!" << endl;
			exit(1);
		}

		items[++top] = c;
	}

	T pop(){
		if(empty()){
			cout << "Stack Empty!" << endl;
			exit(1);
		}

		return items[top--];
	}

	int empty(){ return top == -1; }

	int full(){ return top+1 == MAX; }
};

int main(){

	Stack<char> st(10);

        //the letters 'A' - 'J'
	for(int i = 65; i < 75; i++)
		st.push(i);

        //remove all the data
	for(int j = 0; j < 10; j++)
		cout << st.pop() << endl;

	return 0;
}

J
I
H
G
F
E
D
C
B
A