#38302: C 解法


dadin852@gmail.com (黃少遠)

學校 : 不指定學校
編號 : 207501
來源 : [140.122.105.200]
最後登入時間 :
2023-10-03 15:19:24
e548. 11995 - I Can Guess the Data Structure! -- UVA | From: [211.76.67.200] | 發表日期 : 2023-11-11 10:19

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
    int data;
    struct node* next;
} node;

void priorEnque(node**, int);
void enqueue(node**, node**, int);
void push(node**, int);
int takeOut(node**, node** ptrtail); // NULL for no_tail
void printList(node*);
int main() {
    node* priorhead = NULL;
    node* quehead=NULL, * quetail=NULL;
    node* stackhead = NULL;
    int n, i, op, x;
    char c, pflag, qflag, sflag, sum;
    while (scanf("%d",&n) != EOF) {
        pflag=1; qflag=1; sflag=1;
        for (i=0; i<n; i++) {
            scanf("%d", &op);
            c = getchar();
            if(c==' ') scanf("%d",&x);
            else  x=-1;
            if (op == 1) {
                priorEnque(&priorhead, x);
                enqueue(&quehead, &quetail, x);
                push(&stackhead, x);
            } else if (op == 2) {
                if(takeOut(&priorhead,NULL) != x)
                    pflag = 0;
                if(takeOut(&quehead,&quetail) != x)
                    qflag = 0;
                if(takeOut(&stackhead,NULL) != x)
                    sflag = 0;
            }
        }
        sum = pflag + qflag + sflag;
        if (sum == 0) {
            printf("impossible\n");
        } else if (sum == 1) {
            if (pflag) printf("priority queue\n");
            else if (qflag) printf("queue\n");
            else if (sflag) printf("stack\n");
        } else if (sum > 1) {
            printf("not sure\n");
        }
        while(takeOut(&priorhead,NULL) != -1) {}
        while(takeOut(&quehead,&quetail) != -1) {}
        while(takeOut(&stackhead,NULL) != -1) {}
    }
    return 0;
}
void priorEnque(node** headptr, int x) {
    node* prev, * current, * q;
    q = (node*)malloc(sizeof(node));
    if (q==NULL) return;
    q->data = x;
    if (*headptr==NULL) {
        *headptr=q; q->next=NULL;
    } else {
        prev = NULL;
        current = *headptr;
        while (current != NULL && current->data > x) {
            prev=current; current=current->next;
        }
        if(prev==NULL) *headptr=q;
        else prev->next=q;
        q->next = current;
    }
}
void enqueue(node** headptr, node** tailptr, int x) {
    node* q;
    q = (node*)malloc(sizeof(node));
    if (q==NULL) return;
    q->data=x; q->next=NULL;
    if (*headptr==NULL && *tailptr==NULL) {
        *headptr=q; *tailptr=q;
    } else {
        (*tailptr)->next = q;
        *tailptr = q;
    }
}
void push(node** headptr, int x) {
    node* q;
    q = (node*)malloc(sizeof(node));
    if (q==NULL) return;
    q->data = x;
    q->next = *headptr;
    *headptr = q;
}
int takeOut(node** headptr, node** tailptr) {
    node* p = *headptr;  int x;
    if (*headptr == NULL) {
        // printf("Empty list ");
        return -1;
    } else {
        x = (*headptr)->data;
        *headptr = (*headptr)->next;
        if (*headptr==NULL && tailptr!=NULL) *tailptr=NULL;
        free(p);
        return x;
    }
}
void printList(node* headcpy) {
    while (headcpy != NULL) {
        printf("%d", headcpy->data);
        printf(" -> ");
        headcpy = headcpy->next;
    }
    printf("NULL\n");
}

 
ZeroJudge Forum