キューをCで

長さがあらかじめ分かっていない配列を含む構造体でも、1度にメモリ確保できるというので（これ）、今度はスタックじゃなくてキューを作ってみた。キューはリング状にしてデキュー時のスライドという無駄な処理をなくすのが常套手段のようだけど、ひとまず効率の悪い素朴なやり方で作ってみた。

#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int len;
  int index;
  int line[0];
} Que;

int checkQue(Que *q){
  if(q->len == q->index){
    return -1; // full
  }else if(q->index == 0){
    return 2; // empty
  }else{
    return 0;
  }
}

int showQue(Que *q){
  int i;
  for(i = 0; i < q->len; i++)
    printf("que[%2d]: %3d\n", i, q->line[i]);
}

int que(Que *q, int i){
  if(checkQue(q) != -1){
    q->line[q->index++] = i;
  }else{
    puts("can't que any more");
    return -1;
  }
}

int deque(Que *q, int *i){
  int slot;
  if(checkQue(q) != 2){
    *i = q->line[0];
    for(slot = 0; slot < q->index; slot++)
      q->line[slot] = q->line[slot + 1];
    q->index--;
    return 0;
  }else{
    puts("que is empty");
    return -1;
  }
}

Que *alloc(int l){

  Que *q = (Que *) malloc(sizeof(Que) + (l * 4));
  if(q == NULL) exit(1);
  q->index = 0;
  q->len = l;

  return q;
}

int main(int argc, char *argv[]){
  int i,j;
  int l = atoi(argv[1]);

  Que *q = alloc(l);

  for(i = 0; i < l; i++)
    que(q, i*2);
  
  deque(q,&i);  que(q,i);
  deque(q,&i);  que(q,i);

  showQue(q);
  free(q);
}

実行結果は、

$ gcc -o que que.c ; ./que 10
que[ 0]:   4
que[ 1]:   6
que[ 2]:   8
que[ 3]:  10
que[ 4]:  12
que[ 5]:  14
que[ 6]:  16
que[ 7]:  18
que[ 8]:   0
que[ 9]:   2

と、動いてる。