Queue コードを書いてみた

C 言語の勉強で Queue (キュー) のプログラムを組んでる友達がいる。

• キュー (コンピュータ) - Wikipedia

先日、「@aka なら、15 分位いで queue のプログラムを書けるよね?」と振られたので、「15 分は無理だけど 1、2 時間で作れると思う」と返した。それで気付いたんだけど、ぼくは Queue のプログラムを書いたことがない。せっかくなので、ちょっと挑戦してみた。

int 型のデータを enqueue/dequeue するだけのプログラム。とってもシンプル。

大雑把なコードを書くのに 30 分。バグ潰しに 1 時間。ブラッシュアップに 1 時間。

ソースコードは gist で管理している。ライセンスは GPL (ってほどのコードでもないけど)。fork はご自由に。

• gist: 83763 - GitHub (queue)

ソースコード

ソースコードも一応貼っておく。C99 のソースコード。gcc でコンパイルする時は、-std=c99 オプションが要る。

queue.h

#ifndef __QUEUE_H__
#define __QUEUE_H__
 
typedef struct node_tt
{
  struct node_tt* prev;
  int n;
} node_t;
 
typedef struct
{
  node_t* head;
  node_t* tail;
} queue_t;
 
queue_t* new_queue(void);
bool enqueue(int n, queue_t* queue);
int dequeue(queue_t* queue);
void del_queue(queue_t* queue);
 
#endif /* __QUEUE_H__ */

queue.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "queue.h"
 
/* ---------------------------------------- *\
Function declaration
\* ---------------------------------------- */
static bool is_empty(queue_t* q);
 
/* ---------------------------------------- *\
Functions
\* ---------------------------------------- */
queue_t* new_queue(void)
{
  queue_t* q = (queue_t*)malloc(sizeof(queue_t));
  if (q == NULL){
    fprintf(stderr, "Allocation Error: queue\n");
    return NULL;
  }
  q->tail = NULL;
  q->head = q->tail;
 
  return q;
}
 
/* Return TRUE if succeeded to malloc NEW node, else return FALSE. */
bool enqueue(int n, queue_t* queue)
{
  node_t* new = (node_t*)malloc(sizeof(node_t));
  if (new == NULL){
    fprintf(stderr, "Allocation Error: node\n");
    return false;
  }
  new->n = n;
  new->prev = NULL;
 
  if (is_empty(queue)){
    queue->tail = new;
  } else {
    queue->head->prev = new;
  }
  queue->head = new;
 
  return true;
}
 
/* Return 0 if queue is empty, else return dequeued value */
int dequeue(queue_t* queue)
{
  node_t* last = queue->tail;
  if (is_empty(queue)){
    fprintf(stderr, "QUEUE is empty\n");
    return 0;
  } else {
    queue->tail = last->prev;
  }
 
  int n = last->n;
  free(last);
  return n;
}
 
void del_queue(queue_t* queue)
{
  if (!is_empty(queue)){
      node_t* last = queue->tail;
      queue->tail = last->prev;
      free(last);
  }
  free(queue);
}
 
static bool is_empty(queue_t* q)
{
  return q->tail == NULL;
}
 

#ifdef DEBUG
/* ---------------------------------------- */
int main(void)
{
  queue_t* q = new_queue();
 
  enqueue(5, q);
  enqueue(4, q);
  enqueue(3, q);
  printf("%d\n", dequeue(q));
  printf("%d\n", dequeue(q));
  printf("%d\n", dequeue(q));
  // queue is empty
 
  // dequeue error check when queue is empty
  printf("%d\n", dequeue(q));
 
  enqueue(2, q);
  printf("%d\n", dequeue(q));
  // queue is empty
 
  del_queue(q);
  return 0;
}
#endif /* DEBUG */