线性结构的两种常见应用之一 队列

线性结构的两种常见应用之一 队列

• 定义：

  • 一种可以实现“先进先出”得存储结构。

• 分类：

  • 链式队列：用链表实现

  • 静态队列（循环队列）：用数组实现

• 循环链表的重点

为了方便 我们先把一个简单的队列画出来(这里的“0”指的是没有元素！！)（Typora不会做表格，只能打表格了..）

4 |0|
3 |0|<——rear
2 |2|
1 |3|
0 |8|<——front

1. 静态队列为什么必须是循环队列

• 当加入一个元素时，元素插入rear的位置，rear向上移动，front不动；取出一个元素时，front向上移动，rear不动，这样会导致经过几轮的移动后，rear和front都往上移动，如果不为循环队列，下面的区域之后将永远用不到，造成了内存浪费。

2. 循环队列需要几个参数来确定，及其含义？

• 2个参数：front(指向头部元素)和rear（指向尾部元素的后一个元素）。

3. 如何判断循环队列是否为空

• 如果front与rear的值相等，则队列一定为空

4. 如何判断循环队列是否已满

4 |0|<——rear
3 |9|
2 |8|
1 |5|
0 |3|<——front

• 数组长度为5，如果再加一个元素，rear=（rear+1）% 5，这时rear等于front。
• 按道理来说，是不是rear和front相等，就算数组满了呢？但是不行！因为数组为空也同样是这个条件！！
• 所以我们采取一个方法，让数组的最大元素减一个（才一个，不会影响），即队列最后一个位置永远不能插入，如上图，就认为该数组已满，所以只要rear+1==front我们就认为该数组满了。
• 即队列为len，当数组元素为len-1时，认为该队列已满。

//2020.4.3//16.18

#include<iostream>
using namespace std;

typedef struct Queue
{
	int* pBase;   //循环队列形式类似数组，设定数组首地址
	int front;   //队头
	int rear;   //队尾
	int len;   //队伍长度
}QUEUE, * PQUEUE;


//初始化队列
void init_queue(PQUEUE, int);
//判断队列是否已满
bool is_full(PQUEUE);
//插入元素
void entry_queue(PQUEUE, int);
//判断队列是否为空
bool is_empty_(PQUEUE);   //用is_empty疯狂报错 搞了半天原来vs自带这个函数..只能改名了。。还不会
//删除元素
void out_queue(PQUEUE);
//遍历队列
void traverse_queue(PQUEUE);

int main()
{
	int val;
	int length = 5;
	QUEUE Q;
	PQUEUE pQ = &Q;
	init_queue(pQ, length);
	entry_queue(pQ, 1);
	entry_queue(pQ, 0);
	entry_queue(pQ, 4);
	entry_queue(pQ, 2);
	entry_queue(pQ, 8);   //虽然队列长度是5，但最大元素只能是4
	entry_queue(pQ, 5);
	traverse_queue(pQ);
	out_queue(pQ);
	return 0;
}

void init_queue(PQUEUE pQ, int length)
{
	pQ->len = length;
	pQ->pBase = (int*)malloc(sizeof(int) * pQ->len);
	pQ->front = 0;
	pQ->rear = 0;    //现在没有元素，数组第一个下标为0
	return;
}

bool is_full(PQUEUE pQ)
{
	if ((pQ->rear + 1) % pQ->len == pQ->front)        
		return true;
	else
		return false;
}

void entry_queue(PQUEUE pQ, int val)
{
	if (is_full(pQ))
		cout << "队列已满，元素" << val << "插入失败" << endl;
	else
	{
		pQ->pBase[pQ->rear] = val;
		pQ->rear = (pQ->rear + 1) % pQ->len;
	}
	return;
	
}
bool is_empty_(PQUEUE pQ)
{
	if (pQ->front == pQ->rear)
		return true;
	else
		return false;
}
void out_queue(PQUEUE pQ)
{
	if (is_empty_(pQ))
		cout << "队列为空，无法删除元素" << endl;
	else
	{
		cout << "出队元素为" << pQ->pBase[pQ->front] << endl;
		pQ->front = (pQ->front + 1) % pQ->len;		
	}
	return;
}

void traverse_queue(PQUEUE pQ)
{	
	if (is_empty_(pQ))
		cout << "队列为空";
	int i = pQ->front;
	while (i != pQ->rear)
	{
		cout << pQ->pBase[i] << " ";
		i = (i + 1) % pQ->len;
	}
	return;
}