数据结构 栈

栈：仅限尾部插入或删除的线性表

表尾：栈顶

表头：栈底

特性：后进先出

结构为：

template
class stack
{
public:
    stack();//初始化
    ~stack();//析构
    void push(T x);//插入元素
    void pop();//删除元素
    T top(); //查看栈顶元素
    int size();//元素个数
    bool empty();//判空
private:
    int _size; //计算数据数量
    T *p;  //创建一个指针
};

#include
#include
using namespace std;
const int MAX_size = 500;
template 
class stack
{
public:
	stack();//初始化
	~stack();//析构
	void push(T x);//插入元素
	void pop();//删除元素
	T top(); //查看栈顶元素
	int size();//元素个数
	bool empty();//判空
private:
	int _size; //计算数据数量
	T *p;  //创建一个指针
};

 //初始化
template 
stack::stack() {   
	_size = 0; //个数为0
	p = new T[MAX_size];//开辟500个空间
}

//析构
template 
stack::~stack() {
	if (p != nullptr)//当p不为空指针时释放内存，并把p变为空指针
	{
        delete[]p;
        p = nullptr;
	}
	
}

//插入数据
template 
void stack::push(T x)
{
	if (_size == MAX_size)//容量不足 退出
	{
		exit(1);
	}
	p[_size]=x;//容量未满，插入数据
	_size++;
}
//查看栈顶元素
template 
T stack::top()
{
	if (_size == 0)//没有元素的话 返回0
	{
		 exit(1);
	}
	return p[_size-1];///返回栈顶数据
}
//删除元素
template 
void stack::pop()
{
	if (_size == 0)
	{
		exit(1)
	}
	_size--;//元素个数减一
}

//返回元素个数
template 
int stack::size()
{
	return _size;//返会元素个数
}

//判空
template 
bool stack::empty()
{
	if (_size == 0)
	{
		return true;
	}
	return false;
}

int main()
{
	stack P;
	P.push(5);
	cout << P.top() << endl;
	system("pause");
	return 0;
}

push的实现：

1. 先生成一个新结点
2. 用新结点的指针指向 top节点
3. top指针指向新节点

 pop的实现：

1. 先生成一个新节点指向top的内部节点
2. 删除top节点
3. top指向新节点

#include
using namespace std;


template//让栈元素节点类提前知道有栈
class Stack;

//定义一个栈元素节点类
template
class StackNode
{
	friend class Stack;//声明栈类为节点类的友元，以便访问其私有数据
public:
	StackNode() {};
	StackNode(T _data) :data(_data), base(nullptr) {};
	~StackNode() {};
private:
	T data;
	StackNode* base;
};
//栈
template
class Stack
{
public:
	Stack();
	~Stack();
	void Push(const T p);//插入元素
	void Pop();//删除元素
	T Top();//返回栈顶元素
	bool Empty();//判空
	int Size();//元素个数
private:
	int size;
	StackNode* top;
};
//初始化
template
Stack::Stack()
{
	size = 0;//初始个数为0
	top = nullptr;//把头指针设为空指针
}
//析构函数
template
Stack::~Stack()
{
	while (!Empty())//不为空就一直删除栈顶元素
	{
		Pop();
	}
}
//插入数据
template
void Stack::Push(const T p)
{
	StackNode* P = new StackNode(p);
	P->base = top;//p的base指向 top
	top = P;//top指向P节点
	size++;//节点数加一
}
//删除数据
template
void Stack::Pop()
{
	if (size == 0)//个数为0，结束
	{
		exit(1);
	}
	StackNode* P = top->base;//新建一个指针指向top内部节点（下一个节点）
	delete top;//释放top的内存
	top = P;//top指向栈顶下一个节点
	size--;//个数减一
}
//查看数据
template
T Stack::Top()
{
	if (size == 0)//为空，结束
	{
		exit(1);
	}
	return top->data;//不为空，返回数据
}
//返回个数
template
int Stack::Size()
{
	return size;
}
//判空
template
bool Stack::Empty()
{
	if (size == 0)
	{
		return true;
	}
	return false;
}
int main()
{
	Stackm;
	m.Push(6);
	cout< 
栈输入表达式的情况：