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

栈的概念和结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出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;
}

入栈

压栈就是在栈顶插入元素，其中是肯定要考虑到扩容的问题，当this->top == this->size时，就要考虑到扩容了，扩容也是像之前顺序表那样每次扩一倍，这样可以一定程度地减少扩容次数，但同时是会带来一定的空间消耗的。

//入栈
void Push(const DateType& val)
{
	if (ifFull())
	{
		ExpandStack();
	}
	data[top++] = val;
}

出栈

出栈就是在栈顶pop掉一个元素，也就是top-1指向的位置，只需要将top进行一个减1的操作即可。
与此同时，我们要确保此次栈不为空，所以要进行判断栈空的操作，防止程序崩溃。

//出栈，并获取出栈元素
bool Pop(DateType &item)
{
	if (isEmpty())
	{
		cout << "栈为空，无法出栈" << endl;
		return false;
	}
	item = data[--top];
	return true;
}

赋值运算符重载

运算符重载的注意事项在前面的博客我已经介绍过了，尤其是赋值运算符，感兴趣的小伙伴可以去看看，这里要注意几点

• 返回的是*this，对象本身
• 不要自己给自己赋值
• 要防止内存泄漏
• 防止浅拷贝的发生

//等号运算符的重载
Stack& operator=(const Stack& stack)
{
	//防止自赋值
	if (this == &stack)
	{
		return *this;
	}
	//防止内存泄漏
	if (data != NULL)
	{
		delete[] data;
	}
	//防止浅拷贝
	this->data = new DateType[stack.size];
	if (data == NULL)
	{
		cout << "内存分配失败" << endl;
		exit(-1);
	}
	for (int i = 0; i < stack.top; i++)
	{
		this->data[i] = stack.data[i];
	}
	this->size = stack.size;
	this->top = stack.top;
	return *this;
}

打印

//打印
void PrintStack()
{
	for (int i = 0; i < top; i++)
	{
		cout << data[i] << "  ";
	}
	cout << endl;
}

整体代码以及测试

#define _CRT_SECURE_NO_WARNINGS
#include<iostream> //引入头文件
#include<string>//C++中的字符串
using namespace std; //标准命名空间
#define InitSize  5
/*
栈,利用顺序表实现
*/
template <class DateType>
class Stack
{
public:
	//初始化栈，初始化的大小是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;
	}
	//等号运算符的重载
	Stack& operator=(const Stack& stack)
	{
		//防止自赋值
		if (this == &stack)
		{
			return *this;
		}
		//防止内存泄漏
		if (data != NULL)
		{
			delete[] data;
		}
		//防止浅拷贝
		this->data = new DateType[stack.size];
		if (data == NULL)
		{
			cout << "内存分配失败" << endl;
			exit(-1);
		}
		for (int i = 0; i < stack.top; i++)
		{
			this->data[i] = stack.data[i];
 
		}
		this->size = stack.size;
		this->top = stack.top;
		return *this;
	}
	//销毁栈
	~Stack()
	{
		if (data != NULL)
		{
			delete[] data;
			data = NULL;
		}
	}
	//判断栈是否满了
	bool ifFull()
	{
		if (top == size)
		{
			return true;
		}
		return false;
	}
	//判断栈是否为空
	bool isEmpty()
	{
		if (top == 0)
		{
			return true;
		}
		return false;
	}
	//入栈
	void Push(const DateType& val)
	{
		if (ifFull())
		{
			ExpandStack();
		}
		data[top++] = val;
	}
	//出栈，并获取出栈元素
	bool Pop(DateType &item)
	{
		if (isEmpty())
		{
			cout << "栈为空，无法出栈" << endl;
			return false;
		}
		item = data[--top];
		return true;
	}
	//扩容
	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;
	}
	//打印
	void PrintStack()
	{
		for (int i = 0; i < top; i++)
		{
			cout << data[i] << "  ";
		}
		cout << endl;
	}
private:
	DateType* data;//栈空间指针
	int size;//栈容量
	int top;//栈顶，栈中元素个数
};
int main()
{
	Stack<int> stack;
	stack.Push(1);
	stack.Push(2);
	stack.Push(3);
	stack.Push(4);
	stack.Push(5);
	stack.PrintStack();
	cout << "-------------------------" << endl;
	int b = 0;
	stack.Pop(b);
	cout << b << endl;
	stack.Pop(b);
	cout << b << endl;
	stack.PrintStack();
	cout << "-------------------------" << endl;
	Stack<int> stack2(stack);
	stack2.PrintStack();
	cout << "-------------------------" << endl;
	Stack<int> stack3;
	stack3 = stack2;
	stack3.PrintStack();
	cout << "-------------------------" << endl;
	system("pause");
	return EXIT_SUCCESS;
}

队列

队列的概念和结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。

队列的结构，我们选取单链表来实现，秩序进行头删和为插的不足即可。如果选数组，那么每一次删头我们都要挪动一遍数据，这种方式不优，所以我们还是选取用单链表来实现。
定义的结构如下：

template<class DateType>
//链队的结点类型
struct Node
{
	DateType data;
	Node<DateType> *next;
	Node(Node<DateType>* p = NULL)
	{
		next = p;
	}
	//构造函数
	Node(DateType val, Node<DateType>* p = NULL)
	{
		data = val;
		next = p;
	}
};

template <class DateType>
class Queue
{
public:
private:
	//声明，也是定义，只不过定义的是指针类型，保存的应该是地址，未初始化
	//队头指针
	Node<DateType>* front;
	//队尾指针
	Node<DateType>* rear;
};

队列的实现

队列的接口

Queue();//构造函数，初始化队列
~Queue();//析构函数
bool QueuePush(const DateType& val);//队尾入队
bool QueuePop(DateType& val);//对头出队列
bool getFront(DateType& val) const;//获取对头元素的值
bool getRear(DateType& val);//获取队尾元素的值
void MakeEmpty();//将队列清空
bool isEmpty() const;//判断队列是否为NULL
int getSize() const;//返回队列元素的个数
void PrintQueue();//输出队列元素

队列的初始化

初始化很简单，只要将头指针和尾指针都置空。

//构造函数
Queue()
{
	front = NULL;
	rear = NULL;
}

判断队列是否为空

//判断队列是否为NULL
bool isEmpty() const
{
	if (front == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}

入队

出队就是进行单链表尾删的操作，要考虑链表为空时不能进行删除，还要注意的是只有一个节点进行删除是要改变尾指针的指向。

//队尾入队列
bool QueuePush(const DateType& val)
{
	if (front == NULL)
	{
		//如果队列为空，直接用指针开辟结点
		front = rear = new Node<DateType>(val);
		if (front == NULL)
		{
			cout << "内存分配失败" << endl;
			return false;
		}
	}
	else
	{
		Node<DateType>* p = new Node<DateType>(val);
		rear->next = p;
		if (rear->next == NULL)
		{
			cout << "内存分配失败" << endl;
			return false;
		}
		//更新尾结点
		rear = rear->next;
	}
	return true;
}

出队

出队就是进行单链表尾删的操作，要考虑链表为空时不能进行删除，还要注意的是只有一个节点进行删除是要改变尾指针的指向。

bool QueuePop(DateType& val)
{
	//如果队列为空，不允许出列
	if (isEmpty())
	{
		return false;
	}
	else
	{
		Node<DateType>* p = front;
		val = front->data;
		front = front->next;
		delete p;
		return true;
	}
}

获取队头元素和队尾元素

首先要确保链表不为空，对头就是返回头节点的大小，队尾就是返回尾节点的大小。
具体实现如下：

//获取对头元素的值
bool getFront(DateType& val) const
{
	if (isEmpty())
	{
		return false;
	}
	val = front->data;
	return true;
}
//获取队尾元素的值
bool getRear(DateType& val) {
	if (isEmpty())
	{
		return false;
	}
	val = rear->data;
	return true;
}

获取队列元素个数

遍历一遍链表，同时进行计数操作，最后返回计数结果即可。

//返回队列元素的个数
int getSize() const
{
	//函数返回队列元素的个数
	Node<DateType>* p = front;
	int count = 0;
	while (p != NULL)
	{
		++count;
		p = p->next;
	}
	return count;
}

队列的销毁

为了防止内存泄漏，动态内存申请的空间一定要我们自己手动释放，养成一个良好的习惯。所以要将链表的空间逐个释放。

//将队列清空
void MakeEmpty()
{
	//置空队列，释放链表中所有的结点
	Node<DateType>* current;
	if (front != NULL)
	{
		current = front;
		front = front->next;
		delete current;
	}
}

打印队列

//输出队列元素
void PrintQueue()
{
	Node<DateType>* p = front;
	while (p != NULL)
	{
		cout << p->data << "  ";
		p = p->next;
	}
	cout << endl;
}

整体代码以及测试

#define _CRT_SECURE_NO_WARNINGS
#include<iostream> //引入头文件
#include<string>//C++中的字符串
using namespace std; //标准命名空间
/*
队列，单链表实现
*/
template<class DateType>
//链队的结点类型
struct Node
{
	DateType data;
	Node<DateType> *next;
	Node(Node<DateType>* p = NULL)
	{
		next = p;
	}
	//构造函数
	Node(DateType val, Node<DateType>* p = NULL)
	{
		data = val;
		next = p;
	}
};
template <class DateType>
class Queue
{
public:
	//构造函数
	Queue()
	{
		front = NULL;
		rear = NULL;
	}
	//析构函数
	~Queue()
	{
		MakeEmpty();
	}
	//队尾入队列
	bool QueuePush(const DateType& val)
	{
		if (front == NULL)
		{
			//如果队列为空，直接用指针开辟结点
			front = rear = new Node<DateType>(val);
			if (front == NULL)
			{
				cout << "内存分配失败" << endl;
				return false;
			}
		}
		else
		{
			Node<DateType>* p = new Node<DateType>(val);
			rear->next = p;
			if (rear->next == NULL)
			{
				cout << "内存分配失败" << endl;
				return false;
			}
			//更新尾结点
			rear = rear->next;
		}
		return true;
	}
	//对头出队列
	bool QueuePop(DateType& val)
	{
		//如果队列为空，不允许出列
		if (isEmpty())
		{
			return false;
		}
		else
		{
			Node<DateType>* p = front;
			val = front->data;
			front = front->next;
			delete p;
			return true;
 
		}
	}
	//获取对头元素的值
	bool getFront(DateType& val) const
	{
		if (isEmpty())
		{
			return false;
		}
		val = front->data;
		return true;
	}
	//获取队尾元素的值
	bool getRear(DateType& val) {
		if (isEmpty())
		{
			return false;
		}
		val = rear->data;
		return true;
	}
	//将队列清空
	void MakeEmpty()
	{
		//置空队列，释放链表中所有的结点
		Node<DateType>* current;
		if (front != NULL)
		{
			current = front;
			front = front->next;
			delete current;
		}
	}
	//判断队列是否为NULL
	bool isEmpty() const
	{
		if (front == NULL)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//返回队列元素的个数
	int getSize() const
	{
		//函数返回队列元素的个数
		Node<DateType>* p = front;
		int count = 0;
		while (p != NULL)
		{
			++count;
			p = p->next;
		}
		return count;
	}
	//输出队列元素
	void PrintQueue()
	{
		Node<DateType>* p = front;
		while (p != NULL)
		{
			cout << p->data << "  ";
			p = p->next;
		}
		cout << endl;
	}
private:
	//声明，也是定义，只不过定义的是指针类型，保存的应该是地址，未初始化
	//队头指针
	Node<DateType>* front;
	//队尾指针
	Node<DateType>* rear;
};
int main()
{
	Queue<int> que;
	que.QueuePush(1);
	que.QueuePush(2);
	que.QueuePush(3);
	que.QueuePush(4);
	que.PrintQueue();
	cout << "----------------------" << endl;
	int b = 0;
	que.QueuePop(b);
	cout << b << endl;
	que.QueuePop(b);
	cout << b << endl;
	que.PrintQueue();
	cout << "----------------------" << endl;
	int c = 0;
	que.getFront(c);
	cout << c << endl;
	que.PrintQueue();
	cout << que.getSize() << endl;
	cout << "----------------------" << endl;
	system("pause");
	return EXIT_SUCCESS;
}