约瑟夫环

#include <iostream>
#include <stack>
using namespace std;
struct Node{//定义一个结点
    int data;
    struct  Node* next;
};
int main(){
    int n;
    while(cin>>n){
    Node *head=new Node;//定义个头结点，并使date=1
    head->data=1;
    head->next=NULL;
    Node *p=head;  //定义一个指针p，初始指向头结点  
    stack<int>outCome;//定义一个栈outCome
    for(int i=2;i<=n;i++){
		Node *baby=new Node;//定义新结点baby，按顺序链表将结点都连上去 
        p->next=baby;
        baby->data=i;
        p=baby;
    }
    p->next=head;//将头尾结点连在一起
    p=head;//p指向头结点，表示从头开始数的意思
    Node *mid=p;//定义mid指针，确保mid永远在要删的结点前
    for(int i=1;i<=n;i++){//其实不需要n遍只是确保所有都删了
    	for(int j=1;j<=3;j++){//遇‘三’就删
        	if(j!=3){
        	    mid=p;
        	    p=p->next;
			}
        	else{
            	outCome.push(p->data);//将要删的结点的数据压入栈里
            	mid->next=p->next;//删掉结点
            	p=p->next;  
        	}
    	}
	}
    cout<<outCome.top()<<endl;//输出最上面的数据
	}
    return 0;
}

解题思路

建立循环链表，一到三循环数，遇到‘三’就把此时p所指的点的数据域压入栈中，后删除这个结点。最后输出最上面的栈。

stack用法

c++栈头文件：

#include<stack>
stack<int>haxi;//栈的声明
haxi.empty();//栈空返回true，否则返回false
int x=xiha.size();//返回栈中元素个数
xiha.pop();//移除栈顶元素
xiha.push(10);//将k置于栈顶
t=xiha.top();//返回栈顶元素
stack<int>wuhu;
wuhu.swap(haxi);//交换两个栈内的元素；