一、第二章目录

第1节、第2节、第4节的内容在数据结构的栈、队列、链表的博客中有更详细的介绍。

二、实现简单纸牌游戏

游戏规则:两人轮流出牌。甲出第一张牌,乙也出第一张牌并放在甲打出的牌的上面。若打出的牌与桌上某张牌相同,可将桌上这两张牌及其中间所有牌取走放入自己牌组。直到一方牌全出完,另一方获胜。

分析:两人的出牌从第一张牌出,而放入牌是放入牌组的最后面,可以看作两个队列;桌面上的牌放的时候放在最上面,取的时候也是从最上面取,可以看作一个栈。因此我们可以用两个队列、一个栈来模拟该游戏。

#define MaxSize 50
typedef struct {     //定义栈的结构体
    int data[MaxSize];	//存放栈中的数据元素
    int top;	//栈顶指针,即栈顶元素在data数组中的下标
} SqStack;

typedef struct {     //定义队列的结构体
    int data[MaxSize];    //存放队列中的数据元素
    int front, rear;        //队头和队尾指针
} SqQueue;

假设甲的牌为2 4 1 2 5 6,乙的牌为3 1 3 5 6 4,这里数组的大小MaxSize设成12就够了。

  • 设甲为队列A,乙为队列B。循环将两个队列的元素入队
SqQueue *A, *B;            //定义甲为队列A,乙为队列B
InitQueue(A); InitQueue(B); //将两个队列初始化
int a[6] = {2,4,1,2,5,6};  //甲的牌为241256
int b[6] = {3,1,3,5,6,4};  //乙的牌为313564
for(int i=0;i<6;i++) {
    enQueue(A, a[i]);    //循环将甲的牌入队
    enQueue(B, b[i]);    //循环将乙的牌入队
}
  • 设栈S来保存桌面上的牌
SqStack *S;        //栈L来保存桌面上的牌
InitStack(S);   //初始化栈
  • 出牌:A、B分别出队+进栈
int e1,e2;      //分别用来保存A、B出队元素
deQueue(A,e1);    //甲出牌,出的牌进栈
Push(S,e1);
deQueue(B,e2);    //乙出牌,出的牌进栈
Push(S,e2);
  • 出牌后判断:1.是否有一方队空,说明他出完牌,输了
if(QueueEmpty(A)) printf("甲出完牌了,乙获胜");
if(QueueEmpty(B)) printf("乙出完牌了,甲获胜");
  • 出牌后判断:2.出的牌是否是桌面上牌已经有的,有的话将两副牌及中间所有的牌拿走(出栈+入队)。
  • 这里遇到了个问题,如何判断栈L中是否已经有这个数?用遍历的话效率太低,我们用上一章学的桶排序的思想,设一个数组book[10],先初始化为0,然后每次入栈的时候,给相应的book[e] += 1,就能很方便记录下栈里的所有元素了。
for(int i=0;i<9;i++)
        book[i] = 0;

deQueue(A,e1);      //甲出牌
if(book[e1] != 0){  //栈内没有e1,则进栈
    Push(S,e1);
    book[e1] += 1;
}
else{               //栈内已有e1,则将e1元素及其之后的元素出栈+入队
    enQueue(A, e1);
    int e = -1;       //e用来保存栈顶元素
    while (e != e1) {
    Pop(S, e);
    book[e] -= 1;
    enQueue(A, e);
    printf("甲拿走牌:%d,", e);
}
    

//乙出牌时也一样处理
  • 将出牌过程用循环处理
//出牌
for (int i = 0; i < 100; i++) {
    printf("第%d次出牌:", i + 1);
    int e1, e2;      //分别用来保存A、B出队元素

    //甲出牌
    deQueue(A, e1);    
    printf("甲出的是%d。", e1);
    if (QueueEmpty(A)) {
        printf("甲出完牌了,乙获胜。");
        break;
    }
    if (book[e1] == 0) {       //栈内没有e1,则进栈
        Push(S, e1);
        book[e1] += 1;
    } else {                    //栈内已有e1,则将e1元素及其之后的元素出栈+入队
        enQueue(A, e1);
        int e = -1;       //e用来保存栈顶元素
        while (e != e1) {
            Pop(S, e);
            book[e] -= 1;
            enQueue(A, e);
            printf("甲拿走牌:%d,", e);
        }
    }


    //乙出牌
    deQueue(B, e2);    
    printf("乙出的是%d。", e2);
    if (QueueEmpty(B)) {
        printf("乙出完牌了,甲获胜。");
        break;
    }
    if (book[e2] == 0) {       //栈内没有e2,则进栈
        Push(S, e2);
        book[e2] += 1;
    } else {                    //栈内已有e2,则将e2元素及其之后的元素出栈+入队
        enQueue(B, e2);
        int e = -1;          //e用来保存栈顶元素
        while (e != e2) {
            Pop(S, e);
            book[e] -= 1;
            enQueue(A, e);
            printf("乙拿走牌:%d,", e);
        }
    }
    printf("\n");
}

总代码:

#include <iostream>

#define MaxSize 50

typedef int ElemType;
typedef struct {     //定义栈的结构体
    int data[MaxSize];    //存放栈中的数据元素
    int top;    //栈顶指针,即栈顶元素在data数组中的下标
} SqStack;

typedef struct {     //定义队列的结构体
    int data[MaxSize];    //存放队列中的数据元素
    int front, rear;        //队头和队尾指针
} SqQueue;

//初始化顺序栈
void InitStack(SqStack *&s) {
    s = (SqStack *) malloc(sizeof(SqStack));
    s->top = -1;
}

//销毁顺序栈
void DestroyStack(SqStack *&s) {
    free(s);
}

//判断栈是否为空
bool StackEmpty(SqStack *s) {
    return (s->top == -1);
}

//进栈
bool Push(SqStack *&s, ElemType e) {
    if (s->top == MaxSize - 1)    //溢出栈返回false
        return false;
    s->top++;            //栈顶指针增1
    s->data[s->top] = e;        //元素e放在栈顶指针处
    return true;
}

//入栈
bool Pop(SqStack *&s, ElemType &e) {
    if (s->top == -1)        //溢出栈返回false
        return false;
    e = s->data[s->top];        //将栈顶元素赋给e
    s->top--;            //栈顶指针减1
    return true;
}

//取栈顶元素
bool GetTop(SqStack *s, ElemType &e) {
    if (s->top == -1)        //栈满的情况,即栈上溢出
        return false;
    e = s->data[s->top];        //将栈顶元素赋给e
    return true;
}


//初始化顺序队
void InitQueue(SqQueue *&q) {
    q = (SqQueue *) malloc(sizeof(SqQueue));
    q->front = q->rear = -1;
}

//销毁顺序队
void DestroyQueue(SqQueue *&q) {
    free(q);
}

//判断队列是否为空
bool QueueEmpty(SqQueue *q) {
    return (q->front == q->rear);
}

//进队
bool enQueue(SqQueue *&q, ElemType e) {
    if (q->rear == MaxSize - 1)    //队满上溢出
        return false;
    q->rear++;
    q->data[q->rear] = e;
    return true;
}

//出队
bool deQueue(SqQueue *&q, ElemType &e) {
    if (q->front == q->rear)    //队空
        return false;
    q->front++;
    e = q->data[q->front];
    return true;
}


int main() {
    //生成甲、乙的队列A、B
    SqQueue *A, *B;            //定义甲为队列A,乙为队列B
    InitQueue(A);
    InitQueue(B); //将两个队列初始化
    int a[6] = {2, 4, 1, 2, 5, 6};  //甲的牌为241256
    int b[6] = {3, 1, 3, 5, 6, 4};  //乙的牌为313564
    for (int i = 0; i < 6; i++) {
        enQueue(A, a[i]);    //循环将甲的牌入队
        enQueue(B, b[i]);    //循环将乙的牌入队
    }
    //生成已出牌的栈S
    SqStack *S;        //栈L来保存桌面上的牌
    InitStack(S);   //初始化栈
    //记录栈里有哪些元素
    int book[10];
    for (int i = 0; i < 10; i++)
        book[i] = 0;
    //出牌
    for (int i = 0; i < 100; i++) {
        printf("第%d次出牌:", i + 1);
        int e1, e2;      //分别用来保存A、B出队元素
        //甲出牌
        deQueue(A, e1);    
        printf("甲出的是%d。", e1);
        if (QueueEmpty(A)) {
            printf("甲出完牌了,乙获胜。");
            break;
        }
        if (book[e1] == 0) {       //栈内没有e1,则进栈
            Push(S, e1);
            book[e1] += 1;
        } else {                    //栈内已有e1,则将e1元素及其之后的元素出栈+入队
            enQueue(A, e1);
            int e = -1;       //e用来保存栈顶元素
            while (e != e1) {
                Pop(S, e);
                book[e] -= 1;
                enQueue(A, e);
                printf("甲拿走牌:%d,", e);
            }
        }

        //乙出牌
        deQueue(B, e2);   
        printf("乙出的是%d。", e2);
        if (QueueEmpty(B)) {
            printf("乙出完牌了,甲获胜。");
            break;
        }
        if (book[e2] == 0) {       //栈内没有e2,则进栈
            Push(S, e2);
            book[e2] += 1;
        } else {                    //栈内已有e2,则将e2元素及其之后的元素出栈+入队
            enQueue(B, e2);
            int e = -1;          //e用来保存栈顶元素
            while (e != e2) {
                Pop(S, e);
                book[e] -= 1;
                enQueue(A, e);
                printf("乙拿走牌:%d,", e);
            }
        }
        printf("\n");
    }
}

运行结果: