数据结构——队列

#include <stdio.h>
#include <malloc.h>

typedef char ElemType;
typedef struct Node{   //队列中的结点
	ElemType data;
	struct Node *next;
} QNode;

typedef struct{      
	QNode *front;     //指向队列头
	QNode *rear;      //指向队列尾
}Queue;

void Init(Queue *&q){
	q=(Queue *)malloc(sizeof(Queue));
	q->front=q->rear=NULL;
}

void Destroy(Queue *&q){
    QNode *p=q->front,*r;
	while(p!=NULL){
		r=p->next;
		free(p);
		p=r;
	}
	free(q);
}

int Length(Queue *q){
	int n=0;
	QNode *p=q->front;
	while (p!=NULL){
		n++;
		p=p->next;
	}
	return n;
}

int isEmpty(Queue *q){
	return q->rear==NULL?1:0;
}

void Enter(Queue *&q,ElemType e){
	QNode *s;
    s=(QNode *)malloc(sizeof(QNode));
	s->data=e;
	s->next=NULL;
    if (q->rear==NULL)		//若链队为空,则新结点是队首结点又是队尾结点
		q->front=q->rear=s;
	else{
		q->rear->next=s;  //将s链到队尾
		q->rear=s;
	}
}

int Leave(Queue *&q,ElemType &e){
	QNode *t;
	if (q->rear==NULL)		//队列为空
		return 0;
	if (q->front==q->rear){  //队列只有一个结点
		t=q->front;
		q->front=q->rear=NULL;
	}
	else{					//队列有多个结点
		t=q->front;
		q->front=q->front->next;
	}
	e=t->data;
    free(t);
	return 1;
}

void main()
{
	ElemType e;
	Queue *q;
	printf("(1)初始化链队q\n");
	Init(q);
	printf("(2)依次进链队元素a,b,c\n");
	Enter(q,'a');
	Enter(q,'b');
	Enter(q,'c');
	printf("(3)链队为%s\n",(isEmpty(q)?"空":"非空"));
	if (Leave(q,e)==0) 
		printf("队空,不能出队\n");
	else
		printf("(4)出队一个元素%c\n",e);
	printf("(5)链队q的元素个数:%d\n",Length(q));
	printf("(6)依次进链队元素d,e,f\n");
	Enter(q,'d');
	Enter(q,'e');
	Enter(q,'f');
	printf("(7)链队q的元素个数:%d\n",Length(q));
	printf("(8)出链队序列:");
	while (!isEmpty(q))
	{	Leave(q,e);
		printf("%c ",e);
	}
	printf("\n");
	printf("(9)释放链队\n");
	Destroy(q);
}

 运行结果：

(1)初始化链队q
(2)依次进链队元素a,b,c
(3)链队为非空
(4)出队一个元素a
(5)链队q的元素个数:2
(6)依次进链队元素d,e,f
(7)链队q的元素个数:5
(8)出链队序列:b c d e f
(9)释放链队