queue2.c

自己做的常用库和实现的数据结构。public domain.

/* Demo of loop queue, using dynamic array.
 *
 * Written by Cyril Hu ([e-mail]), public domain.
 */
#include "my.h"
#define QUEUE_INIT_SIZE 1
#define QUEUE_INCREMENT 3
#define MAX 7
typedef int ElemType;
typedef struct {
	ElemType e;
} QNode, *QNodePtr;
typedef struct {
	QNodePtr head, rear, front;
	size_t queuesize;
} Queue, *QueuePtr;

void InitQueue(QueuePtr p)
{
	p->rear = p->front = p->head = (QNodePtr)mem('m', (p->queuesize = QUEUE_INIT_SIZE) * sizeof(QNode));
}
void EnQueue(QueuePtr p, ElemType data)
{
	ptrdiff_t r;
	static size_t queuemaxlen = 0;
	QNodePtr x, y;
	if(p->rear == p->front && queuemaxlen++) {
		r = p->rear - p->head;
		p->head = (QNodePtr)mem('r', p->head, (p->queuesize + QUEUE_INCREMENT) * sizeof(QNode));
		x = p->head + p->queuesize - 1 + QUEUE_INCREMENT, y = p->head + p->queuesize - 1;
		p->rear = p->head + r, p->front = p->rear + QUEUE_INCREMENT;
		for(; y >= p->rear; x->e = y->e, --x,--y);
		p->queuesize += QUEUE_INCREMENT;
	}
	p->rear->e = data;
	p->rear == p->head + p->queuesize - 1 ? p->rear = p->head : p->rear++;
}
void DeQueue(QueuePtr p, ElemType *q)
{
	if(p->front != p->rear) {
		*q = p->front->e;
		p->front == p->head + p->queuesize - 1 ? p->front = p->head : p->front++;
	}
}
void DestroyQueue(QueuePtr p)
{
	free(p->head);
}
int main(void)
{
	Queue b, *p = &b;
	int i,a[MAX];
	InitQueue(p);
	for(i=0; i<MAX; i++)
		EnQueue(p, i);
	for(i=0; i<MAX*2; i++)
		DeQueue(p, &a[i]);
	for(i=0; i<MAX; i++)
		printf("%d ", a[i]);
	DestroyQueue(p);
	return 0;
}