欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-01 11:28:36
...

一、顺序栈类模板
数据结构之栈(顺序栈、链栈的类模板实现)(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;
}


二、链栈类模板
数据结构之栈(顺序栈、链栈的类模板实现)(C++)


//文件名:"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;
}