链式队列----数据结构

队列的基本概念

队列是一种操作受限的线性表（先进先出），只允许在队尾插入，队头删除。

例如去银行办理业务，肯定是先来的先出去，后来的人排在后方，只有第一个人业务办理完了，才会有一个人出队列。

队列的实现

结点和指针的定义

#define MAX_SIZE 50
 
typedef int DateElem;         //队列中的元素类型
typedef struct _QueueNode
{
	DateElem date;
	struct _QueueNode* next;  //和单链表结点的定义一样
}QueueNode; 
 
 
typedef QueueNode*  QueuePtr;      //可以用QueuePtr创建一个指向结点的指针
 
typedef struct LinkQueue           //定义的是队列头、尾指针
{
	int length;    //存储队列的长度，因为要频繁获取长度
	QueuePtr head; //指向第一个结点，队头指针
	QueuePtr tail; //指向最后一个结点，队尾指针
}Queue;

初始化

//初始化队列
bool InitQueue(Queue* sq)
{
	if (!sq) return false; 
 
	sq->length = 0;
	sq->head = NULL;     //置为空，最开始为空队列
	sq->tail = NULL;
	return true;
}

判断是否为空

bool IsEmpty(Queue* sq)
{
	if (!sq) return false;
 
    //头指针没有指向任何一个结点
	if (sq->head == NULL) //不能用 sq->head == sq->tail 来判断，因为队列只有一个元素时，头尾指针指向同一个结点，但是可以用 sq->head == sq->tail = NULL，意思是三个都相等
	{
		return true;
	}
 
	return false;
}

判断是否满了

bool IsFull(Queue* sq)
{
	if (!sq) return false;
 
	if (sq->length >= MAX_SIZE) //长度最开始为0，插入一个，长度 +1
	{
		return true;
	}
	return false;
}

插入（入队）

bool EnterQueue(Queue* sq, DateElem *e)
{
	if (!sq) return false;   
 
	if (IsFull(sq)) return false; //队列满了，无法继续插入
 
 
	QueueNode *p = new QueueNode;
	p->date = *e;
	p->next = NULL;               //因为是最后一个结点，没有直接后继
	
	if (IsEmpty(sq)) //空队列
	{
		sq->head = p;
		sq->tail = p;
	}
	else
	{
		//此时head指向第一个结点，tail指向最后一个结点
		sq->tail->next = p;
		sq->tail = p;          //更新tail指针
	}
 
	sq->length++;              //别忘记了
	return true;
}

删除（出队）

bool PopQueue(Queue* sq,DateElem *date)
{
	if (!sq || IsEmpty(sq)) return false;
 
	if (!date) return false;
	
	//此时head指向第一个结点，tail指向最后一个结点
	QueueNode* p = sq->head;
	sq->head = p->next;         //head指向第二个结点
	*date = p->date;            //返回删除的值
 
	delete p;
 
	//如果队列只有一个结点，而恰好刚刚删除了，也就是空队列
	if (IsEmpty(sq))
	{
		sq->head = NULL; //head已经为空，写一下更整齐（可以不用写）
		sq->tail = NULL;
	}
	
	sq->length--;
	return true;
}

打印队列

bool Print(Queue* sq)  //和链表的打印一样
{
	if (!sq ) return false; 
 
	if (IsEmpty(sq))
	{
		cout << "队列为空" << endl;
	}
	QueueNode* p = sq->head;
	cout << "队列中的元素：";
	while (p != NULL)
	{
		printf("%d ", p->date);
		p = p->next;
	}
	cout << endl;
	return true;
}

清空队列

//清空队列
bool ClearQueue(Queue* sq)
{
	if (!sq || IsEmpty(sq)) return false; 
 
	QueueNode* p = sq->head,*q = NULL;
 
	while (p != NULL) 
	{
		q = p->next;    
		delete p;            
		p = q;
	}
    
	sq->length = 0;
	sq->head = NULL;
	sq->tail = NULL;
	return true;
}

获取队头元素

bool GetHead(Queue* sq, DateElem* date)
{
	if (!date || !sq || IsEmpty(sq) )return false; 
 
	*date = sq->head->date;   //指针返回队首元素
	return true;
 
}

主函数代码

可以在主函数中测试一下刚刚实现的功能，还有一些功能可以自己去实现，比如获取队列长度。

int main(void)
{
	Queue* sq = new Queue ;
	DateElem* s = new DateElem;
	//1.初始化队列
	InitQueue(sq);
 
 
	for (int i = 1; i <= 7; i++)
	{
		if (EnterQueue(sq, &i))
		{
			cout << "入队成功" << endl;
 
		}
		else
		{
			cout << "入队失败，" << i << "未插入" << endl;
		}
	}
 
	Print(sq);
	for (int i = 0; i < 8; i++)
	{
		if (PopQueue(sq, s))
		{
			cout << "出队的元素是" << *s << endl;
		}
		else
		{
			cout << "出队失败" << endl;
		}
		
		Print(sq);
	}
 
	ClearQueue(sq);
	Print(sq);
	return 0;
}