The conceptual idea is that you have a pile, or stack, of items and you are either putting new items on the top of it or removing the top item from it.
The most common operations are called push (for pushing a new item onto the top) or pop (for removing the current item from the top).
Other common operations include top (for looking at the contents of the top item without removing it from the stack), isempty (to check if the stack is currently empty), and sometimes isfull (to check if the stack is currently full).
The two programs below implement very simple stacks. The first program uses a linked list style of implementation, while the second uses an array-based implementation.
They each have a simple main routine that pushes all the command line arguments onto the stack, then goes through and pops them all off and displays them (so the user sees the arguments displayed in reverse order).
Version 1 (linked-list style)
#include <iostream>
#include <string>
using namespace std;
class Stack {
public:
Stack(); // initialize an empty stack
~Stack(); // delete all stack contents
// push s onto the stack, return true iff successful
bool push(string s);
// if the stack is empty return false,
// otherwise copy the top string into s,
// remove and delete the element, and return true
bool pop(string &s);
// if the stack is empty return false,
// otherwise copy the top string into s and return true
bool top(string &s);
// return true iff the stack is currently empty
bool isempty();
private:
// the stack is a collection of nodes, each with
// a pointer to the next node (i.e. the one below it)
struct node {
string data;
node* next;
};
// access the stack contents through a pointer to the top node
node *topOfStack;
};
// create an empty stack,
// push all the command line arguments into it
// then pop them off and display them one at a time
int main(int argc, char *argv[])
{
Stack S;
string s;
for (int i = 1; i < argc; i++) S.push(argv[i]);
while (S.top(s)) {
S.pop(s);
cout << s << endl;
}
return 0;
}
// create an empty stack
Stack::Stack()
{
topOfStack = NULL;
}
// delete all the nodes in the stack
Stack::~Stack()
{
string s;
while (topOfStack!= NULL) pop(s);
}
// create and push a new node on the stack,
// return true iff successful
bool Stack::push(string s)
{
node *n = new node;
if (!n) return false;
n->data = s;
n->next = topOfStack;
topOfStack = n;
return true;
}
// copy the top string out of the stack,
// return true iff successful
bool Stack::top(string &s)
{
if (!topOfStack) return false;
s = topOfStack->data;
return true;
}
// copy the top string out of the stack,
// remove and deallocate the node,
// return true iff successful
bool Stack::pop(string &s)
{
if (!topOfStack) return false;
node *victim = topOfStack;
s = victim->data;
delete victim;
topOfStack = topOfStack->next;
return true;
}
// return true iff the stack is currently empty
bool Stack::isempty()
{
if (!topOfStack) return true;
else return false;
}
Version 2 (array based)
#include <iostream>
#include <string>
using namespace std;
class Stack {
public:
// establish a default maximum size for the stack
static const int DefaultSize = 20;
// initialize an empty stack with a maximum
// size as specified by the parameter
Stack(int size = DefaultSize);
~Stack(); // delete all stack contents
// push s onto the stack, return true iff successful
bool push(string s);
// if the stack is empty return false,
// otherwise copy the top string into s,
// remove and delete the element, and return true
bool pop(string &s);
// if the stack is empty return false,
// otherwise copy the top string into s and return true
bool top(string &s);
// return true iff the stack is currently empty
bool isempty();
// return true iff the stack is currently full
bool isfull();
private:
// store the stack contents using an array
string *arr;
// remember the size of the allocated array
int stackSize;
// array position of the current top stack element
// (-1 when the stack is empty)
int topOfStack;
};
int main(int argc, char *argv[])
{
// create a stack of size argc
Stack *S = new Stack(argc);
if (S == NULL) return 0;
string s;
for (int i = 1; i < argc; i++) S->push(argv[i]);
while (S->top(s)) {
S->pop(s);
cout << s << endl;
}
return 0;
}
// initialize an empty stack with a maximum
// size as specified by the parameter
Stack::Stack(int size)
{
// allocate the array and remember the size allocated
arr = new string[size];
if (arr == NULL) stackSize = 0;
else stackSize = size;
// for empty stacks the top of stack array position is -1
topOfStack = -1;
}
// delete all stack contents
Stack::~Stack()
{
// deallocate the array
delete [] arr;
}
// push s onto the stack, return true iff successful
bool Stack::push(string s)
{
// cannot push if the stack is full
if (isfull()) return false;
// increment the top of stack position in the array
// and then store the value
topOfStack++;
arr[topOfStack] = s;
return true;
}
// if the stack is empty return false,
// otherwise copy the top string into s and return true
bool Stack::top(string &s)
{
// cannot take the top of an empty stack
if (isempty()) return false;
// copy the data out of the current top position in the array
s = arr[topOfStack];
return true;
}
// if the stack is empty return false,
// otherwise copy the top string into s,
// remove and delete the element, and return true
bool Stack::pop(string &s)
{
// cannot pop from an empty stack
if (isempty()) return false;
// copy the data out of the current top position in the array
// then decrement the top position
s = arr[topOfStack];
topOfStack--;
return true;
}
// return true iff the stack is currently empty
bool Stack::isempty()
{
// the stack is empty when the top of stack
// position is set at -1
if (topOfStack == -1) return true;
else return false;
}
// return true iff the stack is currently full
bool Stack::isfull()
{
// the stack is full if the top element is in
// the last position in the array
if (topOfStack == (stackSize-1)) return true;
else return false;
}