目录

一、带头结点

测试

二、不带头结点

测试

一、带头结点

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

typedef struct LinkNode{	// 链队列结点 
	int data;
	struct LinkNode *next; 
}LinkNode; 

typedef struct LinkQueue{	// 链队列 
	LinkNode *front,*rear;	// 队头指针和队尾指针 
}LinkQueue;

// 1、初始化  （带头结点）
bool InitLinkQueue(LinkQueue &Q){
	// 建立头结点刚开始都指向头结点 
	Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));
	// 初始为空 
	Q.front->next = NULL;
	
	return true;
} 

// 2、判断链队列是否为空
bool Empty(LinkQueue Q){
	if(Q.front == Q.rear){
		return true;
	}else{
		return false;
	}
} 

// 3、入队操作 （带头结点）
bool EnQueue(LinkQueue &Q,int e){
	LinkNode *s;
	s= (LinkNode *) malloc(sizeof(LinkNode));
	s->data = e;
	s->next = NULL;		// 插入在队尾 
	Q.rear->next = s;	// 新结点插入到 rear 之后 
	Q.rear = s;			// 修该表尾指针
	return true; 
} 

// 4、出队操作 （带头结点）
bool outQueue(LinkQueue &Q,int &e){
	if(Q.front == Q.rear){	// 空队 
		return false;
	}
	LinkNode *p = Q.front->next;	// p指向要删除的指针 
	e = p->data;
	Q.front->next = p->next;		// 修该头结点的 next 指针域
	if(Q.rear == p){				// 此次是最后一个结点出队 
		Q.rear = Q.front; 			// 修该 rear 指针 
	}
	free(p);
	return true; 
} 

// 5、遍历
void print(LinkQueue Q){
	Q.front = Q.front->next;
	while(Q.front != NULL){
		printf("%d ",Q.front->data);
		Q.front = Q.front->next;
	}
} 


int main(){
	LinkQueue Q;
	InitLinkQueue(Q); 
	EnQueue(Q,120);
	EnQueue(Q,110);
	EnQueue(Q,119);
	EnQueue(Q,114);
	printf("入队顺序是：");
	print(Q); 
	
	
	int e = -1;
	outQueue(Q,e);
	printf("出队元素是：%d\n",e);
	printf("队列剩余元素："); 
	print(Q); 
	
	return 0;
} 

测试

入队顺序是：120 110 119 114 出队元素是：120
队列剩余元素：110 119 114
--------------------------------
Process exited after 0.01241 seconds with return value 0
请按任意键继续. . .

二、不带头结点

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

typedef struct LinkNode{	// 链队列结点 
	int data;
	struct LinkNode *next; 
}LinkNode; 

typedef struct LinkQueue{	// 链队列 
	LinkNode *front,*rear;	// 队头指针和队尾指针 
}LinkQueue;

//  1、初始化
bool InitQueue(LinkQueue &Q) {
	Q.front = NULL;
	Q.rear = NULL;
	return true;
}

// 2、判断队列是否为空
bool isEmpty(LinkQueue Q){
	if(Q.front == NULL){
		return true;
	}else{
		return false;
	}
} 

// 3、入队 （不带头结点）
bool enQueue(LinkQueue &Q,int e){
	LinkNode *s = (LinkNode *) malloc(sizeof(LinkNode));
	s->data = e;
	s->next = NULL;
	if(Q.front == NULL){	// 在空队列中插入第一个元素 
		Q.front = s;
		Q.rear = s;
	}else{
		Q.rear->next = s;	// 新结点插入到 rear 以后 
		Q.rear = s;			// 修该队尾指针 
	}
	return true;
} 

// 4、出队（不带头结点）
bool outqueue(LinkQueue &Q, int &e){
	if(Q.front == NULL){	// 队空 
		return false;
	}	
	LinkNode *p = Q.front;	// p 指针指向本次要出队的结点 
	e = p->data;			// 返回队头元素 
	Q.front = p->next;		// 修该对头指针
	if(Q.rear == p){		// 此次是最后一个结点出队 
		Q.front = NULL;
		Q.rear = NULL;
	} 
	free(p);	// 释放结点空间 
	return true;
}

// 队满 ：因为是链式存储，动态分配空间，一般不会存队满的情况

// 5、遍历
void print(LinkQueue Q){
	while(Q.front != NULL){
		printf("%d ",Q.front->data);
		Q.front = Q.front->next;
	}
}  

int main(){
	LinkQueue Q;
	InitQueue(Q); 
	
	enQueue(Q,120);
	enQueue(Q,110);
	enQueue(Q,119);
	enQueue(Q,114);
	printf("入队顺序是：");
	print(Q); 
	
	
	int e = -1;
	outqueue(Q,e);
	printf("出队元素是：%d\n",e);
	printf("队列剩余元素："); 
	print(Q); 
	
	return 0;
} 

测试

入队顺序是：120 110 119 114 出队元素是：120
队列剩余元素：110 119 114
--------------------------------
Process exited after 0.01206 seconds with return value 0
请按任意键继续. . .