栈和队列都是有特殊存入取出规则的容器

栈：先进后出，后进先出

int s[10000]={},b=0,t=0;

s[t++]=x;

t--;

cout<<s[t-1];

if(t==b);

队列：先进先出，后进后出

int q[10000]={},f=0,r=0;//创建队列以及队头队尾

//队尾指向尾元素的下一个位置

q[r++]=x;//入队

f++;//出队

cout<<q[f];//获取队头元素

if(f==r);//判断队空

#include <queue>

queue<类型> 变量名;

queue<int> q;

q.push(x);//入队

q.pop();//出队

cout<<q.front();//队头

q.empty();//队空

int a,b,c;

cin>>a>>b>>c;

queue<int> q1,q2;

for(int i=1;i<=a;i++) q1.push(i);

for(int i=1;i<=b;i++) q2.push(i);

while(c--){

   cout<<q1.front()<<" "<<q2.front()<<endl;

   q1.push(q1.front());

   q2.push(q2.front());

   q1.pop();

   q2.pop();

}

约瑟夫问题

n个人围成一圈，从1号到n号，从头开始查数，每次数到M枪毙

求枪毙顺序或求最后存活编号

通过队列化简环形问题，利用出队入队完成

int i=1;

while(q.size()!=1){

   if(i==m){

       //求枪毙顺序

       q.pop();

       i=1;

   }

   else{

       i++;

       q.push(q.front());

       q.pop();

   }

}

//求存活

约瑟夫变种

n个人围成一圈，从1号到n号，从头开始查数，

枪毙编号是一组数据，每次数到M[i]枪毙

求枪毙顺序或求最后存活编号

//输入n只猴子

int n;

cin>>n;

queue<int> q;

for(int i=1;i<=n;i++) q.push(i);

//保存n只猴子的死亡数字

int m[10000]={};

for(int i=1;i<=n;i++) cin>>m[i];

//开始淘汰

int i=1,num=m[1];

while(q.size()!=1){

   if(i==num){

       //求枪毙顺序

       q.pop();

       num=m[q.front()];

       i=1;

   }

   else{

       i++;

       q.push(q.front());

       q.pop();

   }

}

//求存活

作业：

笔记赶快补上**

围圈报数

下节课：双向队列，循环队列【手写队列时，容易造成空间大量浪费，通过循环队列可以优化】