数据结构--栈（FILO）和队列（FIFO）的应用

╰+攻爆jí腚メ 2022-06-02 06:13 301阅读 0赞

*  纸牌游戏：***游戏的规则*** 是这样的：将一副扑克牌平均分成两份，每人拿一份。小哼先拿出手中的第一张扑克牌放在桌上，然后小哈也拿出手中的第一张扑克牌，并放在小哼刚打出的扑克牌的上面，就像这样两人交替出牌。出牌时，如果某人打出的牌与桌上某张牌的牌面相同，即可将两张相同的牌及其中间所夹的牌全部取走，并依次放到自己手中牌的末尾。当任意一人 手中的牌全部出完时，游戏结束，对手获胜。
 *  假如游戏开始时，小哼手中有 6张牌，顺序为 2 4 1 2 5 6，小哈手中也有 6张牌，顺序 为 3 1 3 5 6 4，终谁会获胜呢？
 *  这恰好对应队列的两个操作，出牌就是出队，赢牌就是入队。小哈的操作和小哼是一样的。而桌子就是一个栈，每打出一张牌放到桌上就相当于入栈。当有人赢牌的时候，依次将牌从桌上拿走，这就相当于出栈。那如何解决赢牌的问题呢？赢牌的规则是：如果某人打出的牌与桌上的某张牌相同，即可将两张牌以及中间所夹的牌全部取走。
 *  代码：

#include<iostream>
     #include<cstring>
     #include<stdio.h>
    using namespace std;
    struct queue{
        int data[1000];
        int head;
        int tail;
    };
    struct stack{
        int data[100];
        int top;
    };
    int main(){
        struct queue q1,q2;
        struct stack s;
        q1.head=1,q1.tail=1;
        q2.head=1,q2.tail=1;
        s.top=0;
        int t;
        for(int i=1;i<=6;i++){
            cin>>q1.data[q1.tail];
            q1.tail++;
        }
        for(int i=1;i<=6;i++){
            cin>>q2.data[q2.tail];
            q2.tail++;
        }
        int book[12];
        for(int i=0;i<=9;i++){
            book[i]=0;
        }
        while(q1.head<q1.tail&&q2.head<q2.tail){
             t=q1.data[q1.head];
            if(book[t]==0){
                q1.head++;
                s.top++;
                s.data[s.top]=t;
                book[t]=1;
            }
            else{
                q1.head++;
                q1.data[q1.tail]=t;
                q1.tail++;
                while(s.data[s.top]!=t){
                    q1.data[q1.tail]=s.data[s.top];
                    book[s.data[s.top]]=0;
                    s.top--;
                    q1.tail++;
                }
            }
            t=q2.data[q2.head];
            if(book[t]==0){
                q2.head++;
                s.top++;
                s.data[s.top]=t;
                book[t]=1;
            }else{
               q2.head++;
               q2.data[q2.tail]=t;
               q2.tail++;
               while(s.data[s.top]!=t){
                    book[s.data[s.top]]=0;
                    q2.data[q2.tail]=s.data[s.top];
                    q2.tail++;
                      s.top--;
               }
            }
            }
          if(q2.head==q2.tail){
            cout<<"小哼win\n"<<endl;
            cout<<"小哼当前的牌是"<<endl;
            for(int i=q1.head;i <=q1.tail-1;i++){
                cout<<" "<<q1.data[i];
            }
            if(s.top>0){
                cout<<"\n 桌上的牌是"<<endl;
                for(int i=1;i<=s.top;i++){
                    cout<<" "<<s.data[i];
                }
            }else
            cout<<"桌子上没牌啦！"<<endl;
        }else{
            cout<<"小哈win\n"<<endl;
                cout<<"小哈当前的牌是"<<endl;
                for(int i=q2.head;i<=q2.tail-1;i++){
                    cout<<" "<<q2.data[i];
                }
                if(s.top>0){
                    cout<<"\n 桌上的牌是"<<endl;
                    for(int i=1;i<=s.top;i++){
                        cout<<" "<<s.data[i];
                    }
                }else
                cout<<"桌子上没牌啦！"<<endl;
        }
        return 0;
    }