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; }