ch3-栈和队列-链式队列的实现

#include <stdio.h>
#include <stdlib.h>
//链表中的结点结构
typedef struct QNode{
	int data;
	struct QNode *next;
}QNode;

//创建带头结点链式队列的函数
QNode *initQueue(){
	//创建一个头结点
	QNode *queue=(QNode*)malloc(sizeof(QNode));
	//对头结点进行初始化
	queue->next=NULL;
	return queue;//头结点后面即将连接一串结点，所以返回头结点就好啦
}

//数据元素入链式队列函数
QNode *enQueue(QNode *rear,int data){
	//1.用节点包裹入队元素
	QNode *enElem=(QNode*)malloc(sizeof(QNode));
	enElem->data=data;
	enElem->next=NULL;
	//2、尾插法建立新节点与rear节点之间的逻辑关系,
	rear->next=enElem;
	//3、rear指向新节点
	rear=enElem;
	return rear;//返回队尾指针raer，因为每次入队都是从队尾处入的
}

//链式队列出队函数
QNode *DeQueue(QNode * top,QNode * rear){
	if(top->next==NULL){
	printf("\n队列为空");
		return rear;
	}
	//创建一个指向待删除(出队)结点的指针p
	QNode *p=top->next;
	printf("%d",p->data);
	top->next=p->next;//头指针指向改为出队结点后面的结点
	//特殊情况：队列在出队后为空，则令rear=top
	if(rear==p){
	rear=top;
	}
	free(p);
}

int main() {
    QNode * queue,*top,*rear;
    queue=top=rear=initQueue();//创建头结点queue
    //向链队列中添加结点，使用尾插法添加的同时，队尾指针需要指向链表的最后一个元素
    rear=enQueue(rear, 1);
    rear=enQueue(rear, 2);
    rear=enQueue(rear, 3);
    rear=enQueue(rear,4);
    //入队完成，所有数据元素开始出队列
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    return 0;
}