数据结构（5）栈

栈的结构很简单，没啥说的，分别使用数组和链表两种方法实现栈

/*--------数组实现的栈--------------------------*/
template<class T>
class arrayStack {
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)//判断是否为空
			cout << "空栈" << endl;
		return stack[stackTop];
	}
	void pop() {//删除顶部元素
		if( stackTop == -1)
			cout << "空栈" << endl;
		stack[stackTop--].~T();
	}
	void push(const T& theElement);
private:
	int stackTop;//顶部元素的序号，从-1开始，-1为空
	int arrayLength;
	T* stack;
};

template<class T>
arrayStack<T>::arrayStack(int initialCapacity) {
	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);//数组变长函数在数据结构(1)
		arrayLength *= 2;
	}
	stack[++stackTop] = theElement;
}


/*---------链表实现的栈---------------------*/
//定义节点，详见数据结构(2)
template<class T>
struct chainNode {
	T element;
	chainNode<T>* next;

	chainNode() {}
	chainNode(const T& element) {
		this->element = element;
	}
	chainNode(const T& element, chainNode<T>* next) {
		this->element = element;
		this->next = next;
	}
};

template<class T>
class linkedStack {
public:
	linkedStack(int initialCapacity = 10) {//构造函数
		stackTop = NULL;
		stackSize = 0;
	}
	~linkedStack();
	bool empty() const {//判断是否为空
		return stackSize == 0;
	}
	T& top() {//返回栈顶元素
		if (stackSize == 0) {
			cout << "空栈" << endl;
		}
		return stackTop->element;
	}
	void pop();
	void push(const T& theElement) {//进栈
		stackTop = new chainNode<T>(theElement, stackTop);
		stackSize++;
	}
private:
	chainNode<T>* stackTop;
	int stackSize;
};

template<class T>
void linkedStack<T>::pop() {//删除栈顶元素
	if (stackSize == 0) {
		cout << "空栈" << endl;
	}
	chainNode<T>* nextNode = stackTop->next;
	delete stackTop;
	stackTop = nextNode;
	stackSize--;
}

template<class T>
linkedStack<T>::~linkedStack() {//析构函数，删除所有节点
	while (stackTop!=NULL)
	{
		chainNode<T>* nextNode = stackTop->next;
		delete stackTop;
		stackTop = nextNode;
	}
}