/* queue.c */
/* use of bidirectional list for fifo */
#include <stdio.h>
#include <stdlib.h>

struct dlist {
	int d;
	struct dlist *f;	/* forward */
	struct dlist *b;	/* backward */
};

struct queue {
	struct dlist *top, *tail;
	int          length;
};

void qinit(struct queue *x)
{
	x->length = 0;
	x->top = (struct dlist*)malloc(sizeof(struct dlist));
	x->tail = (struct dlist*)malloc(sizeof(struct dlist));
	x->top->f = x->tail; x->top->b = NULL;
	x->tail->f = NULL; x->tail->b = x->top;
}

void qput(struct queue *x, int v)
{
	struct dlist *w;

	w = (struct dlist*)malloc(sizeof(struct dlist));
	w->d = v; w->f = x->top->f; w->b = x->top;
	x->top->f->b = w;
	x->top->f = w;
	x->length++;
}

int qget(struct queue *x)
{
	int    data;

	if (x->length == 0) {
		fprintf(stderr,"queue error!\n");exit(1);
	} else {
		data = x->tail->b->d;
		x->tail->b = x->tail->b->b;
		free(x->tail->b->f);
		x->tail->b->f = x->tail;
		x->length--;
	}
	return(data);
}

int main()
{
	struct queue q;
	int x,y;

	qinit(&q);
	printf("%d %d %ld %ld\n",x,y,(long)q.top->f,(long)q.tail->b);
	qput(&q,1);
	printf("%d %d %ld %ld\n",x,y,(long)q.top->f,(long)q.tail->b);
	qput(&q,2);
	printf("%d %d %ld %ld\n",x,y,(long)q.top->f,(long)q.tail->b);
	x = qget(&q);
	printf("%d %d %ld %ld\n",x,y,(long)q.top->f,(long)q.tail->b);
	y = qget(&q);
	printf("%d %d %ld %ld\n",x,y,(long)q.top->f,(long)q.tail->b);
	return(0);
}