栈的结构很简单,没啥说的,分别使用数组和链表两种方法实现栈
/*--------数组实现的栈--------------------------*/
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;
}
}
Comments NOTHING