自构建栈类（数组和链表双实现方式）

最近学习数据结构与算法，讲到链表和栈，为了满足自己的好奇心和小小的成就感还有巩固知识，便根据栈的特点和功能，自构建栈类（分别使用数组和链表实现)

在用链表实现时发现用结构体老是报错有问题，想到类本身就是结构体的演化，而且占据的内存是一样的，为什么要执着于用结构体呢，
带着想法度娘了一下，发现这篇博客就是用的类模板，所以验证了心里的想法用类来代替结构体，
因知单纯看书看别人的代码是不够的，自己敲出来的才是自己的，所以把自己写的代码分享出来，也方便以后查看回忆

/**
构建栈，并完善栈的各项操作，
1，判空
2，判断栈的长度，
3.插入，取出
4.栈顶的元素 
5.栈中的元素个数
*/

数组实现

/**
构建栈，并完善栈的各项操作，

1，判空
2，判断栈的长度，
3.插入，取出
4.栈顶的元素 
5.是否有最长度元素 


*/
#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
template<class T>
class mystack{
	private:
		
		int top;
	    int maxn;
		T *data;
	public:
		mystack(){
			top=-1;
			maxn=100;
			data=new T(maxn);
			memset(data,0,sizeof(data));
		}
		bool isEmpty(){
			return top==-1;
		}
		bool isFull(){
			return top==maxn-1;
		}
		bool push(T temp){
			if(top<maxn){
			//	cout<<"top="<<top<<endl;
				data[++top]=temp;
			//	cout<<"出入成功"<<data[top]<<"成功"<<endl;
				return true;
			}
			return false;
		}
		
		T pop(){
			T t=data[top];
			data[top]=0;
			top--;
			return t;
		}
		T gettop(){
		//	cout<<"gettop="<<data[top]<<endl;
			T t=data[top];
			return t;
		}
		~mystack(){
			delete data;
		}
};
int main(){
	mystack<int> s;
	cout<<s.isEmpty()<<endl;
	cout<<s.isFull()<<endl;
	
	int a=100;
	int b=200;
	s.push(a);
	cout<<"top1="<<s.gettop()<<endl;
	s.push(b);
	cout<<"top2="<<s.gettop()<<endl;
	cout<<"pop1="<<s.pop()<<endl;
	cout<<"isempty? "<<s.isEmpty()<<endl;
	cout<<"pop2="<<s.pop()<<endl;
	cout<<"isempty? "<<s.isEmpty()<<endl;
	return 0;
}

2.单向链表是实现：

#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
template<class T>
class Node{
private:
	T data;
	Node *pre;
public:
	Node(){}
	Node(T t,Node* _pre){
		data = t;
		pre = _pre;
	}

	T getData(){
		return data;
	}
	void setData(T t){
		data = t;
	}
	Node* getPre(){
		return pre;
	}
	void setPre(Node *_pre){
		pre = _pre;
	}
	~Node(){
//		cout<<"\n执行析构函数Node"<<endl;
	}

};



template<class T>
class mystack2{
private:
	Node<T>* top;
	Node<T>* Temp;
public:
	mystack2(){
		top = NULL;
		Temp = NULL;

	}
	bool isEmpty(){
		return top == NULL;
	}
	bool isFull(){
		return top != NULL;
	}
	bool push(T temp){
			Temp = new Node<T>(temp, NULL);
			if (top != NULL){
				Temp->setPre(top);
			}
			top = Temp;
			return true;
	}

	T pop(){
		T t = top->getData();

		Temp = top;
		top = top->getPre();
		delete Temp;

		return t;
	}
	T gettop(){
		T t = top->getData();
		return t;
	}
	~mystack2(){
	//	cout<<"delete->"<<top->getData();
	//	cout<<"\n执行析构函数mystack2"<<endl; 
			while (top)
			{
			//	cout<<"delete->"<<top->getData()<<endl;
				Temp = top;
				top = top->getPre();
		//		cout<<"delete->"<<top->getData();
				delete Temp;

			}

		


		if (Temp){

			delete Temp;
			Temp=NULL;
		}
		if (top){

				delete top;
				top=NULL;
		}
	}
};

int main(){
	mystack2<int> s;
	cout<<s.isEmpty()<<endl;
	cout<<s.isFull()<<endl;
	
	int a=100;
	int b=200;
	s.push(a);
	cout<<"top1="<<s.gettop()<<endl;
	s.push(b);
	cout<<"top2="<<s.gettop()<<endl;
	cout<<"pop1="<<s.pop()<<endl;
	cout<<"isempty? "<<s.isEmpty()<<endl;
	cout<<"pop2="<<s.pop()<<endl;
	cout<<"isempty? "<<s.isEmpty()<<endl;

	s.push(a);
	cout<<"top3="<<s.gettop()<<endl;
	s.push(b);
	s.push(a);
	s.push(b);


	return 0;
}

如果看不懂可以看下面带注释的
1.数组实现：`

/**
构建栈，并完善栈的各项操作，

1，判空
2，判断栈的长度，
3.插入，取出
4.栈顶的元素 
5.是否有最长度元素 


*/
#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
template<class T>
class mystack{
	private:
		int top;
	    int maxn;
		T *data;
	public:
		//初始化 
		mystack(){
			top=-1;
			maxn=100;//默认栈的最多100个元素 
			//分配数组内存 //销毁要用delete data 
			data=new T(maxn);
			memset(data,0,sizeof(data));//初始化数组 
		}
		//判断栈是否为空，若栈顶为-1，为空，否则为真 
		bool isEmpty(){
			return top==-1;
		}
		//判断是否 
		bool isFull(){
			return top==maxn-1;//如果栈现在是99 0-99为100个，满了 
		}
		//压入元素到栈，压栈 
		bool push(T temp){
			//如果栈未满则压栈 ，返回真，否则假 
			if(top<maxn){
				data[++top]=temp;
				return true;
			}
			return false;
		}
		//出栈 
		T pop(){
			T t=data[top];
			data[top]=0;//改未初始化 
			top--;//栈顶减1 
			return t;
		}
		//单纯得到栈顶数值 
		T gettop(){
		//	cout<<"gettop="<<data[top]<<endl;
			T t=data[top];
			return t;
		}
		//栈中有多少个元素 
		int length(){
			return top+1;//栈顶的下标就是个数-1 
		} 
		~mystack(){
			delete data;
		}
};
int main(){
	mystack<int> s;
	cout<<s.isEmpty()<<endl;
	cout<<s.isFull()<<endl;
	
	int a=100;
	int b=200;
	s.push(a);
	cout<<"top1="<<s.gettop()<<endl;
	s.push(b);
	cout<<"top2="<<s.gettop()<<endl;
	cout<<"pop1="<<s.pop()<<endl;
	cout<<"isempty? "<<s.isEmpty()<<endl;
	cout<<"pop2="<<s.pop()<<endl;
	cout<<"isempty? "<<s.isEmpty()<<endl;
	return 0;
}

2.链表实现：

#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
//采用模板类节点 ，结构体总是不知道啥毛病，老报错 
template<class T>
class Node{
private:
	T data;//数据 
	//节点的上一个节点，往栈底方向，如果本节点的前驱节点为空，则本节点为栈的最后一个节点
	Node *pre; 
public:
	Node(){}
	Node(T t,Node* _pre){
		data = t;
		pre = _pre;
	}

	T getData(){
		return data;
	}
	void setData(T t){
		data = t;
	}
	Node* getPre(){
		return pre;
	}
	void setPre(Node *_pre){
		pre = _pre;
	}
	~Node(){
//		cout<<"\n执行析构函数Node"<<endl;
	}

};



template<class T>
class mystack2{
private:
	Node<T>* top;//定义栈顶节点 
	Node<T>* Temp;//定义中间节点 
public:
	mystack2(){//初始化 
		top = NULL;
		Temp = NULL;
	}
	//判空 
	bool isEmpty(){
		return top == NULL;
	}
	
	
//因压栈和出栈均动态变化并且不会造成内存浪费，故此实现决定不考虑栈的节点上限  
	
//	//判断是否 满了，
	bool isFull(){//一直不满 
		return false; 
	}
	//压栈 
	bool push(T temp){
			Temp = new Node<T>(temp, NULL);//分配内存 ，并设置数据，前驱为空 
			//如果栈顶存在，即栈里本来有节点，则次节点的前驱指向栈顶 
			if (top != NULL){
				Temp->setPre(top);
			}
			
			//新压入的节点为栈顶 
			top = Temp;//更新栈顶 
			return true;
	}
	//出栈 
	T pop(){
		T t = top->getData();//取出栈顶的值 
		Temp = top;//临时保存 
		top = top->getPre();//出栈后，栈顶的前驱变为栈顶 
		delete Temp;//销毁栈顶 

		return t; 
	}
	//得到栈顶的数据 
	T gettop(){
		T t = top->getData();
		return t;
	}
	//析构函数 
	~mystack2(){
	//	cout<<"\n执行析构函数mystack2"<<endl; 
	
	//当栈顶不为空 
			while (top)
			{
				//取出栈顶， 
				
				Temp = top;
				//更新栈顶 
				top = top->getPre();
				delete Temp;//销毁栈顶 

			}

		

		//最后判断 
		if (Temp){

			delete Temp;
			Temp=NULL;
		}
		if (top){

				delete top;
				top=NULL;
		}
	}
};

int main(){
	mystack2<int> s;
	cout<<s.isEmpty()<<endl;
	cout<<s.isFull()<<endl;
	
	int a=100;
	int b=200;
	s.push(a);
	cout<<"top1="<<s.gettop()<<endl;
	s.push(b);
	cout<<"top2="<<s.gettop()<<endl;
	cout<<"pop1="<<s.pop()<<endl;
	cout<<"isempty? "<<s.isEmpty()<<endl;
	cout<<"pop2="<<s.pop()<<endl;
	cout<<"isempty? "<<s.isEmpty()<<endl;

	s.push(a);
	cout<<"top3="<<s.gettop()<<endl;
	s.push(b);
	s.push(a);
	s.push(b);


	return 0;
}