队列问题非STL解决方案

常年使用STL解决队列问题，以至于严重生疏队列的根本原理。。。

直到今日被老师被迫使用算法原理解决问题，方才意识到我对队列一窍不通。。。

。。。直到经过一系列的坑蒙拐骗之后，方才理清楚一些头绪，在此附记。

有关概念在此不再赘述，因为这东西怕不是一搜一大堆。。。

循环队列——数组存储方案：

我们需要的东西：

1.一个数组，拿来存队列。

int ique[capa];//capa是数组（队列）的最大容量，看下面↓

2.头指针及尾指针，指明队列的头和尾。

int	ihead=0,itail=0;

3.再来两个量——队列的当前长度（是变量）及其最大容量（是常量，在开数组时已经界定，这里为演示开的短一些，只开到4）

int ilen=0;

const int capa=4;

接下来是一些基本的操作：

1.将elem入队：

int elem;

ique[itail]=elem;//尾指针始终指向队列尾部的下一个位置，因此我们只需将尾指针处的数字做出更改即可。

itail++;//尾指针自增，指向下一个位置。

itail=itail % capa;//圈重点，见下↓

ilen++;//因为多了一个元素而长度增加，使ilen自增。

itail=itail % capa;

我们一直在使尾指针自增，而数组的长度只有4。在这里通过取余即可实现循环入队。这样当尾指针增大到capa以外时，通过该语句即可自动使尾指针跳转回数组的开头，实现循环读入、循环存储。

在这里尾指针始终指向队列尾部的下一个位置，使其指向队列尾部那个元素的原理是相同的。

2.出队，存入elem：

int elem;

elem=ique[ihead];//直接取出头指针处的元素

ihead++;//头指针往下移动

ihead=ihead % capa;//和上面同理

ilen--;//因为少了一个元素而长度减少，使ilen自减。

比较关键的操作就在于将指针对capa取余，这样的操作可以使指针形成循环，也就实现了队列的循环存储。在其他地方如果我们需要用到循环存储，对其容量取余是个很好的思路。当然实际应用中其大小不仅仅是4这么少，我们还应该留意数据范围合理安排空间，要不出现了塞不下或者空太多的问题都是很辣手棘手的。

基本的操作就是这样（是不是很简单）（是不是理解起来有些难）（还是本来就挺简单被我给说难了。。。）

举个例子：

洛谷P1996 约瑟夫问题

题目：

n个人(n<=100)围成一圈,从第一个人开始报数,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出圈,……依次类推,直到所有的人都出圈,请输出依次出圈人的编号.

输入格式

n m

输出格式

出圈的编号

输入样例

10 3

输出样例

3 6 9 2 7 1 8 5 10 4

说明

m,n≤100

-->用STL的话基本不用动脑，5分钟搞定。如下：

#include<queue>//队列所必须的头文件

#include<cstdio>

using namespace std;

queue <int> set;//创建该队列

int main()

{

	int n,m;

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

	{

		set.push(i);//把各个人的编号入队准备报数

	}

	int counti=1;//报数的计数器

	while(!set.empty())

	{

		if(counti!=m)

		{

			set.push(set.front());//不是m，循环将队头塞进队尾，实现循环

			set.pop();

		}

		if(counti==m)

		{

			printf("%d ",set.front());//是m这个人出列，将其编号输出后出队

			set.pop();

			counti=1;//再次从1开始

			continue;//继续

		}

		counti++;

	}

	return 0;

}

不使用STL的话，构建队列就要稍微麻烦一些，不过能更好的理解其原理及应用。然而无论如何STL都只是个工具，我们必要应该掌握的还是其实现原理。下面是无STL的解决方案：

//luogu.org P1996 -- NO STL Solution

//queue--Array Solution

//IZWB003-2019/07/24

#include<cstdio>

//set queue//设置该队列

int head=0,tail=0;//指针2个

int length=0;const int capacity=120;//大小及长度

int queue[capacity];//通过数组储存队列

int element;

using namespace std;

int main()

{

	int n,m;

	scanf("%d%d",&n,&m);

	for(int i=0;i<n;i++)

	{

		queue[tail]=i+1;//尾指针处入队

		tail++;

		tail=tail%capacity;//上面的方法

		length++;//改长度

	}

	int i=0;//以i作为报数的计数器

	while(true)

	{

		element=queue[head];//头指针处出队

		head++;

		head=head%capacity;//上面的方法

		length--;//改长度

		i++;//报数

		if(i==m)//该出队处

		{

			printf("%d ",element);//输出

			i=0;//重新报数

		}

		else//不符合则接着入队

		{

			queue[tail]=element;

			tail++;

			tail=tail%capacity;

			length++;

		}

		if(length==0) break;//队空则结束

	}

	return 0;

}

有关链表建队列的相关知识，有时间的话，稍后补充。

巴特西

队列问题非STL解决方案

队列问题非STL解决方案

循环队列——数组存储方案：

我们需要的东西：

接下来是一些基本的操作：

1.将elem入队：

2.出队，存入elem：

举个例子：

最新文章

热门文章