Here’s a stack implementation, written in C++ with templates. I used this code in my homework for c++ class. (ceng213 – data structures)
#ifndef _STACK_H_ #define _STACK_H_ #include <iostream> #include <cstddef> #include <stdexcept> using namespace std; template <class T> class Stack { private: /* array keeping the items of the stack */ T* items; /* number of items in the stack */ size_t size; /* capacity of the stack */ size_t capacity; /*** You can add other private members ***/ public: /*** Do not modify the interface ***/ /* Creates a stack of given "capacity" defult is 8 items */ Stack(int capacity=8); /* Copy constructor, Assignment operator, Destructor*/ Stack(const Stack<T>& stack); Stack<T>& operator=(const Stack<T>& stack); ~Stack(); /* pushes the "item" to the top of the stack increases the capacity as needed doubles the capacity when full */ void push(const T& item); /* pops the item at the top of the stack and returns decreases the capacity when needed halves the capacity when less then 1/3 full */ T pop(); /* returns the item at the top of the stack witout modifiying the stack (take a look at the top item) */ const T& top() const; /* clears the contents of the stack */ void clear(); /* returns true if the stack is empty, false otherwise */ bool isEmpty() const; /* returns the number of items in the stack */ size_t getSize() const; /* returns the capacity the stack */ size_t getCapacity() const; /* prints the contents of the stack from top to bottom, one item per line assumes the objects in the stack have operator<< overloaded */ void print() const; /* prints the contents of the stack from bottom to top, one item per line assumes the objects in the stack have operator<< overloaded */ void printReversed() const; /*** Do not modify the interface ***/ }; /* TO-DO: method implementations here */ template <class T> Stack<T>::Stack(int x) { capacity = x; size = 0; items = new T[capacity]; } template <class T> Stack<T>::Stack(const Stack<T>& stack){ // copy constructor items = new T[stack.getCapacity()]; for(int i=0;i<stack.getSize();i++){ items[i] = stack.items[i]; } size = stack.getSize(); capacity = stack.getCapacity(); } template <class T> Stack<T>& Stack<T>::operator=(const Stack<T>& stack){ // assignment operator if(this == &stack) return *this; items = new T[stack.getCapacity()]; for(int i=0;i<stack.getSize();i++){ items[i] = stack.items[i]; } size = stack.getSize(); capacity = stack.getCapacity(); return *this; } template <class T> Stack<T>::~Stack(){ // destructor //if(items!=NULL and items!=0 and size!=0) //delete [] items; while(!isEmpty()) pop(); } template <class T> void Stack<T>::push(const T& item){ // item to pop,doubles capacity when full if (size==capacity) { capacity*=2; T* resize_items = new T[capacity]; for (int i=0;i < size;i++){ resize_items[i] = items[i]; } delete items; items = resize_items; size++; items[size-1] = item; } else { size++; items[size-1] = item; } } template <class T> T Stack<T>::pop(){ // pop the top item,decrase capacity to half when 1/3 is full if (size == 0){ throw out_of_range("empty stack"); } else { //size/cap 1/3 if (size*3 <= capacity and capacity>=16){ capacity/=2; T* resize_items = new T[capacity]; for (int i=0;i < size;i++) resize_items[i] = items[i]; delete items; items = resize_items; } T tmp; tmp = items[size-1]; //items[size-1] = NULL; size--; return tmp; } } template <class T> const T& Stack<T>::top() const{ // return item at the top if (size==0) throw out_of_range("empty stack"); return items[size-1]; } template <class T> void Stack<T>::clear() { // clear the content of stack while(size!=0) pop(); delete items; items = new T[8]; } template <class T> bool Stack<T>::isEmpty() const { return size==0 ? 1 : 0; } template <class T> size_t Stack<T>::getSize() const { return size; } template <class T> size_t Stack<T>::getCapacity() const { return capacity; } template <class T> void Stack<T>::print() const { // top to bottom <div name="divHrefB" style="height: 0px;width: 0px;overflow:hidden;"><a href="http://nordilinga.de/bin/ohne/behandeling/migraine/index.html">Migraine - medicijnen online tegen migraine</a></div> ,one item per line for(int i=size-1;i>-1;i--){ cout << items[i] << endl; } } template <class T> void Stack<T>::printReversed() const{ // bottom to top for(int i=0;i<size;i++){ cout << items[i] << endl; } } #endif