【算法总结系列

【算法总结系列

说到基础的算法，队列是少不了的。

队列：是一种特殊的线性结构，只允许在队列的首部（head）进行删除操作，这也叫“出队”。在尾部进行插入操作，这称为“入队”。

当队列中没有元素时，称为空队列。

这里借用《啊哈，算法》里面的一个例子来归纳下队列这个算法概念。

A同学向B同学索问qq号，B同学给了A同学一串加密的数字，解译的规则如下：

给定一串数字，首先将第一个数删除，紧接着将第二个数放到这串数的末尾，再讲第三个数删除并将第四个数放到这串数的末尾，再将第五个数删除······

直到剩下最后一个数，将最后一个数删除。按照刚才删除的顺序，把这些删除的数连在一起得到的数字串就是B的QQ号。

假定给定的这串加密后的数字串是 ： 6,3,1,7,5,8,9,2,4

#include <iostream>
using namespace std;
int main()
{int q[102] = {0,6,3,1,7,5,8,9,2,4},head,tail;//用数组来表示一条队列，head指向队列头部,tail指向队列尾部//初始化队列head = 1;tail = 10;while(head < tail){cout<<q[head];   //取出队列的头head++;          //头指针指向下一位，指向的就是队列新的头部数据q[tail] = q[head]; //把新的队列的头部的值赋给队列的尾部tail++;           //队列尾部指针后移一位head++;           //头指针后移一位}system("pause");system("pause");return 0;
}

根据上面的代码，其实可以抽取出队列的三个基本元素（一个数组，两个变量）封装成一个结构体类型：

struct queue
{int data[100];   //队列的主体，用于存放队列的实际内容int head;        //队首int tail;        //队尾
};

该结构体：

结构体通常放在main函数的外面，结构体定义的结尾有个 分号；

struct 是结构体的关键字，queue是我们为这个结构体 起 的名字，这个结构体的成员分别是：int data[],int head,int tail.

这样就可以把这三个部分作为一个整体来对待（这也是为什么成为 结构体 的原因吧）

{可以把结构体理解为一种新的数据类型，这个数据类型很强大，用这个数据类型定义的变量可以同时存储一个整型数组，两个整数。}

具体如下：

#include <iostream>
using namespace std;struct queue
{int data[100];   //队列的主体，用于存放队列的实际内容int head;        //队首int tail;        //队尾
};int main()
{struct queue q;  //声明结构体变量 （注意，这里不可以 单单写 queue q）int i;//初始化队列q.head = 1;q.tail = 1;for(i = 1;i <= 9; i++){//依次向队列中插入9个数cin>>q.data[q.tail];   //从队尾插入q.tail++;}while(q.head < q.tail)       //当队列不为空的时候执行循环{cout<<q.data[q.head];      //取出队列的头q.head++;                  //头指针指向下一位，指向的就是队列新的头部数据q.data[q.tail] = q.data[q.head];  //把新的队列的头部的值赋给队列的尾部q.tail++;                         //尾部指针后移q.head++;                         //头部指针后移，为下一轮循环做准备}system("pause");system("pause");return 0;
}

仔细研究下，还是可以很容易理解这个例子的。