1.3 队列的顺序存储实现和链式存储实现（C语言）

队列的存储实现

• • • 顺序存储实现源码
    • 运行
    • • 顺环队列
      • • 1. 使用额外标记：Size或者tag域
        • 2. 仅使用n-1个数组空间
    • 链式存储实现源码
    • 运行
    • • 链队列示意图
    • int data[]与int *data区别(c中数组名可以看成指针)

顺序存储实现源码

• 数组的方式实现队列的顺序存储。用一个一维数组来存储队列的数据，对队列执行操作时，插入和删除分别是对数组头和数组尾进行操作，所以还要有两个指针变量来指示数组的头和尾

#include #include #define ERROR 0#define MaxSize 5/* 存储空间初始分配量 */typedef int ElementType;  //给int取别名typedef int Position;struct QNode {ElementType *Data;     /* 存储元素的数组 */Position Front, Rear;  /* 队列的头、尾指针 */};typedef struct QNode *Queue;/*生成长度为MaxSize的空队列*/Queue CreateQueue(){Queue Q = (Queue)malloc(sizeof(struct QNode));Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));Q->Front = Q->Rear = 0;return Q;}/*判断队列Q是否已满*/bool IsFull(Queue Q){return ((Q->Rear + 1) % MaxSize == Q->Front);}/*若队列未满，将数据元素X插入队列Q中*/bool AddQ(Queue Q, ElementType X){if (IsFull(Q)) {printf("队列满");return false;}else {/* Rear指针向后移一位置，若到最后则转到数组头部 */Q->Rear = (Q->Rear + 1) % MaxSize;//循环队列：求余函数/* 将元素X赋值给队尾 */Q->Data[Q->Rear] = X;//注意这里Q->Rear=1，也就是说队尾是1，从第一位开始赋值return true;}}/*判断队列Q是否为空*/bool IsEmpty(Queue Q){return (Q->Front == Q->Rear);}/*若队列不空，将队头数据从队列中删除并返回*/ElementType DeleteQ(Queue Q){if (IsEmpty(Q)) {printf("队列空");return ERROR;}else {Q->Front = (Q->Front +1) % MaxSize;return  Q->Data[Q->Front];}}/* 从队头到队尾依次对队列Q中每个元素输出 */ElementType Queueshow(Queue Q){int i;i = Q->Front;if (IsEmpty(Q)) {printf("栈是空的");}elsewhile ((i + Q->Front) != Q->Rear){i = (i +1) % MaxSize; //初次时，i=1，从第一位开始输出printf("%d\t",Q->Data[i]);}printf("\n");return 0;}/* 返回Q的元素个数，也就是队列的当前长度 */int QueueLength(Queue Q){return  (Q->Rear - Q->Front + MaxSize) % MaxSize;}int  show(Queue Q) {printf("此时队列的长度为%d,此时队头Front指向的元素为%d,此时队尾Rear指向的元素为%d\n", QueueLength(Q),Q->Front, Q->Rear);return 0;}int main() {Queue q;//结构体指针 int i = 0;q = CreateQueue();printf("此时队列的MaxSize大小为%d\n", MaxSize);printf("此时队列q的元素有\n");Queueshow(q);show(q);printf("若队列未满，将元素X插入队列\n");    for (i = 1; i < MaxSize; i++) {printf("将%d插入队列q为新的队尾元素\n", i);AddQ(q, i);}show(q);printf("此时堆栈q的元素有\n");Queueshow(q);printf("若队列不空，删除并返回队头元素\n");for (i = 1; i < MaxSize; i++) {printf("将队头元素%d从队列q中删除并返回\n", DeleteQ(q));}show(q);printf("此时堆栈q的元素有\n");Queueshow(q);return 0;}

运行

此时队列的MaxSize大小为5此时队列q的元素有栈是空的此时队列的长度为0,此时队头Front指向的元素为0,此时队尾Rear指向的元素为0若队列未满，将元素X插入队列将1插入队列q为新的队尾元素将2插入队列q为新的队尾元素将3插入队列q为新的队尾元素将4插入队列q为新的队尾元素此时队列的长度为4,此时队头Front指向的元素为0,此时队尾Rear指向的元素为4此时堆栈q的元素有1234若队列不空，删除并返回队头元素将队头元素1从队列q中删除并返回将队头元素2从队列q中删除并返回将队头元素3从队列q中删除并返回将队头元素4从队列q中删除并返回此时队列的长度为0,此时队头Front指向的元素为4,此时队尾Rear指向的元素为4此时堆栈q的元素有栈是空的

顺环队列

1. 使用额外标记：Size或者tag域

• 增加一个额外的标记，Size来记录当前队列元素的个数，删除元素-1，加入元素+1，由Size为0或n得知队列空满
• 插入元素的时候，Tag设为1，删除一个元素的时候tag等于0，tag代表最后一次操作是插入还是删除，此时就知道队列到底是空或满

2. 仅使用n-1个数组空间

• 另外一种方法是，数组大小虽然是n，但是不放满，最多只放n-1个元素，就像上面的例子，数组有6，但是我最多放5个

链式存储实现源码

#include #include #define ERROR 0#define NULL 0#define MaxSize 5/* 存储空间初始分配量 */typedef int ElementType;  /* ElementType类型根据实际情况而定，这里假设为int */typedef struct Node *PtrToNode;struct Node {     /* 队列中的结点结构 */ ElementType Data;PtrToNode Next;};typedef PtrToNode Position;struct QNode {      /* 队列的链表结构 */Position Front, Rear;  /* 队列的头、尾指针 */};typedef struct QNode *Queue;/* 构造一个空队列Q */Queue InitQueue(){Queue Q=(Queue)malloc(sizeof(struct QNode));Q->Front = Q->Rear = (Position)malloc(sizeof(Node));if (!Q->Front)exit(false);//正常退出Q->Front->Next = NULL;return Q;}/* 销毁队列Q */void DestroyQueue(Queue Q){while (Q->Front){Q->Rear = Q->Front->Next;free(Q->Front);Q->Front = Q->Rear;}}/* 将Q清为空队列 */Queue ClearQueue(Queue Q){Position p, q;Q->Rear = Q->Front;p = Q->Front->Next;Q->Front->Next = NULL;while (p){q = p;p = p->Next;free(q);}return Q;}/*判断队列Q是否为空*/bool IsEmpty(Queue Q){return (Q->Front == NULL);}/* 插入元素e为Q的新的队尾元素 */ElementType EnQueue(Queue Q, ElementType e){Position s = (Position)malloc(sizeof(Node));if (!s) /* 存储分配失败 */exit(false);s->Data = e;s->Next = NULL;Q->Rear->Next = s;/* 把拥有元素e的新结点s赋值给原队尾结点的后继 */Q->Rear = s;/* 把当前的s设置为队尾结点，rear指向s */return 0;}/*若队列不空，将队头数据从队列中删除并返回*/ElementType DeleteQ(Queue Q){Position FrontCell;ElementType FrontElem;if (IsEmpty(Q)) {printf("队列空");return ERROR;}else {FrontCell = Q->Front->Next; /*将欲删除的队头结点暂存给新建结点*/FrontElem = FrontCell->Data;/* 将欲删除的队头结点的值赋值给新建变量*/Q->Front->Next = FrontCell->Next;/* 将原队头结点的后继FrontCell->next赋值给头结点后继*/if (Q->Front == Q->Rear) /* 若队列只有一个元素 */Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */free(FrontCell);  /* 释放被删除结点空间  */return  FrontElem;}}/* 从队头到队尾依次对队列Q中每个元素输出 */ElementType Queueshow(Queue Q){Position p;p = Q->Front->Next;if (Q->Front->Next==NULL) {printf("队列是空的");return false;}elsewhile (p){printf("%d\t",p->Data);p = p->Next;}printf("\n");return 0;}/* 返回Q的元素个数，也就是队列的当前长度 */int QueueLength(Queue Q){int i = 0;Position p ;p = Q->Front;if (p->Next == NULL) {//printf("队列是空的\n");return false;}elsewhile (Q->Rear != p){i++;p = p->Next;}return i;}void  show(Queue Q) {Position p,p2;if (Q->Front == Q->Rear|| Q->Front->Next==NULL){printf("链队列为空，无法返回队头数据\n"); }else{p = Q->Front->Next;//队头printf( "此时队头Front指向的元素为%d,\n" ,p->Data );p2 = Q->Rear;printf("此时队尾Rear指向的元素为%d\n", p2->Data);}printf("此时队列的长度为%d,\n", QueueLength(Q));}int main() {Queue q;//结构体指针 int i = 0;q = InitQueue();ClearQueue(q);printf("此时队列的MaxSize大小为%d\n", MaxSize);printf("此时队列q的元素有\n");Queueshow(q);show(q);printf("若队列未满，将元素X插入队列\n");    for (i = 1; i < MaxSize; i++) {printf("将%d插入队列q为新的队尾元素\n", i);EnQueue(q, i);}printf("此时队列q的元素有\n");Queueshow(q);show(q);printf("若队列不空，删除并返回队头元素\n");for (i = 1; i < MaxSize; i++) {printf("将队头元素%d从队列q中删除并返回\n", DeleteQ(q));}printf("此时队列q的元素有\n");Queueshow(q);show(q);DestroyQueue(q);return 0;}

运行

此时队列的MaxSize大小为5此时队列q的元素有队列是空的链队列为空，无法返回队头数据此时队列的长度为0,若队列未满，将元素X插入队列将1插入队列q为新的队尾元素将2插入队列q为新的队尾元素将3插入队列q为新的队尾元素将4插入队列q为新的队尾元素此时队列q的元素有1234此时队头Front指向的元素为1,此时队尾Rear指向的元素为4此时队列的长度为4,若队列不空，删除并返回队头元素将队头元素1从队列q中删除并返回将队头元素2从队列q中删除并返回将队头元素3从队列q中删除并返回将队头元素4从队列q中删除并返回此时队列q的元素有队列是空的链队列为空，无法返回队头数据此时队列的长度为0,

链队列示意图

int data[]与int *data区别(c中数组名可以看成指针)

做形参的时候，int data[]与int *data无任何区别。

int data[]申请的是一个静态数组，在设计时就需要考虑其大小，这样带来的缺点是空间大小固定，导致空间不够用或者浪费
int *data申请的是一个指针变量(申请一个路标)，然后通过malloc函数申请一片空间(在建设工程中申请一片空地，这样可以按照需求确定大小，然后让路标指向这片空地)，得到动态数组(即申请的空间可以由变量大小确定)。

data[i]本来就是*(data+i)
如果要访问int data[5]实际上是先获得这个数组的头指针int *data，然后在内存中偏移5个int的数据长度int *(data+5)，也就是从代码的理解上，可以认为int data[5]与 int *(data+5)等价