数据结构之栈（顺序栈、链栈的类模板实现）（C++）

一、顺序栈类模板

//文件名："SqStack.h"
#pragma once
#ifndef SQSTACK_H_
#define SQSTACK_H_

/*
	注：
	1.实现类模板时，目前在VS中似乎只能将类定义与类实现放于同一个文件中，才能连接成功！！
	2.模板的包含编译模式在 VS 中不能连接成功（#include "SqStack.cpp"）；
	3.模板的分离编译模式在 VS 中不支持 export ，也不可用。
*/

template <typename ElemType>
class SqStack
{
	/*
		顺序栈 类模板定义
		设计思路：
			1.出现的问题：原一维指针只能用来操作一维数组，而一维数组的每个元素内存又是固定的，这时类对象在 Push() 时就无法复制到数组中；
			2.解决方式：设计一个二维指针（指针的指针），构成一个一维的指针数组，在类对象 Push() 时，只存放其对象地址。
	*/
private:
	ElemType **base;	//栈底指针的指针，指针数组中存放元素地址
	int top;	//栈顶索引
	int StackSize;	//栈容量
	int STACK_INCREMENT = 10;	//满栈后，栈扩充步长
public:
	SqStack(int m);	//构建一个长度为 m 的栈
	~SqStack();	//析构函数：栈销毁
	void Push(ElemType *e);	//入栈
	ElemType *Pop();	//出栈
	ElemType *GetTop();	//获取栈顶元素
	bool Empty();	//测栈空
	//void Tranverse();	//显示栈中元素（需元素对象自身先实现显示接口才行）
};


template <typename ElemType>
SqStack<ElemType>::SqStack(int m)
{
	/*
		构造函数：初始化顺序栈
	*/
	this->base = (ElemType **)malloc(m * sizeof(ElemType *));	//申请指针数组表空间
	//this->base = new ElemType*[m];
	this->top = -1;	//初始化栈顶索引 -1 空标志，[顺序栈栈底（数组第一个结点）为 0 ]
	this->StackSize = m;	//初始化当前栈容量 m
}

template <typename ElemType>
SqStack<ElemType>::~SqStack()
{
	/*
		析构函数：销毁链栈
			注：栈对象不负责销毁元素对象内存！！
	*/
	/*
	//0.遍历销毁元素对象内存
	for (int i = 0; i < this->top; i++)
	{
		delete this->base[i];
		cout << "删除 ：" << i << endl;
	}
	*/
	//1.初始化参数
	this->StackSize = 0;
	this->top = -1;
	//2.销毁指针的指针（开辟的一维指针数组空间）
	delete[] this->base;
}

template <typename ElemType>
void SqStack<ElemType>::Push(ElemType *e)
{
	/*
		入栈
	*/
	//判断是否满栈
	if (this->top == this->StackSize - 1)
	{
		//cout << "栈满，无法入栈！" << endl;
		//return;
		//满栈后，扩充
		this->base = (ElemType **)realloc(this->base, (this->StackSize + this->STACK_INCREMENT) * sizeof(ElemType *));
		this->StackSize = this->StackSize + this->STACK_INCREMENT;
		cout << "栈满，开辟10个空间，共计：" << this->StackSize << endl;
	}
	this->top++;
	*(this->base + this->top) = e;
}

template <typename ElemType>
ElemType *SqStack<ElemType>::Pop()
{
	/*
		出栈
	*/
	//判断是否空栈
	if (this->top == -1)
	{
		cout << "栈空，无法出栈！" << endl;
		return NULL;
	}
	ElemType *e = *(this->base + this->top);
	this->top--;
	return e;
}

template <typename ElemType>
ElemType *SqStack<ElemType>::GetTop()
{
	/*
		获取栈顶元素
	*/
	//判断是否空栈
	if (this->top == -1)
	{
		cout << "栈空，无栈顶元素！" << endl;
		return NULL;
	}
	return *(this->base + this->top);
}

template <typename ElemType>
bool SqStack<ElemType>::Empty()
{
	/*
		测栈空
	*/
	return this->top == -1 ? true : false;
}

#endif // !SQSTACK_H_

//文件名："SqStack_Test.cpp"
#include "stdafx.h"
#include <iostream>
#include "SqStack.h"
using namespace std;

struct BNode
{
	int tag;
	int bal;
};

int main()
{
	//1.测试 BNode 类型结点
	BNode *bn1 = new BNode();
	bn1->tag = 4;
	BNode *bn2 = new BNode();
	bn2->tag = 5;
	SqStack<BNode> sqa(1);
	sqa.Push(bn1);
	sqa.Push(bn2);
	BNode *b;
	b = sqa.Pop();
	cout << b->tag << endl;	
	delete bn1, bn2;
	cout << "-------------------" << endl;
	
	//2.测试 int 类型结点
	SqStack<int> *sqb = new SqStack<int>(10);
	sqb->Push(new int(2));
	int a = *sqb->GetTop();
	cout << a << endl;
	delete sqb;
	cout << "-------------------" << endl;
	
	return 0;
}

二、链栈类模板

//文件名："LinkStack.h"
#pragma once
#ifndef LINKSTACK_H_
#define LINKSTACK_H_

/*
	链栈 类模板定义
*/
template <typename ElemType>
class LinkStack
{
	/*
		链栈结点
	*/
	struct LSNode
	{
		ElemType *data;	//数据元素
		LSNode *next;	//指针域
	};
private:
	LSNode *top;	//链栈头指针（栈顶指针）
public:
	LinkStack() { this->top = NULL; }	//无参构造
	~LinkStack();	//析构函数：销毁链栈
	void Push(ElemType *e);	//入栈
	ElemType *Pop();	//出栈
	ElemType *GetTop();	//获取栈顶元素
	bool Empty() { return this->top == NULL ? true : false; }
};

template <typename ElemType>
LinkStack<ElemType>::~LinkStack()
{
	/*
		析构函数：销毁链栈
	*/
	LSNode *p = this->top, *q;
	while (p != NULL)
	{
		q = p->next;
		cout << "删除：" << p << endl;
		delete p->data;
		delete p;
		p = q;
	}
}

template <typename ElemType>
void LinkStack<ElemType>::Push(ElemType *e)
{
	/*
		入栈
	*/
	LSNode *p = new LSNode();
	p->data = e;
	p->next = this->top;
	this->top = p;
}

template <typename ElemType>
ElemType *LinkStack<ElemType>::Pop()
{
	/*
		出栈
	*/
	if (this->top == NULL)
	{
		cout << "栈空！" << endl;
		return NULL;
	}
	LSNode *p = this->top;
	ElemType *e = this->top->data;
	this->top = this->top->next;
	delete p;
	return e;
}

template <typename ElemType>
ElemType *LinkStack<ElemType>::GetTop()
{
	/*
		获取栈顶元素
	*/
	if (this->top == NULL)
	{
		cout << "栈空！" << endl;
		return NULL;
	}
	return this->top->data;
}

#endif // !LINKSTACK_H_

//文件名："LinkStack_Test.cpp"
#include "stdafx.h"
#include <iostream>
#include "LinkStack.h"
using namespace std;

struct Node
{
	int a;
	int b;
};

int main()
{
	LinkStack<Node> *ls = new LinkStack<Node>();
	Node *n1 = new Node();
	n1->a = 1;
	n1->b = 2;
	Node *n2 = new Node();
	n2->a = 3;
	n2->b = 4;
	ls->Push(n1);
	ls->Push(n2);
	//ls->Pop();
	//ls->Pop();
	Node *n3 = ls->Pop();
	if (n3 == NULL)
		cout << "空" << endl;
	else
		cout << n3->a << endl;

	if (!ls->Empty())
		delete ls;
	
	return 0;
}