1.洗牌在生活中十分常见，现在需要写一个程序模拟洗牌的过程。 现在需要洗2n张牌，从上到下依次是第1张，第2张，第3张一直到第2n张。首先，我们把这2n张牌分成两堆，左手拿着第1张到第n张（上半堆），右手拿着第n+1张到第2n张（下半堆）。接着就开始洗牌的过程，先放下右手的最后一张牌，再放下左手的最后一张牌，接着放下右手的倒数第二张牌，再放下左手的倒数第二张牌，直到最后放下左手的第一张牌。接着把牌合并起来就可以了。 例如有6张牌，最开始牌的序列是1,2,3,4,5,6。首先分成两组，左手拿着1,2,3；右手拿着4,5,6。在洗牌过程中按顺序放下了6,3,5,2,4,1。把这六张牌再次合成一组牌之后，我们按照从上往下的顺序看这组牌，就变成了序列1,4,2,5,3,6。 现在给出一个原始牌组，请输出这副牌洗牌k次之后从上往下的序列。
思路使用栈（这里没有用到STL 容器）
#include<iostream>2. 小明同学把1到n这n个数字按照一定的顺序放入了一个队列Q中。现在他对队列Q执行了如下程序：
#include<string.h>
#include<ctype.h>
using namespace std;
int stack[200+10];
int stack1[100+10];
int stack2[100+10];
int length=0;
int length1=0;
int length2=0;
int main()
{
int T;
int n,k;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=0;i<2*n;i++)
{scanf("%d",&stack[2*n-1-i]);}
length=2*n;
while(k--)
{//分成两堆
length1=0;
length2=0;
for(int i=0;i<n;i++)
stack1[length1++]=stack[--length];//左手
for(int i=n;i<2*n;i++)
stack2[length2++]=stack[--length];//右手
//洗牌
length=0;
while(length1>0 && length2>0)
{
stack[length++]=stack2[--length2];//长度先减一，再出栈
stack[length++]=stack1[--length1];
}
//和牌
}
//输出栈(自顶向下)
while(length>1)
{
printf("%d ",stack[--length]);
}
printf("%d\n",stack[--length]);
}
//system("pause");
return 0;
}
while(!Q.empty()) //队列不空，执行循环做取出队头的值操作的时候，并不弹出当前队头。
{
int x=Q.front(); //取出当前队头的值x
Q.pop(); //弹出当前队头
Q.push(x); //把x放入队尾
x = Q.front(); //取出这时候队头的值
printf("%d\n",x); //输出x
Q.pop(); //弹出这时候的队头
}
小明同学发现，这段程序恰好按顺序输出了1,2,3,...,n。现在小明想让你构造出原始的队列，你能做到吗？
解题思路：把该过程逆向（使用双端队列实现）
#include<iostream>
#include<string.h>
#include<ctype.h>
using namespace std;
#include<deque>
int main()
{
int T;
int n;
scanf("%d",&T);
while(T--)
{
deque<int> q;
scanf("%d",&n);
while(n)
{
q.push_front(n--);
int t=q.back();
q.push_front(t);
q.pop_back();
}
//从队头到队尾，依次输出
while(q.size()>1)
{cout<<q.front()<<" ";
q.pop_front();
}
cout<<q.front()<<endl;
}
//system("pause");
return 0;
}
3. 已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号1开始报数，数到k的那个人出列；他的下一个人又从1开始报数，数到k的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
例如n=10，k=3时，输出的出列顺序是3，6，9，2，7，1，8，5，10，4。
解题思路，典型的使用链表实现。STL中链表实现方式有多种，这里使用vector
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> a; //定义向量对象a
int n,k,x=0;
cout<<"请输入总人数n和出环位置k："<<endl;
cin>>n>>k;
for(int i=0; i<n; i++)
{
a.push_back(i+1); //初始化向量对象a，依次将i+1插入尾部
}
while(a.size()) //当向量中元素个数不为0
{
x = (x+k-1) % a.size(); //计算出环位置
cout<<a[x]<<" ";
a.erase(a.begin()+x); //在向量中删除此元素
}
system("pause");
return 0;
}
看到这里，读者应该能发现，在程序设计过程中使用现成的数据结构实现，能减少程序设计的麻烦，算法思路更加明确
这里做一个简单的总结，总结程序设计构成中常用的STL
1）。栈 stack
- #include <stack> //引入栈
- 在STL中栈一共就5个常用操作函数（top()、push()、pop()、 size()、empty() ），很好记的。
入栈，如例：s.push(x);
出栈，如例：s.pop();注意，出栈操作只是删除栈顶元素，并不返回该元素。
访问栈顶，如例：s.top()
判断栈空，如例：s.empty()，当栈空时，返回true。
访问栈中的元素个数，如例：s.size()
2）队列
定义一个queue的变量 queue<Type> M //例如 queue <int> Q,q,、、
查看是否为空范例 M.empty() 是的话返回1，不是返回0;
从已有元素后面增加元素 M.push()
输出现有元素的个数 M.size()
显示第一个元素 M.front()
显示最后一个元素 M.back()
清除第一个元素 M.pop()
3）双端队列
使用deque容器之前必须加上<deque>头文件：#include<deuqe>;
deque<Elem> c 创建一个空的deque；
c.front()返回c容器的第一个元素
c.back()返回c容器的最后一个元素
c.size()返回c容器中实际拥有的元素个数
c.push_back(num)在末尾位置插入元素
c.pop_back()删除末尾位置的元素
c.push_front(num)在开头位置插入元素
c.pop_front()删除开头位置的元素
另外常用的还有：c.insert(pos,num)在pos位置插入元素num
c.erase(pos)删除pos位置的元素
下面看一道经典的约瑟夫环的题
问题描述：
已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号1开始报数，数到k的那个人出列；他的下一个人又从1开始报数，数到k的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
例如n=10，k=3时，输出的出列顺序是3，6，9，2，7，1，8，5，10，4。
#include<iostream>
#include<deque>
using namespace std;
int main()
{
deque<int> a; //定义向量对象a
int n,k,x=0;
cout<<"请输入总人数n和出环位置k："<<endl;
cin>>n>>k;
for(int i=0; i<n; i++)
{
a.push_back(i+1); //初始化向量对象a，依次将i+1插入尾部
}
while(a.size()) //当向量中元素个数不为0
{
x = (x+k-1) % a.size(); //计算出环位置
cout<<a[x]<<" ";
a.erase(a.begin()+x); //在向量中删除此元素
}
system("pause");
return 0;
}