首页 > 代码库 > 手工数据结构系列-C语言模拟队列 hdu1276

手工数据结构系列-C语言模拟队列 hdu1276

#include <stdio.h>
#include <stdlib.h>
#define init_size 1000
typedef struct {
    int head,tail,size,__size,*seq;
}Queue;
typedef Queue* Q_P;
void init(Q_P q){
    q->head=q->tail=0;q->__size=init_size;q->size=0;
    q->seq=(int*)malloc(init_size*sizeof(Queue));
}
void push(Q_P q,int ele){
    if(q->tail+1>=q->__size){
        q->seq=(int*)realloc(q->seq,sizeof(int)*(q->__size*=2));
    }
    q->seq[q->tail++]=ele;
    q->size++;
    //debug
    // printf("PUSH %d SIZE:%d\n",q->seq[q->tail-1],q->size);
}
int empty(Q_P q){
    if(q->head==q->tail) return 1;
    return 0;
}
void pop(Q_P q){
    if(!empty(q)) q->head++,q->size--;
    // printf("POP SIZE:%d\n",q->size);
}
int front(Q_P q){
    if(!empty(q)) return q->seq[q->head];
}
void print(Q_P q){
    printf("%d",front(q));pop(q);
    while(q->size!=0) {printf(" %d",front(q));pop(q);}
    printf("\n");
}
void test(){
    int i;
    Q_P q=(Q_P)malloc(sizeof(Queue));
    init(q);
    for(i=0;i<10;++i) {push(q,i);}
    print(q);    
}
void solve(){
    int n,i,T;scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        Q_P a=(Q_P)malloc(sizeof(Queue)),b=(Q_P)malloc(sizeof(Queue));//或者Queue *a,*b;
        init(a);init(b);
        for(i=1;i<=n;++i){
                push(a,i);push(b,i);
        }
        // print(a);print(b);
        //print the Queue ,but at the same time the action does clear the queue
        if(a->size!=0&&a->size<=3) print(a);
        int cnt=0;
        while(a->size>3||b->size>3){
            int k;
            for(k=2;k<=3;++k){
                cnt++;
                if(cnt&1){
                    while(b->size!=0) pop(b);
                    int cc=0;while(a->size!=0) {if(++cc%k!=0) push(b,front(a));pop(a);}
                }
                else{
                    while(a->size!=0) pop(a);
                    int cc=0;while(b->size!=0) {if(++cc%k!=0) push(a,front(b));pop(b);}
                }
                if(a->size!=0&&a->size<=3) {print(a);break;}
                if(b->size!=0&&b->size<=3) {print(b);break;}
            }
        }
    } 
}

int main(){
    // test();
    solve();
    return 0;
}

 

手工数据结构系列-C语言模拟队列 hdu1276