simple idea

会社でのC言語研修の問題として、定番だけどキュー&スタックを考えた。
キューとスタックはよく似ていて、違うのはデータの取出す順序が先に入れたものから取出す(キュー)のか、後から入れたものから取出す(スタック)ぐらい。
そこで、キューとスタックをまとめてあつかえるプログラムを作ってみた。きちんとエラー処理はしていないので、もし使うのであれば、その辺はきちんと作る必要がある。

《que.h》

#ifndef _QUE_H_
#define _QUE_H_

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

#define         GET_QUE         1
#define         GET_STACK       0

/* structuers   */
typedef struct que {
struct  que     *prev;
struct  que     *next;
        void    *data;
} QUE;

/* function prototype   */
int     que_init();
int     que_enque(void *data);
int     que_deque_first(void **data);
int     que_deque_last(void **data);

#endif  /* _QUE_H_      */

《que.c》

#include        "que.h"

static  QUE     root;

static  int     que_deque(void **data, int get_type);

int     que_init()
{
        memset (&root, 0, sizeof(root));
        root.prev = &root;
        root.next = &root;

        return(0);
}

int     que_enque(void *data)
{
        QUE     *p      = NULL;
        QUE     *last   = NULL;

        p = (QUE *) malloc (sizeof(QUE));

        if (root.next == &root || root.prev == &root) {
                root.next = p;
                root.prev = p;
                p->prev = &root;
        } else {
                last = root.prev;
                last->next = p;
                root.prev = p;
                p->prev = last;
        }

        p->next = &root;
        p->data = data;

        return(0);
}

int     que_deque_first(void **data)
{
        int     status;

        if (root.next == &root) {
                return(1);
        }

        status = que_deque(data, GET_QUE);

        return(status);
}

int     que_deque_last(void **data)
{
        int     status;

        if (root.prev == &root) {
                return(1);
        }

        status = que_deque(data, GET_STACK);

        return(status);
}

static  int     que_deque(void **data, int get_type)
{
        QUE     *p      = NULL;

        if (get_type) {
                p = root.next;
                p->next->prev = p->prev;
                root.next = p->next;
        } else {
                p = root.prev;
                p->prev->next = p->next;
                root.prev = p->prev;
        }

        *data = p->data;
        free(p);

        return(0);
}

que_deque()内で、キューまたはスタックの切替えを行っている。使用する場合は、ラッパーであるque_deque_first()、que_deque_last()でキューまたはスタックを選択する。