3-5 链式队列

若用户无法估计所用队列的长度，则宜采用链队列

链队列定义

typedef struct Qnode {
	QElemType data;
	struct Qnode *next;
}Qnode, *QueuePtr

因为链队中需要2个指针（头指针和尾指针），我们为2个指针定义一个结构体

typedef struct LinkQueue{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue

【算法】链队初始化

Status InitQueue(LinkQueue &Q) {
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(Qnode));
	if(!Q.front)
		exit(OVERFLOW);
	Q.front->next = NULL;
	return OK;
}

【算法】销毁链队列

算法思想：从头结点开始，依次释放所有结点

Status DestroyQueue(LinkQueue &Q) {
	while(Q.front) {
		p = Q.front->next; //或者可以用尾指针rear代替p，节省内存空间
		free(Q.front);
		Q.front = p;
	}
	return OK;
}

【算法】将元素e入队

  Status EnQueue(LinkQueue &Q, QElemType e) {
	p = (QueuePtr)malloc(sizeof(Qnode));
	if(!p)
		return ERROR;
	p->data = e;
	p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;
	return OK;
}

【算法】链队出队

Status DeQueue(LinkQueue &Q, QElemType &e) {
	if(Q.front == Q.rear) 
		return ERROR;
	p = Q.front->next;
	e = p->data;
	Q.front->next = p->next;
	if(Q.rear == p) //如果队列中仅有一结点，要将尾指针指向头结点
		Q.rear = Q.front;
	free(p);
	return OK;
}

【算法】求队列头元素

Status GetHead(LinkQueue Q, QElemType &e) {
	if(Q.front == Q.rear)
		return ERROR;
	e = Q.front->next->data;
	return OK;
}