数据结构复习(队列)

链栈

#include <stdio.h>
#include <stdlib.h>

typedef struct QNode{
	int data;
	struct QNode *next;
}QNode;

typedef struct
{
	QNode *front;
	QNode *rear;
}LiQueue;

//队尾入队，队头出队
void initLiQueue(LiQueue *&lqu){
	lqu = (LiQueue *)malloc(sizeof(LiQueue));
	lqu->front = lqu->rear = NULL;
} 
 
int isQueueEmpty(LiQueue *lqu){
	if(lqu->front == NULL || lqu->rear == NULL)
		return 1;
	else
		return 0; 
}

void enQueue(LiQueue *&lqu, int x){
	QNode *node;
	node = (QNode *)malloc(sizeof(QNode));
	node->data = x;
	node->next = NULL;
	//如果队列为空，插入的结点为首结点，那么队头和队尾都指向这个新插入的首结点 
	if(lqu->rear == NULL)
		lqu->front = lqu->rear = node;
	else
	{
		//否则的话，这个结点插入到队尾所指的结点的后面，并把队尾指针指向新结点 
		lqu->rear->next = node;
		lqu->rear = node;
	}
}

int deQueue(LiQueue *&lqu, int &x){
	QNode *p;
	//如果队尾指针为空，表明队列为空，这时不能再删除 
	if(lqu->rear == NULL){
		return 0;
	}
	else
	{
		//否则的话，队列不为空，将p指向队头所指的元素，准备free(p) 
		p = lqu->front;
	}
	//队头和队尾都指向同一个对象，这时要么队列为空，要么队列只有一个元素，
	//但是前一步已经判断完队列不为空了，这时只能是队列中只有一个元素 
	if(lqu->front == lqu->rear){
		//队列中只有一个元素，删掉这个元素队列就为空了，需要将队头和队尾指针同时置空 
		lqu->front=lqu->rear=NULL;
	}else{
		//队列不为空，且不只有一个元素，将队头指向目前队头所指的元素的下一个元素，逻辑上删掉了前一个队头 
		lqu->front = lqu->front->next;
	}
	x=p->data;
	//释放p所占的内存空间，不可少 
	free(p);
	return 1;
}

int main(){
	LiQueue *liQueue;
	initLiQueue(liQueue);
	enQueue(liQueue, 77);
	enQueue(liQueue, 99);
	enQueue(liQueue, 88);
	
	int elem;
	if(deQueue(liQueue, elem)){
		printf("删除成功，元素为:%d\n", elem);
	}else{
		printf("删除失败\n");
	}
	if(deQueue(liQueue, elem)){
		printf("删除成功，元素为:%d\n", elem);
	}else{
		printf("删除失败\n");
	}
    return 0;
}