数据结构C++,栈的实现

#include <iostream>
#include <cstdlib>

template<class T>
void changeLength1D(T*& a, int oldLength, int newLength) {
  if(newLength<0) {
    std::cout<<"new length must be >=0\n";
    exit(-1);
  }

  T* temp=new T[newLength];
  int number=std::min(oldLength,newLength);
  std::copy(a,a+number,temp);
  delete [] a;
  a=temp;
}

template<class T>
class stack {
public:
  virtual ~stack() {}
  virtual bool empty() const=0;
  virtual int size() const=0;
  virtual T& top()=0;
  virtual void pop()=0;
  virtual void push(const T& theElement)=0;
};

template<class T>
class arrayStack:public stack<T> {
public:
  arrayStack(int initialCapacity=10);
  ~arrayStack() {delete [] stack;}
  bool empty() const {return stackTop==-1;}
  int size() const {return stackTop + 1;}
  T& top() {
    if(stackTop==-1) {
      std::cout<<"stack is empty\n";
      exit(-1);
    }
    return stack[stackTop];
  }
  void pop() {
    if(stackTop == -1) {
      std::cout<<"stack is empty\n";
      exit(-1);
    }
    stack[stackTop--].~T();
  }
  void push(const T& theElement);

private:
  int stackTop;
  int arrayLength;
  T* stack;
};

template<class T>
arrayStack<T>::arrayStack(int initialCapacity) {
  if(initialCapacity < 1) {
    std::cout<<"Must be > 0.\n";
    exit(-1);
  }
  arrayLength=initialCapacity;
  stack=new T[arrayLength];
  stackTop=-1;
}

template<class T>
void arrayStack<T>::push(const T& theElement) {
  if(stackTop == arrayLength-1) {
    changeLength1D(stack, arrayLength, 2*arrayLength);
    arrayLength *= 2;
  }
  stack[++stackTop] = theElement;
}

int main() {
  arrayStack<int> my_stack(20);

  for(size_t i=0; i<10; i++) {
    my_stack.push(i);
  }

  for(;;) {
    if(my_stack.empty())
      break;
    std::cout<<my_stack.top()<<" ";
    my_stack.pop();
  }
  std::cout<<"\n";

  return 0;
}

原文地址:https://www.cnblogs.com/donggongdechen/p/8858886.html