【数据结构】队列的链式实现

 

 

#include 
typedef struct LinkNode
{
	int data;
	struct LinkNode* next;
	
}LinkNode;
typedef struct
{
	LinkNode* front, * rear;
 
}LinkQueue;
/// 
///初始化队列 （带头结点）
/// 
/// 
void InitQueue(LinkQueue &Q)
{
	Q.front = Q.rear =(LinkNode*) malloc(sizeof(LinkNode));
	Q.front->next = NULL;
}
void testLinkQueue()
{
	LinkQueue Q;
	InitQueue(Q);
}
 
bool IsEmpty(LinkQueue Q)
{
	if (Q.front == Q.rear)
		return true;
	else
	{
		return false;
	}
}

 

 

//新元素入队（带头结点）
void EnQueue(LinkQueue &Q,int x)
{
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	Q.rear->next = s;
	Q.rear = s;
}

 

//新元素入队（不带头结点）
void EnQueue(LinkQueue& Q, int x)
{
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	if (Q.front == NULL)
	{
		Q.front = s;
		Q.rear = s;
	}
	else
	{
	Q.rear->next = s;
	Q.rear = s;
	}
}

 

//对头元素出队(带头节点)
bool  DeQueue(LinkQueue &Q,int &x)
{
	if (Q.front == Q.rear)
	{
		return false;
	}
	LinkNode* p = Q.front->next;
	x = p->data;
	Q.front->next = p->next;
	if (Q.rear == p)
	{
		Q.rear = Q.front;
	}
	free(p);
	return true;
}

 

//对头元素出队(不带头节点)
bool  DeQueue(LinkQueue& Q, int& x)
{
	if (Q.front == NULL)
	{
		return false;
	}
	LinkNode* p = Q.front;
	x = p->data;
	Q.front = p->next;
	if (Q.rear == p)//最后一个结点出队
	{
		Q.front = NULL;
		Q.rear = NULL;
	}
	free(p);
	return true;
}