链队列
队列的链式存储结构其实是线性表的单链表，只不过它只能尾进头出，我们把它简称链队列
定义链队列的结点
typedef struct LinkNode {
int data;
struct LinkNode* next;
}*LinkNodePtr;
定义链队列的结构：
typedef struct LinkQueue {
LinkNodePtr front;
LinkNodePtr rear;
}*LinkQueuePtr;
入队：
void enqueue(LinkQueuePtr paraQueuePtr, int paraElement){
//创建新结点
LinkNodePtr tempNodePtr = (LinkNodePtr)malloc(sizeof(LinkNodePtr));
tempNodePtr->data = paraElement;
tempNodePtr->next = NULL;
//将结点链接到队列中去
paraQueuePtr->rear->next = tempNodePtr;
paraQueuePtr->rear = tempNodePtr;
}
出队：
int dequeue(LinkQueuePtr paraQueuePtr){
int resultValue;
LinkNodePtr tempNodePtr;
//判断队列是否为空
if(paraQueuePtr->front == paraQueuePtr->rear){
printf("the queue is emptyrn");
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;
}
全部代码：
#include#include //定义链队列的结点 typedef struct LinkNode { int data; struct LinkNode* next; }*LinkNodePtr; //链队列 typedef struct LinkQueue { LinkNodePtr front; LinkNodePtr rear; }*LinkQueuePtr; LinkQueuePtr initQueue(){ LinkQueuePtr resultPtr = (LinkQueuePtr)malloc(sizeof(LinkQueuePtr)); LinkNodePtr headerPtr = (LinkNodePtr)malloc(sizeof(LinkNodePtr)); headerPtr->data = -1; headerPtr->next = NULL; resultPtr->front = headerPtr; resultPtr->rear = headerPtr; return resultPtr; } void outputLinkQueue(LinkQueuePtr paraQueuePtr){ // LinkNodePtr tempPtr = 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 tempNodePtr = (LinkNodePtr)malloc(sizeof(LinkNodePtr)); tempNodePtr->data = paraElement; tempNodePtr->next = NULL; //将结点链接到队列中去 paraQueuePtr->rear->next = tempNodePtr; paraQueuePtr->rear = tempNodePtr; } //出队 int dequeue(LinkQueuePtr paraQueuePtr){ int resultValue; LinkNodePtr tempNodePtr; //判断队列是否为空 if(paraQueuePtr->front == paraQueuePtr->rear){ printf("the queue is emptyrn"); 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); } int main(){ testLinkQueue(); return 1; }
运行结果：
Queue full. Queue full. Elements in the queue: 10, 11, 12, 13, dequeue gets 10 dequeue gets 11 dequeue gets 12 dequeue gets 13 No element in the queue. dequeue gets -1 No element in the queue. dequeue gets -1 Elements in the queue: 8,
循环队列
队列的头尾相接的循序结构称为循环队列
定义循环队列的结构体：
typedef struct CircleIntQueue{
int data[TOTAL_SPACE];
int head;
int tail;
}*CircleIntQueuePtr;
初始化：
CircleIntQueuePtr initQueue() {
CircleIntQueuePtr resultPtr = (CircleIntQueuePtr)malloc(sizeof(CircleIntQueue));
resultPtr->head = 0;
resultPtr->tail = 0;
return resultPtr;
}
入队：
void enqueue(CircleIntQueuePtr paraPtr, int paraValue) {
// 判断队列是否满了
if((paraPtr->tail+=1)%TOTAL_SPACE == paraPtr->head){
printf("Queue fullrn");
return;
}
paraPtr->data[paraPtr->tail%TOTAL_SPACE] = paraValue;
paraPtr->tail = (paraPtr->tail+1)%TOTAL_SPACE;
}
出队：
int dequeue(CircleIntQueuePtr paraPtr){
int resultValue;
// 判断队列是否为空
if(paraPtr->head == paraPtr->tail){
printf("No element in the Queuern");
return -1;
}
resultValue = paraPtr->data[paraPtr->head%TOTAL_SPACE];
paraPtr->head = (paraPtr->head+1)%TOTAL_SPACE;
return resultValue;
}
总代码：
#include#include #define TOTAL_SPACE 5 //定义循环队列的结构体 typedef struct CircleIntQueue{ int data[TOTAL_SPACE]; int head; int tail; }*CircleIntQueuePtr; CircleIntQueuePtr initQueue() { CircleIntQueuePtr resultPtr = (CircleIntQueuePtr)malloc(sizeof(CircleIntQueue)); resultPtr->head = 0; resultPtr->tail = 0; return resultPtr; } // 入队 void enqueue(CircleIntQueuePtr paraPtr, int paraValue) { // 判断队列是否满了 if((paraPtr->tail+=1)%TOTAL_SPACE == paraPtr->head){ printf("Queue fullrn"); return; } paraPtr->data[paraPtr->tail%TOTAL_SPACE] = paraValue; paraPtr->tail = (paraPtr->tail+1)%TOTAL_SPACE; } // 出队 int dequeue(CircleIntQueuePtr paraPtr){ int resultValue; // 判断队列是否为空 if(paraPtr->head == paraPtr->tail){ printf("No element in the Queuern"); return -1; } resultValue = paraPtr->data[paraPtr->head%TOTAL_SPACE]; paraPtr->head = (paraPtr->head+1)%TOTAL_SPACE; return resultValue; } // 输出队列 void outputQueue(CircleIntQueuePtr paraPtr){ int i; if(paraPtr->head == paraPtr->tail){ printf("Empty queue"); return; } printf("Element in the queue:"); for(i = paraPtr->head; i tail;i++){ printf("%d ",paraPtr->data[i%TOTAL_SPACE]); } printf("rn"); } void testLinkQueue(){ int i = 10; CircleIntQueuePtr tempPtr = initQueue(); for (; i < 16; i ++) { enqueue(tempPtr, i); } outputQueue(tempPtr); for (i = 0; i < 6; i ++) { printf("dequeue gets %drn", dequeue(tempPtr)); } enqueue(tempPtr, 8); outputQueue(tempPtr); } int main(){ testLinkQueue(); return 1; }
运行结果：
Queue full Queue full Element in the queue:10 11 12 13 dequeue gets 10 dequeue gets 11 dequeue gets 12 dequeue gets 13 No element in the Queue dequeue gets -1 No element in the Queue dequeue gets -1 Element in the queue:
**总结：**队列的关键在于先进先出的特点，链队列需要动态申请和释放结点，但循环队列是现申请好内存空间，使用期间不释放。在确定队列长度最大值的情况下，建议使用循环队列，如果无法预估队列长度，则用链队列
