数据结构初阶–栈和队列（讲解+类模板实现）

栈的概念和结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）加粗样式的原则。
入栈：从栈顶放入数据的操作。
出栈：从栈顶取出元素的操作。

栈的实现

栈用链表和顺序表两种数据结构都可以实现，我们要确定选择哪一种更优，我们来分析一下。
链表栈：如果选择单链表的话，我们应该选择头当栈顶，尾当栈底，不然的话，每次存取数据都要遍历一遍链表。所以选双链表会比较好一点。
数组栈：访问栈顶的时间复杂度为O(1)，相比链表栈比较优。
所以下面我们用顺序表来实现栈的这种数据结构。
结构如下：初始化栈的大小为5

#define InitSize  5
template <class DateType>
class Stack
{
public:
private:
	DateType* data;//栈空间指针
	int size;//栈容量
	int top;//栈顶，栈中元素个数
};	

栈的接口

栈要实现的接口有以下几个：

Stack();//初始化栈，初始化的大小是5
Stack(const Stack& stack);//拷贝构造函数
Stack& operator=(const Stack& stack);//等号运算符的重载
~Stack();//销毁栈
bool ifFull();//判断栈是否满了
bool isEmpty();//判断栈是否为空
void Push(const DateType& val);//入栈
bool Pop(DateType &item);//出栈，并获取出栈元素
void ExpandStack();//扩容
void PrintStack();//打印

栈的初始化

初始化栈就是把结构体中的成员都初始化一下，方便后续的扩容等操作。
具体实现如下：

//初始化栈，初始化的大小是5
Stack()
{
	data = new DateType[InitSize];
	if (data == NULL)
	{
		cout << "内存分配失败" << endl;
		exit(-1);
	}
	size = InitSize;
	top = 0;
}

拷贝构造

//拷贝构造函数
Stack(const Stack& stack)
{
	this->data = new DateType[stack.size];
	if (data == NULL)
	{
		cout << "内存分配失败" << endl;
		exit(-1);
	}
	for (int i = 0; i < stack.size; i++)
	{
		this->data[i] = stack.data[i];
	}
	this->size = stack.size;
	this->top = stack.top;
}

判断栈满

//判断栈是否满了
bool ifFull()
{
	if (top == size)
	{
		return true;
	}
	return false;
}

扩容

//扩容
void ExpandStack()
{
	this->size = this->size == 0 ? 4 : 2 * this->size;
	DateType* tmp = new DateType[this->size];
	if (tmp == NULL)
	{
		cout << "内存分配失败" << endl;
		exit(-1);
	}
	for (int i = 0; i < top; i++)
	{
		tmp[i] = data[i];
	}
	delete[] data;
	data = tmp;
}

判断栈空

//判断栈是否为空
bool isEmpty()
{
	if (top == 0)
	{
		return true;
	}
	return false;
}

本站声明：
1. iCode9 技术分享网（下文简称本站）提供的所有内容，仅供技术学习、探讨和分享；

2. 关于本站的所有留言、评论、转载及引用，纯属内容发起人的个人观点，与本站观点和立场无关；

3. 关于本站的所有言论和文字，纯属内容发起人的个人观点，与本站观点和立场无关；

4. 本站文章均是网友提供，不完全保证技术分享内容的完整性、准确性、时效性、风险性和版权归属；如您发现该文章侵犯了您的权益，可联系我们第一时间进行删除；

5. 本站为非盈利性的个人网站，所有内容不会用来进行牟利，也不会利用任何形式的广告来间接获益，纯粹是为了广大技术爱好者提供技术内容和技术思想的分享性交流网站。