The stack class

[code lang=c++] #ifndef _CP_STACK_INCLUDED_ #define _CP_STACK_INCLUDED_

#include #include //#pragma once

namespace CP {

template class stack { protected: T *mData; size_t mCap; size_t mSize;

void expand(size_t capacity) {
  T *arr = new T[capacity]();
  for (size_t i = 0;i < mSize;i++) {
    arr[i] = mData[i];
  }
  delete [] mData;
  mData = arr;
  mCap = capacity;
}

void ensureCapacity(size_t capacity) {
  if (capacity > mCap) {
    size_t s = (capacity > 2*mCap) ? capacity : 2*mCap;
    expand(s);
  }
}

public: //-------------- constructor ----------

// copy constructor
stack(const stack<T>& a) {
  this->mData = new T[a.mCap]();
  this->mCap = a.mCap;
  this->mSize = a.size();
  for (size_t i = 0;i < a.size();i++) {
    mData[i] = a.mData[i];
  }
}

// default constructor
stack() {
  int cap = 1;
  mData = new T[cap]();
  mCap = cap;
  mSize = 0;
}

// copy assignment operator
stack<T>& operator=(stack<T> &other) {
  using std::swap;
  swap(mSize,other.mSize);
  swap(mCap,other.mCap);
  swap(mData,other.mData);
  return *this;
}

~stack() {
  delete [] mData;
}

//------------- capacity function -------------------
bool empty() const {
  return mSize == 0;
}

size_t size() const {
  return mSize;
}

//----------------- access -----------------
const T& top() {
  if (size() == 0) throw std::out_of_range("index of out range") ;
  return mData[mSize-1];
}

//----------------- modifier -------------
void push(const T& element) {
  ensureCapacity(mSize+1);
  mData[mSize] = element;
  mSize++;
}

void pop() {
  if (size() == 0) throw std::out_of_range("index of out range") ;
  mSize--;
}

};

}

#endif [/code]

The stack_by_vector class

[code lang=c++] #ifndef _CP_STACK_INCLUDED_ #define _CP_STACK_INCLUDED_

#include #include #include //#pragma once

namespace CP {

template class stack { protected: std::vector v;

public: //-------------- constructor ----------

// copy constructor
stack(const stack<T>& a) {
  v = a.v;
}

// default constructor
stack() { }

~stack() { }

//------------- capacity function -------------------
bool empty() {
  return v.empty();
}

size_t size() {
  return v.size();
}

//----------------- access -----------------
const T& top() {
  if (v.size() == 0) throw std::out_of_range("index of out range") ;
  return v[v.size()-1];
}


//----------------- modifier -------------
void push(const T& element) {
  v.push_back(element);
}

void pop() {
  if (v.size() == 0) throw std::out_of_range("index of out range") ;
  v.pop_back();
  //v.erase(v.begin()+v.size()-1);
}

};

}

#endif [/code]

The testing unit

[code lang=c++] #include #include #include "stack.h" #include #include

//typedef CP::stack Stack; // typedef CP::stack Stack;

bool test1() { Stack s; assert(s.size() == 0);

s.push(1); s.push(2); s.push(3); s.push(3);

assert(s.top() == 3 && s.size() == 4); s.pop(); assert(s.top() == 3 && s.size() == 3); s.pop(); assert(s.top() == 2 && s.size() == 2); s.pop(); assert(s.top() == 1 && s.size() == 1); s.pop();

assert(s.size() == 0);

return true; }

bool test2() { Stack s; s.push(1); s.push(1); s.push(1); s.pop(); s.pop(); s.pop();

Stack s2 = s;

try { int x = s.top(); std::cout << "x = " << x << std::endl; s.pop(); } catch (std::exception &e) { std::cout << "Caught an exception " << e.what() << std::endl; return true; } return false; }

bool test3() { int nRun = 20; int nData = 1000000; for (int i = 0;i < nRun;i++) { Stack s; for (int j = 0;j < nData;j++) { s.push(j); } for (int j = 0;j < nData;j++) { s.pop(); } } return true; }

int main() { if (test1()) std::cout << "---------------------------------------- Test1 OK!" << std::endl; if (test2()) std::cout << "---------------------------------------- Test2 OK!" << std::endl; if (test3()) std::cout << "---------------------------------------- Test3 OK!" << std::endl;

return 0; } [/code]