小猫钓鱼–栈和队列的使用

思路

q1和q2手中的牌分别是一个队列，桌面上的牌是一个栈，用book数组标记桌面上出现的牌。

代码

#include <stdio.h>

struct queue
{
    int data[];
    int head;
    int tail;
};

struct stack
{
    int data[];
    int top;
};

int main()
{
    int a[] = {, , , , , };
    int b[] = {, , , , , };
    int book[];
    struct queue q1, q2;
    struct stack s;
    int i, t, flag;

    q1.head = ; q1.tail = 0;
    q2.head = ; q2.tail = 0;
    s.top = -;

    for (i = ; i< 10; i++) {
        book[i] = ;
    }

    for (i = ; i < 6; ++i) {
        q1.data[q1.tail] = a[i];
        q1.tail++;

        q2.data[q2.tail] = b[i];
        q2.tail++;
    }

    while (q1.head < q1.tail && q2.head < q2.tail) {
        t = q1.data[q1.head];
        printf("q1: %d\n", t);

        if (book[t] == ) {
            q1.head++;
            s.top++;
            s.data[s.top] = t;
            book[t] = ;
        } else {
            q1.head++;
            q1.data[q1.tail] = t;
            q1.tail++;
            while(s.data[s.top] != t) {
                book[s.data[s.top]] = ;
                q1.data[q1.tail] = s.data[s.top];
                q1.tail++;
                s.top--;
            }
        }

        t = q2.data[q2.head];
        printf("q2: %d\n", t);

        if (book[t] == ) {
            q2.head++;
            s.top++;
            s.data[s.top] = t;
            book[t] = ;
        } else {
            q2.head++;
            q2.data[q2.tail] = t;
            q2.tail++;
            while(s.data[s.top] != t) {
                book[s.data[s.top]] = ;
                q2.data[q2.tail] = s.data[s.top];
                q2.tail++;
                s.top--;
            }
        }
    }

    if (q1.head == q1.tail) {
        printf("q2 \n");
        for (i = q2.head; i < q2.tail; ++i) {
            printf("%d ", q2.data[i]);
        }
    }

    if (q2.head == q2.tail) {
        printf("q1 \n");
        for (i = q1.head; i < q1.tail; ++i) {
            printf("%d ", q1.data[i]);
        }
    }

    if (s.top > ) {
        printf("\n桌面上的牌是 ");
        for (i = ; i <= s.top; ++i) {
            printf("%d ", s.data[i]);
        }
    } else {
        printf("\n桌上已经没有牌了");
    }

    return ;
}
           

结果：

5 6 2 3 1 4 6 5 
桌面上的牌是 2 1 3 4
           

python 代码：

q1 = [, , , , , ]
q2 = [, , , , , ]

book = {}
s = []

while len(q1) != and len(q2) !=  :
    t = q1.pop()
    print("q1: %d" % t)

    if t not in book.keys() or book[t] == :
        s.append(t)
        book[t] = 
    else:
        q1.append(t)
        while s[-] != t:
            top = s[-]
            q1.append(top)
            s.pop()
            book[top] = 

    t = q2.pop()
    print("q2: %d" % t)

    if t not in book.keys() or book[t] == :
        s.append(t)
        book[t] = 
    else:
        q2.append(t)
        while s[-] != t:
            top = s[-]
            q2.append(top)
            s.pop()
            book[top] = 

if len(q1) == :
    print("q2 win")
    print(q2)
else:
    print("q1 win")
    print(q1)

if len(s) != :
    print("table")
    print(s)
else:
    print("not table")