数据结构探索,使用C++实现最简单的数据结构代码(二) ——队列(Queue)

在上一篇文章中,我们实现了最简单的栈
接下来继续研究数据结构,队列
栈和队列的共同点在于,他们都是特殊的线性存储结构,只不过对于插入和删除元素的位置进行了限制
栈,是限定在表尾进行插入和删除操作的线性表
队列,是只允许在一端进行插入,另一端进行删除操作的线性表
与上一篇步骤相同,我先使用数组实现一个队列
由于最基础的队列结构简单,在这里我将实现一个循环队列

以下代码在windows10系统,vs2017环境编译通过

#include <iostream>

//2018/12/19 from朱宏江
//使用C++基于数组实现的循环队列,通过代码可了解队列先进先出的特点

class LoopQueue 
{
public:
	LoopQueue() = default;
	~LoopQueue() = default;
public:
	//循环队列初始化
	bool InitQueue()
	{
		memset(this->data, 0, 40);
		this->front = 0;
		this->rear = 0;
		return true;
	}
	//当前队列长度
	int QueueLength()
	{
		return (this->rear - this->front + 10) % 10; 
	}
	//入队
	bool EnQueue(int e) 
	{
		if ((this->rear + 1) % 10 == this->front)     //队列判满 队列头尾之间空出一个元素的间隔
		{
			std::cout << "队满" << std::endl;
			return false;
		}     
		this->data[this->rear] = e;                 //将元素e赋值给队尾
		this->rear = (this->rear + 1) % 10;         //rear指针后移一位,如果到最后则转到队列的数组头部
		return true;
	}
	//出队
	bool DeQueue(int *e) 
	{
		if (this->front == this->rear)              //队列判空 
		{
			return false;
		}
		*e = this->data[this->front];
		this->front = (this->front + 1) % 10;
		return true;
	}
private:
	int data[10];    
	int front;        //头指针
	int rear;         //尾指针,如果队列不为空,指向队列尾元素的下一个位置
};

//测试

int main(int argc, char** argv) 
{
	LoopQueue* lq = new LoopQueue();
	lq->InitQueue();
	std::cout << "当前队长 " << lq->QueueLength() << std::endl;

	for (int i = 0; i < 10; i++)       //测试队满情况
	{
		lq->EnQueue(i);
	}
	std::cout << "当前队长 " << lq->QueueLength() << std::endl;
	int num = 0;
	int* p_num = &num;
	for (int i = 0; i < 9; i++) 
	{
		lq->DeQueue(p_num);
		std::cout << *p_num << " 出队" << std::endl;
	}

	std::cin.get();
	return 0;
}

运行结果如下

接下来,使用链表实现一个队列

#include <iostream>

//2018/12/20 from朱宏江
//本段代码将以链表的形式实现一个队列

typedef struct QNode
{
	int data;
	struct QNode* next;
}QNode;

class ListQueue
{
public:
	ListQueue() {}
	~ListQueue() {}
public:
	//初始化
	void InitQueue() 
	{
		QNode* head = (QNode*)malloc(sizeof(QNode));
		this->front = head;
		this->rear = head;
	}
	//判空
	bool Empty() 
	{
		if (front == rear)
		{
			std::cout << "队列为空" << std::endl;
			return true;
		}
		else
		{
			std::cout << "队列不空" << std::endl;
			return false;
		}
	}
	//入队
	bool EnQueue(int e) 
	{
		QNode* q = (QNode*)malloc(sizeof(QNode));
		q->data = e;
		q->next = nullptr;
		this->rear->next = q;
		this->rear = q;
		return true;
	}
	//出队
	bool DeQueue(int* e) 
	{
		QNode* p = nullptr;
		if (Empty() == true) 
		{
			std::cout << "队列为空" << std::endl;
			return false;
		}
		p = front->next;
		*e = front->next->data;
		front->next = front->next->next;
		if (this->rear == p) 
		{
			this->rear = this->front;
		}
		free(p);
		return true;
	}
	
private:
	QNode* front;
	QNode* rear;
};


int main(int argc, char** argv) 
{
	ListQueue* Q = new ListQueue();
	Q->InitQueue();
	Q->Empty();
	
	for (int i = 0; i < 5; i++) 
	{
		Q->EnQueue(i);
	}

	int num = 0;
	int* p_num = &num;
	for (int i = 0; i < 5; i++) 
	{
		Q->DeQueue(p_num);
		std::cout << *p_num << std::endl;
	}
	
	std::cin.get();
	return 0;
}

运行结果如下