概念
- 栈是一个==有序表==，它的插入操作（入栈）和删除操作（出栈）都只能在列表的==一个端点==（栈顶）进行。
系统栈*
- 用来处理程序运行时的函数调用；
- 当一个函数被调用时，程序会生成一个被称为==活动记录==或==栈框架==的结构，并把这个程序放在系统的栈顶，当函数中调用其他函数时运行过程如下图：
定义ADT
template<class T>
class Stack
{
public:
//创建空栈的容量
Stack(int stackCapacity = 10);
//检测栈是否为空
bool isEmpty()const;
//返回最上面的元素
T& Top()const;
//增加栈的容量
void ChangeCapacitySize(int size);
//添加元素
void Push(const T& item);
//删除最上面的元素
void Pop();
private:
//存储数组
T* stack;
//顶部指针
int top;
//栈容量
int capactity;
};
容量拓展
- 我们应该注意在添加时栈容量是否足够，在容量不够时，增加栈容量，添加容量函数如下：
template<class T>
void Stack<T>::ChangeCapacitySize(int size)
{
if (size <= capactity)throw"只能增加容量！";
T* temp = new T[size];
if (capactity > 0)
{
copy(stack, stack + capactity, temp);
delete[]stack;
}
stack = temp;
capactity = size;
}
添加元素
template<class T>
void Stack<T>::Push(const T& item)
{
if (top == capactity - 1)
{
ChangeCapacitySize(capactity + 1);
}
stack[++top] = item;
}
删除元素
- 因为元素类型为class类，所以我们删除某个元素我们可以直接调用T的析构函数
T::~T()//析构函数
代码如下：
template<class T>
void Stack<T>::Pop()
{
if (isEmpy())throw"栈为空，不可删除！";
stack[top--].~T();
}
代码总览
#include<iostream>
using namespace std;
template<class T>
class Stack
{
public:
//创建空栈的容量
Stack(int stackCapacity = 10);
//检测栈是否为空
bool isEmpty()const;
//返回最上面的元素
T& Top()const;
//增加栈的容量
void ChangeCapacitySize(int size);
//添加元素
void Push(const T& item);
//删除最上面的元素
void Pop();
private:
//存储数组
T* stack;
//顶部指针
int top;
//栈容量
int capactity;
};
template<class T>
Stack<T>::Stack(int stackCapacity)
{
if (stackCapacity < 1)throw"定义容量必须大于1！";
capactity = stackCapacity;
stack = new T[capactity];
top = -1;
}
template<class T>
bool Stack<T>::isEmpty() const
{
return top==-1;
}
template<class T>
T& Stack<T>::Top() const
{
if (top == -1)throw"栈为空！";
return stack[top];
}
template<class T>
void Stack<T>::ChangeCapacitySize(int size)
{
if (size <= capactity)throw"只能增加容量！";
T* temp = new T[size];
if (capactity > 0)
{
copy(stack, stack + capactity, temp);
delete[]stack;
}
stack = temp;
capactity = size;
}
template<class T>
void Stack<T>::Push(const T& item)
{
if (top == capactity - 1)
{
ChangeCapacitySize(capactity + 1);
}
stack[++top] = item;
}
template<class T>
void Stack<T>::Pop()
{
if (isEmpy())throw"栈为空，不可删除！";
stack[top--].~T();
}
