A Simple Array-Based Stack Implementation
//---------------------------------------------------------
// A stack class.
//
// D. Searls
// Jan 2008
//---------------------------------------------------------
#ifndef H_STACKCLASS
#define H_STACKCLASS
#include<cstdlib>
#include<iostream>
using namespace std;
template<class itemType>
class stack
{
private:
itemType* arr;
int n;
int capacity;
//-----------------------------------------------------
// createStack
//
// Allocate memory for a new, empty stack.
//-----------------------------------------------------
void createStack()
{
try
{
arr = new itemType[capacity];
n = 0;
}
catch (bad_alloc bae)
{
cout << "Memory Allocation Failure! Program Terminated";
cout << endl << endl;
exit(0);
}
}
public:
//-----------------------------------------------------
// Default Constructor
//
// Construct an empty stack of size 100.
//-----------------------------------------------------
stack()
{
capacity = 100;
createStack();
}
//-----------------------------------------------------
// Initialization Constructor
//
// Construct an empty stack of the specified size.
//
// In Parameter: size
//-----------------------------------------------------
stack(int size)
{
capacity = size;
createStack();
}
//-----------------------------------------------------
// Destructor
//
// Remove all of the items from the stack
//-----------------------------------------------------
~stack()
{
delete [] arr;
}
//-----------------------------------------------------
// push
//
// Push the specified item onto the top of the stack.
//
// Precondition: full() is false.
//
// Postconditions: size() will be incremented by 1 and
// item will be at the top of the stack.
//
// In Parameter: item
//-----------------------------------------------------
void push(const itemType& item)
{
if (n < capacity)
{
arr[n] = item;
n++;
}
}
//-----------------------------------------------------
// pop
//
// Remove and discard the item on the top of the stack.
//
// Precondition: empty() is false.
//
// Postcondition: size() will be decremented by 1.
//-----------------------------------------------------
void pop()
{
if (n > 0)
{
n--;
}
}
//-----------------------------------------------------
// size
//
// Return the number of items in the stack.
//-----------------------------------------------------
int size()
{
return n;
}
//-----------------------------------------------------
// empty
//
// Return true if the stack is empty and false
// otherwise.
//-----------------------------------------------------
bool empty()
{
return (n == 0);
}
//-----------------------------------------------------
// full
//
// Return true if the stack is full and false
// otherwise.
//-----------------------------------------------------
bool full()
{
return (n == capacity);
}
//-----------------------------------------------------
// top
//
// Return a mutable reference to the item on the top of
// the stack.
//
// Precondition: empty() is false.
//-----------------------------------------------------
itemType& top()
{
return arr[n-1];
}
};
#endif
Some Examples of Using a Stack
//-----------------------------------------------
// StackDemos
//
// The primary purpose of this demo is to
// illustrate how a stack can be used instead of
// recursion.
//
// D. Searls
// Asbury University
// 01/2012
//-----------------------------------------------
#include "ArrayBasedStack1.cpp"
#include<iostream>
#include<iomanip>
using namespace std;
//-----------------------------------------------
// power
//
// Return the value of base raised to the
// specified non-negative integer exponent.
//
// In parameters: base, exponent
//-----------------------------------------------
double power(double base, int exponent)
{
stack<double> dStack;
double result;
while (exponent > 0)
{
dStack.push(base);
exponent--;
}
result = 1.0;
while (!dStack.empty())
{
result = result * dStack.top();
dStack.pop();
}
return result;
}
//-----------------------------------------------
// product
//
// Return the product of the specified integer
// values a and b.
//
// In parameters: a, b
//-----------------------------------------------
int product(int a, int b)
{
stack<int> iStack;
int result;
bool isNegative;
isNegative = (b < 0);
if (isNegative)
{
b = -b;
}
while (b > 0)
{
iStack.push(a);
b--;
}
result = 0;
while (!iStack.empty())
{
result = result + iStack.top();
iStack.pop();
}
if (isNegative)
{
result = -result;
}
return result;
}
//-----------------------------------------------
// outputInBinary
//
// Output the specified non-negative integer as
// an numdigit binary number.
//
// In Parameter: n
//-----------------------------------------------
void outputInBinary(int n, int numDigit)
{
stack<char> chStack;
char bit;
do
{
bit = char(int('0') + n % 2);
chStack.push(bit);
n = n / 2;
} while (n > 0);
for (int places = numDigit; places > chStack.size(); places--)
{
cout << '0';
}
while (!chStack.empty())
{
cout << chStack.top();
chStack.pop();
}
}
//***********************************************
// M A I N D R I V E R
//***********************************************
int main()
{
for (int i = 0; i < 10; i++)
{
cout << setw(8) << power(2.0, i) << endl;
}
cout << endl;
for (int i = -5; i <= 5; i++)
{
cout << setw(8) << product (2, i) << endl;
}
cout <<endl;
for (int i = 0; i <=16; i++)
{
outputInBinary(i,8);
cout << endl;
}
cout << endl;
return 0;
}
