摘要：队列这种数据结构相较于栈就在我们生活中就更加地常见了。其操作方式就像我们生活中的排队一样“先进先出，后进后出”。与栈一样队列也可以分别用链表和顺序表实现，具体用那种就要看我们的实际需求了。其操作呢其实就是线性表特殊的插入与删除操作。与线性表有点不一样的时，我们添加了尾指针，让我们在进行入队操作时的时间复杂度更低。
链队列一.代码块
1）创建
typedef struct linkNode
{
int data;
struct linkNode *next;
}*linkNodePtr;
typedef struct linkQueue
{
linkNodePtr front;
linkNodePtr rear;
}*linkQueuePtr;
2）初始化
linkQueuePtr linkQueueInit()
{
linkNodePtr resultHeader = (linkNodePtr)malloc(sizeof(struct linkNode));
linkQueuePtr resultQueue = (linkQueuePtr)malloc(sizeof(struct linkQueue));
resultHeader->data = -1;
resultHeader->next = NULL;
resultQueue->front = resultHeader;
resultQueue->rear = resultHeader;
return resultQueue;
}
3）打印
void outputLinkQueue(linkQueuePtr paraQueue)
{
linkNodePtr tempPtr = paraQueue->front->next;
while(tempPtr != NULL)
{
printf("%d ",tempPtr->data);
tempPtr = tempPtr->next;
}
printf("rn");
}
4）入队
void enqueue(linkQueuePtr paraQueue,int paraData)
{
linkNodePtr p = (linkNodePtr)malloc(sizeof(struct linkNode));
p->data = paraData;
p->next = NULL;
paraQueue->rear->next = p;
paraQueue->rear = p;
}
5）出队
int dequeue(linkQueuePtr paraQueue)
{
int tempData;
if(paraQueue->front == paraQueue->rear)
{
printf("The queue is emptyn");
return -1;
}
linkNodePtr p = (linkNodePtr)malloc(sizeof(struct linkNode));
tempData = paraQueue->front->next->data;
p = paraQueue->front->next;
if(p->next == NULL)
{
paraQueue->rear = paraQueue->front;
}
else
paraQueue->front->next = p->next;
free(p);
return tempData;
}
6）入队出队测试函数
void test()
{
linkQueuePtr tempQueue = (linkQueuePtr)malloc(sizeof(struct linkQueue));
tempQueue = linkQueueInit();
enqueue(tempQueue, 6);
outputLinkQueue(tempQueue);
enqueue(tempQueue, 66);
outputLinkQueue(tempQueue);
enqueue(tempQueue, 666);
outputLinkQueue(tempQueue);
printf("dequeue gets %drn", dequeue(tempQueue));
printf("dequeue gets %drn", dequeue(tempQueue));
printf("dequeue gets %drn", dequeue(tempQueue));
printf("dequeue gets %drn", dequeue(tempQueue));
}
二.全部代码
#include#include typedef struct linkNode { int data; struct linkNode *next; }*linkNodePtr; typedef struct linkQueue { linkNodePtr front; linkNodePtr rear; }*linkQueuePtr; linkQueuePtr linkQueueInit() { linkNodePtr resultHeader = (linkNodePtr)malloc(sizeof(struct linkNode)); linkQueuePtr resultQueue = (linkQueuePtr)malloc(sizeof(struct linkQueue)); resultHeader->data = -1; resultHeader->next = NULL; resultQueue->front = resultHeader; resultQueue->rear = resultHeader; return resultQueue; } void outputLinkQueue(linkQueuePtr paraQueue) { linkNodePtr tempPtr = paraQueue->front->next; while(tempPtr != NULL) { printf("%d ",tempPtr->data); tempPtr = tempPtr->next; } printf("rn"); } void enqueue(linkQueuePtr paraQueue,int paraData) { linkNodePtr p = (linkNodePtr)malloc(sizeof(struct linkNode)); p->data = paraData; p->next = NULL; paraQueue->rear->next = p; paraQueue->rear = p; } int dequeue(linkQueuePtr paraQueue) { int tempData; if(paraQueue->front == paraQueue->rear) { printf("The queue is emptyn"); return -1; } linkNodePtr p = (linkNodePtr)malloc(sizeof(struct linkNode)); tempData = paraQueue->front->next->data; p = paraQueue->front->next; if(p->next == NULL) { paraQueue->rear = paraQueue->front; } else paraQueue->front->next = p->next; free(p); return tempData; } void test() { linkQueuePtr tempQueue = (linkQueuePtr)malloc(sizeof(struct linkQueue)); tempQueue = linkQueueInit(); enqueue(tempQueue, 6); outputLinkQueue(tempQueue); enqueue(tempQueue, 66); outputLinkQueue(tempQueue); enqueue(tempQueue, 666); outputLinkQueue(tempQueue); printf("dequeue gets %drn", dequeue(tempQueue)); printf("dequeue gets %drn", dequeue(tempQueue)); printf("dequeue gets %drn", dequeue(tempQueue)); printf("dequeue gets %drn", dequeue(tempQueue)); } int main() { test(); }
三.运行结果
6 6 66 6 66 666 dequeue gets 6 dequeue gets 66 dequeue gets 666 The queue is empty dequeue gets -1顺序循环队列
在我们已知队列的最大长度时，可以使用顺序表来进行队列的相关操作。但是，顺序队列会有一个较大的问题，即数组的“假”溢出。我们画一个图来看一下。
我们注意到，在出队操作后，数组其实是还有空间的，但是由于顺序表的单向性，rear指针已经指向了最后，代表了数组空间满了。这就是数组的“假”溢出现象。
对于，我们就可以用到今天要讲的顺序循环队列，实现队该数组空间的最大利用。图示如下
这就很好了，循环队列rear可以回到前面，假溢出现象就不复存在了，最大化的利用数组空间
一.代码块
是这样，由于rear要指向数据的后一个，如果是队满情况呢，rear就直接和front相等了同时队空的情况也是rear=front，两者就不好判断。我们又用到了一个经典的办法：放弃一个空间，不让其首尾相连，如果rear在front后面一个就判断为队满，rear==front就是队空，能储存的数据就比实际申请的空间要少一个
循环的队列该如何处理下标呢？事实上，数组下标正常加就行了，
将其对数组长度取余就会自动转换成我们循环意义上的下标，那么其他
的操作就跟正常的队列差不多了
1）创建
#define MAXSIZE 5
typedef struct circleQueue
{
int data[MAXSIZE];
int front;//指向的下标就是第一个
int rear; //指向的下标是最后一个数据的后一个
}*circleQueuePtr;
2）初始化
void circleQueuePtrInit(circleQueuePtr paraPtr)
{
paraPtr->front = 0;
paraPtr->rear = 0;
}
3）打印
void outputCircleQueue(circleQueuePtr paraPtr)
{
if(paraPtr->front == paraPtr->rear)
{
printf("rn");
return ;
}
int temp = paraPtr->front;
while(1)
{
printf("%d ",paraPtr->data[temp % MAXSIZE]);
if((temp+1) % MAXSIZE == paraPtr->rear % MAXSIZE)
{
break;
}
temp++;
}
printf("rn");
}
4）入队
void enqueue(circleQueuePtr paraPtr,int paraData)
{
if((paraPtr->rear + 1) % MAXSIZE == paraPtr->front % MAXSIZE)
{
printf("The queue is fulln");
return ;
}
paraPtr->data[paraPtr->rear % MAXSIZE] = paraData;
paraPtr->rear++;
}
5）出队
int dequeue(circleQueuePtr paraPtr)
{
int tempData;
if(paraPtr->front == paraPtr->rear)
{
printf("The queue is emptyn");
return -1;
}
tempData = paraPtr->data[paraPtr->front % MAXSIZE];
paraPtr->front++;
return tempData;
}
6）我的测试函数
void test()//我的测试用例
{
circleQueuePtr tempPtr = (circleQueuePtr)malloc(sizeof(struct circleQueue));
circleQueuePtrInit(tempPtr);
outputCircleQueue(tempPtr);
printf("Dequeue gets %dn",dequeue(tempPtr));
enqueue(tempPtr,1);
outputCircleQueue(tempPtr);
enqueue(tempPtr,2);
outputCircleQueue(tempPtr);
enqueue(tempPtr,3);
outputCircleQueue(tempPtr);
enqueue(tempPtr,4);
outputCircleQueue(tempPtr);
enqueue(tempPtr,5);
outputCircleQueue(tempPtr);
printf("Dequeue gets %dn",dequeue(tempPtr));
outputCircleQueue(tempPtr);
printf("Dequeue gets %dn",dequeue(tempPtr));
outputCircleQueue(tempPtr);
printf("Dequeue gets %dn",dequeue(tempPtr));
outputCircleQueue(tempPtr);
printf("Dequeue gets %dn",dequeue(tempPtr));
outputCircleQueue(tempPtr);
printf("Dequeue gets %dn",dequeue(tempPtr));
outputCircleQueue(tempPtr);
enqueue(tempPtr,666);
outputCircleQueue(tempPtr);
}
我的测试函数运行结果
The queue is full 1 2 3 4 Dequeue gets 1 2 3 4 Dequeue gets 2 3 4 Dequeue gets 3 4 Dequeue gets 4 The queue is empty Dequeue gets -1 666
7）老师的测试函数
void test2()//老师的测试用例
{
int i = 10;
circleQueuePtr tempPtr = (circleQueuePtr)malloc(sizeof(struct circleQueue));
circleQueuePtrInit(tempPtr);
for (; i < 16; i ++)
{
enqueue(tempPtr, i);
}
outputCircleQueue(tempPtr);
for (i = 0; i < 6; i ++)
{
printf("dequeue gets %drn", dequeue(tempPtr));
}
enqueue(tempPtr, 8);
outputCircleQueue(tempPtr);
}
老师的测试函数运行结果
The queue is full The queue is full 10 11 12 13 dequeue gets 10 dequeue gets 11 dequeue gets 12 dequeue gets 13 The queue is empty dequeue gets -1 The queue is empty dequeue gets -1 8
二.全部代码
#include#include #define MAXSIZE 5 typedef struct circleQueue { int data[MAXSIZE]; int front;//指向的下标就是第一个 int rear; //指向的下标是最后一个数据的后一个 }*circleQueuePtr; void circleQueuePtrInit(circleQueuePtr paraPtr) { paraPtr->front = 0; paraPtr->rear = 0; } void outputCircleQueue(circleQueuePtr paraPtr) { if(paraPtr->front == paraPtr->rear) { printf("rn"); return ; } int temp = paraPtr->front; while(1) { printf("%d ",paraPtr->data[temp % MAXSIZE]); if((temp+1) % MAXSIZE == paraPtr->rear % MAXSIZE) { break; } temp++; } printf("rn"); } void enqueue(circleQueuePtr paraPtr,int paraData) { if((paraPtr->rear + 1) % MAXSIZE == paraPtr->front % MAXSIZE) { printf("The queue is fulln"); return ; } paraPtr->data[paraPtr->rear % MAXSIZE] = paraData; paraPtr->rear++; } int dequeue(circleQueuePtr paraPtr) { int tempData; if(paraPtr->front == paraPtr->rear) { printf("The queue is emptyn"); return -1; } tempData = paraPtr->data[paraPtr->front % MAXSIZE]; paraPtr->front++; return tempData; } void test()//我的测试用例 { circleQueuePtr tempPtr = (circleQueuePtr)malloc(sizeof(struct circleQueue)); circleQueuePtrInit(tempPtr); outputCircleQueue(tempPtr); printf("Dequeue gets %dn",dequeue(tempPtr)); enqueue(tempPtr,1); outputCircleQueue(tempPtr); enqueue(tempPtr,2); outputCircleQueue(tempPtr); enqueue(tempPtr,3); outputCircleQueue(tempPtr); enqueue(tempPtr,4); outputCircleQueue(tempPtr); enqueue(tempPtr,5); outputCircleQueue(tempPtr); printf("Dequeue gets %dn",dequeue(tempPtr)); outputCircleQueue(tempPtr); printf("Dequeue gets %dn",dequeue(tempPtr)); outputCircleQueue(tempPtr); printf("Dequeue gets %dn",dequeue(tempPtr)); outputCircleQueue(tempPtr); printf("Dequeue gets %dn",dequeue(tempPtr)); outputCircleQueue(tempPtr); printf("Dequeue gets %dn",dequeue(tempPtr)); outputCircleQueue(tempPtr); enqueue(tempPtr,666); outputCircleQueue(tempPtr); } void test2()//老师的测试用例 { int i = 10; circleQueuePtr tempPtr = (circleQueuePtr)malloc(sizeof(struct circleQueue)); circleQueuePtrInit(tempPtr); for (; i < 16; i ++) { enqueue(tempPtr, i); } outputCircleQueue(tempPtr); for (i = 0; i < 6; i ++) { printf("dequeue gets %drn", dequeue(tempPtr)); } enqueue(tempPtr, 8); outputCircleQueue(tempPtr); } int main() { test(); test2(); }
