数据结构与性质(1)队列(queue)基础板子

        队列的定义:队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。它允许在表的一端插入数据，在另一端删除元素。插入元素的这一端称之为队尾。删除元素的这一端我们称之为队首。它的特点是数据元素先进先出(FIFO),类似于排队取票(买到票的在队伍前面，要离开队伍，与删除操作类似；没买到票的在队伍后面，新来的人在队尾，与插入操作类似)。

附简图：

           C                                                                                                       A                      B

则C从head处离开，若有新来的D，则跟着Tail处的B进来。

(打饭先到先得，不能插队!) 

PS:为了避免head与tail重合，我们令tail记录队尾的下一个位置。

实际上，queue也可作为一个结构体类型：

struct queue
{    int data[1000];//队列主体，用于存放数据
     int head；//队首
     int tail；//队尾
};

一.不使用C++中STL库函数对队列进行操作(创建、入队、出队)

#include<iostream>
#include<algorithm>
#include<queue>
struct queue
{    int data[100];
     int head;
     int tail;
};

int main()
{    struct queue q;
     int i;
     //初始化队列
     q.head=1;
     q.tail=1;
     for(i=1;i<10;i++)
     {    scanf("%d",&q.data[q.tail]);//依次向队列中插入9个数
          q.tail++;
     }
     while(q.head<q.tail) //当队列不为空的时候执行循环
     {    
          //打印队首并将队首出队(等同于没有q.data[1])
          printf("%d",q.data[q.head]);
          q.head++；
          //先将新的队首的数添加到队尾
          q.data[tail]=q.data[head];
          q.tail++;//将队首出队     

     }
     return 0;
}

由上述代码可知，我们只能对队列的head和tail进行访问，因此队列不能用for等循环语句进行遍历

二:C++STL中queue的常见接口(内置函数)

构造函数:

queue<T> que;//queue采用模板类实现，queue对象的默认构造形式
queue(const queue &que);//拷贝构造函数

赋值操作:

queue& operator=(const queue &que);//重载等号操作符

数据存取:

push(elem);//向队尾添加元素(类似于v.push_back())
pop();//从队首删除第一个元素
back();//返回队尾值
front();//返回队首值

大小操作:

empty();//判断堆栈是否为空
size();//返回栈的大小

实例操作:

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
    //队列 queue
void test11()
{    queue<int> q;//创建queue
     
     //准备数据
     int a[5];
     for(int i=0;i<5;i++)
     {    a[i]=i;
     }//对a[10]中的每个元素进行赋值
     
     //入队
     q.push(a[0]);
     q.push(a[1]);
     q.push(a[2]);
     q.push(a[3]);
     q.push(a[4]);

      printf("队列大小为: ",q.size());


     //判断只要队列不为空，查看队头，查看队尾，出队
     while(!q.empty)//队列不为空时
     {    printf("%d",q.front());//查看队首   
          printf("%d",q.back());//查看队尾
          q.pop();//出队
          printf("队列大小为: ",q.size());//查看队列大小
     }
}

int main()
{    test11()
     return 0;
}


//PS:queue与vector不同，不提供迭代器，更不支持随机访问



/*常用接口总结:
push-----入队
pop------出队
front-------返回队首元素
back--------返回队尾元素
empty-------判断队列是否为空
size--------返回队列的大小
*/