链队列：使用链表实现的队列；具有队头指针和队尾指针，指示队列元素所在的位置。
特点：
1、只能队尾插入元素、在队头删除元素。
2、先进先出的线性表，先进入的元素出队，后进入的元素才能出队。
优点：
3、相比普通的队列，元素出队时无需移动大量元素，只需移动头指针。
4、可动态分配空间，不需要预先分配大量存储空间。
二、代码功能
1、创建单链表
2、创建链队列
3、初始化链队列
4、链队列的输出
5、链队列的元素的添加（入队）
6、链队列元素的删除（出队)
7、链队列的测试
8、程序入口
9、运行结果
三、链队列代码1、创建单链表
typedef struct LinkNode
{
int data;
LinkNode* next;
}*LinkNodePtr;
2、创建链队列
typedef struct LinkQueue
{
LinkNodePtr front;
LinkNodePtr rear;
}*LinkQueuePtr;
3、初始化链队列
LinkQueuePtr initQueue()
{
LinkQueuePtr resultPtr = (LinkQueuePtr)malloc(sizeof(LinkQueue));
LinkNodePtr headerPtr = (LinkNodePtr)malloc(sizeof(LinkNodePtr));
headerPtr->next = NULL;
resultPtr->front = headerPtr;
resultPtr->rear = headerPtr;
return resultPtr;
}
4、链队列的输出
void outputLinkQueue(LinkQueuePtr paraQueuePtr)
{
LinkNodePtr tempPtr = paraQueuePtr->front->next;
while(tempPtr != NULL)
{
printf("%d ",tempPtr->data);
tempPtr = tempPtr->next;
}
printf("rn");
}
5、链队列的元素的添加（入队）
void enqueue(LinkQueuePtr paraQueuePtr,int paraElement)
{
LinkNodePtr tempPtr = (LinkNodePtr)malloc(sizeof(LinkNode));
tempPtr->data = paraElement;
tempPtr->next = NULL;
paraQueuePtr->rear->next = tempPtr;
paraQueuePtr->rear = tempPtr;
}
6、链队列元素的删除（出队）
int dequeue(LinkQueuePtr paraQueuePtr)
{
int resultValue;
LinkNodePtr tempNodePtr;
if(paraQueuePtr->front == paraQueuePtr->rear)
{
printf("The queue is empty.rn");
return -1;
}
tempNodePtr = paraQueuePtr->front->next;
resultValue = tempNodePtr->data;
paraQueuePtr->front->next = paraQueuePtr->front->next->next;
if (paraQueuePtr->rear == tempNodePtr)
{
paraQueuePtr->rear = paraQueuePtr->front;
}
tempNodePtr = NULL;
return resultValue;
}
7、链队列的测试
void testLinkQueue(){
LinkQueuePtr tempQueuePtr;
tempQueuePtr = initQueue();
enqueue(tempQueuePtr, 10);
enqueue(tempQueuePtr, 30);
enqueue(tempQueuePtr, 50);
outputLinkQueue(tempQueuePtr);
printf("dequeue gets %drn", dequeue(tempQueuePtr));
printf("dequeue gets %drn", dequeue(tempQueuePtr));
printf("dequeue gets %drn", dequeue(tempQueuePtr));
printf("dequeue gets %drn", dequeue(tempQueuePtr));
enqueue(tempQueuePtr, 8);
outputLinkQueue(tempQueuePtr);
}
8、程序入口
int main(){
testLinkQueue();
return 1;
}
9、运行结果
10 30 50 dequeue gets 10 dequeue gets 30 dequeue gets 50 The queue is empty. dequeue gets -1 8四、整体代码
#include#include typedef struct LinkNode { int data; LinkNode* next; }*LinkNodePtr; typedef struct LinkQueue { LinkNodePtr front; LinkNodePtr rear; }*LinkQueuePtr; LinkQueuePtr initQueue() { LinkQueuePtr resultPtr = (LinkQueuePtr)malloc(sizeof(LinkQueue)); LinkNodePtr headerPtr = (LinkNodePtr)malloc(sizeof(LinkNodePtr)); headerPtr->next = NULL; resultPtr->front = headerPtr; resultPtr->rear = headerPtr; return resultPtr; } void outputLinkQueue(LinkQueuePtr paraQueuePtr) { LinkNodePtr tempPtr = paraQueuePtr->front->next; while(tempPtr != NULL) { printf("%d ",tempPtr->data); tempPtr = tempPtr->next; } printf("rn"); } void enqueue(LinkQueuePtr paraQueuePtr,int paraElement) { LinkNodePtr tempPtr = (LinkNodePtr)malloc(sizeof(LinkNode)); tempPtr->data = paraElement; tempPtr->next = NULL; paraQueuePtr->rear->next = tempPtr; paraQueuePtr->rear = tempPtr; } int dequeue(LinkQueuePtr paraQueuePtr) { int resultValue; LinkNodePtr tempNodePtr; if(paraQueuePtr->front == paraQueuePtr->rear) { printf("The queue is empty.rn"); return -1; } tempNodePtr = paraQueuePtr->front->next; resultValue = tempNodePtr->data; paraQueuePtr->front->next = paraQueuePtr->front->next->next; if (paraQueuePtr->rear == tempNodePtr) { paraQueuePtr->rear = paraQueuePtr->front; } tempNodePtr = NULL; return resultValue; } void testLinkQueue(){ LinkQueuePtr tempQueuePtr; tempQueuePtr = initQueue(); enqueue(tempQueuePtr, 10); enqueue(tempQueuePtr, 30); enqueue(tempQueuePtr, 50); outputLinkQueue(tempQueuePtr); printf("dequeue gets %drn", dequeue(tempQueuePtr)); printf("dequeue gets %drn", dequeue(tempQueuePtr)); printf("dequeue gets %drn", dequeue(tempQueuePtr)); printf("dequeue gets %drn", dequeue(tempQueuePtr)); enqueue(tempQueuePtr, 8); outputLinkQueue(tempQueuePtr); }//Of testLinkQueue int main(){ testLinkQueue(); return 1; }
