[数据结构与算法]数据结构——链队（定义、初始化、判断空队、入队、出队、遍历）

以下是数据结构中关于链队的定义、初始化、判断空队、入队、出队、遍历等基础操作。

定义

typedef struct QNode{
	char data;
	QNode *next;
}Qnode,*QP;

typedef struct LinkQueue{
	QP front;//注意这个是指针 
	QP rear;
}Lqueue;

说明：
链队里有两个指针：头指针和尾指针。指针的类型是QNode。
QNode里有两个属性：data和next指针。

初始化

void initial(LinkQueue &lq){
	lq.front = lq.rear = new QNode;
	lq.front->next = NULL;//等价于lq.rear->next = NULL;
}

步骤：

1. 开始链表的头尾指针都指向一个新的节点（该节点无data，只作为链表的头结点使用）；
2. 头指针/尾指针的next设空NULL（因为头指针和尾指针都指向同一个头结点，lq.front->next = NULL等价于lq.rear->next = NULL）。

画出来是这样的：

判断空队

int isNotEmpty(LinkQueue &lq){
	if(lq.front!=lq.rear){
		return 1;
	}
	return 0;
}

如果头尾指针都指向同一个节点（头结点），说明链队为空。

入队

void enQueue(LinkQueue &lq,char e){
	QP p = new QNode;
	p->data = e;
	lq.rear->next = p;//旧队尾指向p 
	p->next = NULL;
	lq.rear = p;//p成为新队尾 
}

void addElem(LinkQueue &lq){
	char elem='\n';
	while(elem!='*'){
		cout<<"请输入新节点(输入*退出):";
		cin>>elem;
		if(elem!='*'){
			enQueue(lq,elem);
		} 
	}
	showLQ(lq);
}

步骤：

1. 声明一个新节点p；
2. 链队尾指针rear的next指向p(rear为旧的队尾)；
3. p的next设空NULL;
4. 尾指针rear设为p（p成为新的rear，即新队尾）。

其中步骤2、3次序可调换。

出队

char deQueue(LinkQueue &lq){
	char c;
	QP p = lq.front->next;
	c = p->data;
	lq.front->next = p->next;
	if(p == lq.rear){
		lq.rear = lq.front;
	}
	delete p;
	return c;
}

void delElem(LinkQueue &lq){
	if(isNotEmpty(lq)){
		cout<<"出队元素为:"<<deQueue(lq)<<endl;
	}
	showLQ(lq);	
}

步骤

1. 判断是否为空队；
2. 声明一个中间节点p（用来释放出队节点）；
3. 将p设为队列第一个节点（即头节点的next节点）；
4. 将p的值提取出来（即出队节点的值）；
5. 头结点的next设为p的next节点（即头结点的next设为头结点的next节点的next节点，这样就跳过出队的节点了）；
6. 释放节点p。
7. 特别处理：如果尾节点rear指向的节点就是头结点的next，说明链队只剩下最后一个节点了（不算头结点），出队后尾节点rear和头指针front一样指向头结点（就像初始化那样）。

遍历队列

void showLQ(LinkQueue lq){
	QP p = lq.front->next;
	cout<<"当前链队数据:";
	if(!isNotEmpty(lq)){
		cout<<"空队!\n";
		delete p;
		return ;
	}
	while(p!=NULL){
		cout<<p->data<<" ";
		p = p->next;
	}
	cout<<endl;
	delete p;
}

步骤：

1. 判断队列是否为空；
2. 设置节点p用作遍历指针；
3. p从第一个节点开始向最后一个节点（即到rear指向的节点）遍历，到NULL就停止遍历即可。

运行截图

源码

/*
		广西师范大学 计算机科学与工程学院 
		GuangXi Normal University 
		College of Computer Science and Engineering  
		Student STZ 
*/ 
#include<iostream>
#include<stdio.h>
using namespace std;

typedef struct QNode{
	char data;
	QNode *next;
}Qnode,*QP;

typedef struct LinkQueue{
	QP front;//注意这个是指针 
	QP rear;
}Lqueue;

void initial(LinkQueue &lq){
	lq.front = lq.rear = new QNode;
	lq.rear->next = NULL;
}

int isNotEmpty(LinkQueue &lq){
	if(lq.front!=lq.rear){
		return 1;
	}
	return 0;
}

void showLQ(LinkQueue lq){
	QP p = lq.front->next;
	cout<<"当前链队数据:";
	if(!isNotEmpty(lq)){
		cout<<"空队!\n";
		delete p;
		return ;
	}
	while(p!=NULL){
		cout<<p->data<<" ";
		p = p->next;
	}
	cout<<endl;
	delete p;
}



void enQueue(LinkQueue &lq,char e){
	QP p = new QNode;
	p->data = e;
	lq.rear->next = p;//旧队尾指向p 
	p->next = NULL;
	lq.rear = p;//p成为新队尾 
}

void addElem(LinkQueue &lq){
	char elem='\n';
	while(elem!='*'){
		cout<<"请输入新节点(输入*退出):";
		cin>>elem;
		if(elem!='*'){
			enQueue(lq,elem);
		} 
	}
	showLQ(lq);
}

char deQueue(LinkQueue &lq){
	char c;
	QP p = lq.front->next;
	c = p->data;
	lq.front->next = p->next;
	if(p == lq.rear){
		lq.rear = lq.front;
	}
	delete p;
	return c;
}

void delElem(LinkQueue &lq){
	if(isNotEmpty(lq)){
		cout<<"出队元素为:"<<deQueue(lq)<<endl;
	}
	showLQ(lq);	
}

void menu(LinkQueue &lq){
	int c = 0;
	while(1){
		cout<<"请选择操作:"<<endl;
		cout<<"1:入队"<<endl;
		cout<<"2:出队"<<endl;
		cout<<"3:遍历队"<<endl;
		cout<<"4:退出"<<endl;
		cin>>c;
		switch(c){
			case 1:addElem(lq);break;
			case 2:delElem(lq);break;
			case 3:showLQ(lq);break;
			case 4:return;
			default:;
		} 
	}
}

int main(){
	LinkQueue lq;
	initial(lq);
	menu(lq); 
	return 0;
}