队列和栈

1、栈的概念

栈又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。

2、栈的顺序存储结构和操作实现

栈的顺序存储结构示意图：

下面通过一个实例展示栈的顺序存储结构的操作实现，其中包含了6种操作：

[cpp]  view plain  copy   #include<stdio.h>   #include<stdlib.h>   typedef int ElemType;  //定义元素类型   struct StackSq         //定义栈结构类型   {       ElemType* stack;   //存栈元素的数组指针       int top;           //存栈顶元素的下标位置       int MaxSize;       //存stack数组长度   };      //栈满需要重新分配更大空间 的情况   void againMalloc(struct StackSq* S)   {       ElemType *p = realloc(S->stack, 2*S->MaxSize*sizeof(ElemType));//此处重新分配的空间为原来的2倍       if (!p)  //重新分配失败       {           printf("存储空间用完！\n");           exit(1);       }       S->stack = p;             //使list指向新栈空间       S->MaxSize = 2 * S->MaxSize;       printf("存储空间已扩大为当前的2倍！\n");//输出提示已扩充空间   }      //1、初始化栈S为空   void InitStack(struct StackSq* S, int ms)   {       if (ms < 0)       {           printf("ms的值非法！\n");           exit(1);       }       S->MaxSize = ms;       S->stack = malloc(ms*sizeof(ElemType));       if (!S->stack)       {           printf("动态存储分配失败！\n");           exit(1);       }       S->top = -1;   //值为-1，表示栈空   }      //2、新元素进栈，即把它插入到栈顶   void Push(struct StackSq* S, ElemType x)   {       if (S->top == S->MaxSize - 1)           againMalloc(S);       S->top++;       S->stack[S->top] = x;   }      //3、删除栈顶元素并返回值   ElemType Pop(struct StackSq* S)   {       if (S->top == -1)       {           printf("栈空，无元素出栈！\n");           exit(1);       }       S->top--;       return S->stack[S->top + 1];   }      //4、读取栈顶元素的值（并不改变栈）   ElemType Peek(struct StackSq* S)   {       if (S->top == -1)       {           printf("栈空，无任何元素！\n");           exit(1);       }       return S->stack[S->top];   }      //5、判断S是否为空。若是空返回1，否则返回0   int EmptyStack(struct StackSq* S)   {       if (S->top == -1)           return 1;       else           return 0;   }      //6、清除栈S中的所有元素，释放动态存储空间   void ClearStack(struct StackSq* S)   {       if (S->stack)       {           free(S->stack);   //释放存储空间           S->stack = 0;           S->top == -1;           S->MaxSize = 0;       }   }      //主函数   void main()   {void againMalloc(struct List *L)   {       ElemType *p = realloc(L->list, 2*L->MaxSize*sizeof(ElemType));//此处重新分配的空间为原来的2倍       if (!p)  //重新分配失败       {           printf("存储空间用完！\n");           exit(1);       }       L->list = p;             //使list指向新线性表空间       L->MaxSize = 2 * L->MaxSize;       printf("存储空间已扩大为当前的2倍！\n");//输出提示已扩充空间   }       struct StackSq s;       int a[8] = {3, 8, 5, 17, 9, 30, 15, 22};       int i;       InitStack(&s, 5);       for (i = 0; i < 8; i++)           Push(&s, a[i]);       printf("%d ", Pop(&s));       printf("%d \n", Pop(&s));       Push(&s, 68);       printf("%d ", Peek(&s));       printf("%d \n", Pop(&s));       while (!EmptyStack(&s))           printf("%d ", Pop(&s));       printf("\n");       ClearStack(&s);   }   运行结果：

3、栈的链接存储结构和操作实现

栈的链接存储结构与线性表的链接存储结构相同。

栈的链接存储结构及操作过程示意图：

下面通过一个实例展示栈的链接存储结构的操作，其中包括6种操作

[cpp]  view plain  copy   #include<stdio.h>   #include<stdlib.h>      typedef int ElemType;  //定义元素类型   struct sNode           //定义链栈结点类型   {       ElemType data;       struct sNode* next;   };      //1、初始化链栈为空   void InitStack(struct sNode** HS)   {       *HS = NULL;   //HS表示栈顶指针   }      //2、向链栈中插入一个元素   void Push(struct sNode** HS, ElemType x)   {       struct sNode *newp;       newp = malloc(sizeof(struct sNode));       if (newp == NULL)       {           printf("内存动态空间用完，退出运行！\n");           exit(1);       }       newp->data = x;       newp->next = *HS;       *HS = newp;   }      //3、从链栈中删除栈顶元素并返回它   ElemType Pop(struct sNode** HS)   {       struct sNode* p;       ElemType temp;       if (*HS == NULL)       {           printf("栈空无法删除！\n");           exit(1);       }       p = *HS;       *HS = p->next;       temp = p->data;       free(p);       return temp;   }      //4、读取栈顶元素   ElemType Peek(struct sNode** HS)   {       if (*HS == NULL)       {           printf("栈空，无栈顶结点！\n");           exit(1);       }       return (*HS)->data;   }      //5、检查链栈是否为空   int EmptyStack(struct sNode** HS)   {       if (*HS == NULL)           return 1;       else           return 0;   }      //6、清除链栈为空   void ClearStack(struct sNode** HS)   {       struct sNode *cp, *np;       cp = *HS;       while (cp != NULL)       {           np = cp->next;           free(cp);           cp = np;       }       *HS = NULL;   }      //主函数   void main()   {       struct sNode *a;       int x = 0;       int m[8] = {3, 8, 5, 17, 9, 30, 15, 22};       printf("当前序列：3,8,5,17,9,30,15,22\n");       InitStack(&a);       while (x != 8)       {           Push(&a, m[x]);           x++;       }       printf("逆序列为：");       while (!EmptyStack(&a))           printf("%d,", Pop(&a));       printf("\n");       ClearStack(&a);   }   运行结果：

4、队列概念

队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入（队尾），在表的另一端进行删除（队首）。

5、队列的顺序存储结构和操作实现（循环列队）

如上图，当队列处于图（d）的状态时不可再插入元素，不然就越界了，但实际队列空间并未占满，为了解决这个问题，就有了循环队列，如下图：

图片展示的很详细，为了区分队空和队满，我们采取少用一个元素空间，约定以“对头指针在队尾指针的下一位置（指环状的下一位置）上”作为队列满状态的标志。

                                  空队列时：Q.front = Q.rear = 0;

                                   一般情况时：入队一个元素，尾指针后移一次，出队一个元素，头指针后移一次。

                                   队列满时：( Q.rear + 1 ) % MaxSize == Q.front （如图中的情况为：（5+1）% 6 == 0）

注意，当情况如下时：

插入a1元素时，Q.rear后移一个位置，但不是直接加1，比如上图 : 5+1=6，但实际位置应为0，所以必须写成：

Q.rear = ( Q.rear + 1) % MaxSize ;

删除元素时的情况同理。

注意：关于内存不足时扩大内存的情况，若Q.rear = Q.MaxSize - 1 时，即 Q.rear 为 5 时，直接扩大内存即可，但当Q.rear ！= Q.MaxSize - 1 时，如下图：（Q.rear,2）

此时，原来位置为0、1位置的元素现在变成了位置为6、7的元素了，而且队尾指针由原来的2变成了8，所以内存扩大后应该进行操作（后面有详细讲解）：

        for (i = 0; i < Q->rear; i++)             Q->queue[i + Q->MaxSize] = Q->queue[i];         Q->rear += Q->MaxSize;

具体情况见下面的程序代码。

下面通过一个实例展示队列顺序存储的操作，包含6种操作

[cpp]  view plain  copy   #include<stdio.h>   #include<stdlib.h>   typedef int ElemType;   struct QueueSq   {       ElemType *queue;   //指向存储队列的数组空间       int front, rear;   //队首指针、队尾指针       int MaxSize;       //queue数组长度   };      //扩展存储空间函数   void againMalloc(struct QueueSq* Q)   {       ElemType *p;       p = realloc(Q->queue, 2*Q->MaxSize*sizeof(ElemType));       if (!p)       {           printf("存储空间用完！\n");           exit(1);       }       Q->queue = p;     //使queue指向新的队列空间       if (Q->rear != Q->MaxSize - 1)       {           int i;           for (i = 0; i < Q->rear; i++)                                               Q->queue[i + Q->MaxSize] = Q->queue[i];   //原队列的尾部内容后移MaxSize个位置           Q->rear += Q->MaxSize;                                    //队尾指针后移MaxSize个位置       }       Q->MaxSize = 2*Q->MaxSize;                                //队列空间修改为原来的2倍       printf("存储空间已为当前2倍！\n");   }   //1、初始化队列   void InitQueue(struct QueueSq* Q, int ms)   {       if (ms <= 0)       {           printf("ms值非法！\n");           exit(1);       }       Q->MaxSize = ms;       Q->queue = malloc(ms*sizeof(ElemType));       if (!Q->queue)       {           printf("内存空间用完！\n");           exit(1);       }       Q->front = Q->rear = 0;    //置队列为空   }      //2、向队列插入元素   void EnQueue(struct QueueSq* Q, ElemType x)   {       if ((Q->rear + 1) % Q->MaxSize == Q->front)  //队空间满           againMalloc(Q);       Q->queue[Q->rear] = x;                       //插入值       Q->rear = (Q->rear + 1) % Q->MaxSize;        //队尾指针后移一个位置   }      //3、从队列中删除元素并返回   ElemType OutQueue(struct QueueSq* Q)   {       ElemType temp;       if (Q->front == Q->rear)       {           printf("队列已空，无法删除！\n");           exit(1);       }       temp = Q->queue[Q->front];                  //保存队首元素值       Q->front = (Q->front + 1) % Q->MaxSize;     //使队首后移一个位置       return temp;   }      //4、读取队首元素，不改变队列状态   ElemType PeekQueue(struct QueueSq* Q)   {       if (Q->front == Q->rear)       {           printf("队列已空，无法读取！\n");           exit(1);       }       return Q->queue[Q->front];   }      //5、检查一个队列是否为空，若是则返回1，否则返回0   int EmptyQueue(struct QueueSq* Q)   {       if (Q->front == Q->rear)           return 1;       else           return 0;   }      //6、清除一个队列为空，释放动态存储空间   void ClearQueue(struct QueueSq* Q)   {       if (Q->queue != NULL)       {           free(Q->queue);           Q->queue = 0;           Q->front = Q->rear = 0;           Q->MaxSize = 0;       }   }      //主函数   void main()   {       struct QueueSq q;       int a[8] = {3,8,5,17,9,30,15,22};       int i;       InitQueue(&q, 5);       for (i = 0; i < 8; i++)           EnQueue(&q, a[i]);       printf("%d ", OutQueue(&q));       printf("%d \n", OutQueue(&q));       EnQueue(&q, 68);       printf("%d ", PeekQueue(&q));       printf("%d \n", OutQueue(&q));       while (!EmptyQueue(&q))           printf("%d ", OutQueue(&q));       printf("\n");       ClearQueue(&q);   }   运行结果：

为验证和详解上面提到的内存扩大问题，我们把上面的主函数换为如下：

[cpp]  view plain  copy   void main()   {       struct QueueSq q;       struct QueueSq* p = &q;       int a[5] = {3,8,5,17,9};       int i;       InitQueue(&q, 6);       for (i = 0; i < 5; i++)           EnQueue(&q, a[i]);       printf("%d ", OutQueue(&q));       printf("%d ", OutQueue(&q));       printf("%d \n", OutQueue(&q));       EnQueue(&q, 67);       printf("插入了67！\n");       EnQueue(&q, 68);       printf("插入了68！\n");       EnQueue(&q, 69);       printf("插入了69！\n");       EnQueue(&q, 100);       printf("插入了100！\n");       printf("%d ", PeekQueue(&q));          //显示队头元素       printf("\n");       for (i = 0; i < 12; i++)           printf("%d ,", p->queue[i]);     //显示所有元素       printf("\n");       while (!EmptyQueue(&q))           printf("%d ", OutQueue(&q));       printf("\n");       ClearQueue(&q);   }   运行结果：

分析：先是依次入队 3,8,5,17,9 五个元素，然后出队3,8,5三个元素，再然后入队67,68，69三个元素，此时状态如下图的左图，

注意：出队的元素虽然不在队里，但在内存里仍存在，如图中的暗绿色的元素。

下面当要将100入队时，内存空间不够，扩大为原来的2倍，此时队中的尾端位置将发生变化如下右图，（暗绿色元素并不在队里）

此时的队头位置元素仍为 17，一次输出下标从0到11位置的内存内容：如上面的运行结果所示，68,69,5仍存在，下标6，7，8三个位置为别是68,69,100，后面的空间无值。

将队的所有元素出队，结果即为上图的运行结果中的：17,9,67,68,69,100。

至此循环顺序队列的相关内容已经非常清晰了。

6、队列的链接存储结构和操作实现

链队的示意图如下：

下面通过实例展示链队的6种操作

[cpp]  view plain  copy   #include<stdio.h>   #include<stdlib.h>   typedef int ElemType;   struct sNode             //结点类型   {       ElemType data;       //值域       struct sNode* next;  //链接指针域   };   struct QueueLk           //队列链接存储结构类型   {       struct sNode* front; //队首指针       struct sNode* rear;  //队尾指针   };      //1、初始化链队   void InitQueue(struct QueueLk* HQ)   {       HQ->front = HQ->rear = NULL;   }      //2、向链队中插入元素   void EnQueue(struct QueueLk* HQ, ElemType x)   {       struct sNode* newp;       newp = malloc(sizeof(struct sNode));       if (newp == NULL)       {           printf("内存动态空间用完，退出运行！\n");           exit(1);       }       newp->data = x;       newp->next = NULL;       if (HQ->front == NULL)  //若链队为空，则新节点既是队首结点又是队尾结点           HQ->front = HQ->rear = newp;       else       //若链队非空，则依次修改队尾结点的指针域和队尾指针，使之都指向新的队尾结点           HQ->rear = HQ->rear->next = newp;   }      //3、从链队中删除元素并返回   ElemType OutQueue(struct QueueLk* HQ)   {       struct sNode* p;       ElemType temp;       if (HQ->front == NULL)       {           printf("队列为空，无法删除！\n");           exit(1);       }       temp = HQ->front->data;       p = HQ->front;       HQ->front = p->next; //使队首指针指向下一个结点       if (HQ->front == NULL) //若删除后队空，则使队尾指针也变为空           HQ->rear = NULL;       free(p);       return temp;   }      //4、读取队首元素，不改变队列状态   ElemType PeekQueue(struct QueueLk* HQ)   {       if (HQ->front == NULL)       {           printf("队列已空，无法读取！\n");           exit(1);       }       return HQ->front->data;   }      //5、检查一个链队是否为空，若是则返回1，否则返回0   int EmptyQueue(struct QueueLk* HQ)   {       if (HQ->front == NULL)           return 1;       else           return 0;   }      //6、清除链队为空，释放动态存储空间   void ClearQueue(struct QueueLk* HQ)   {      struct sNode* p = HQ->front;      while (p != NULL)  //依次删除队列中的每一个结点，循环结束后队首指针已变为空      {           HQ->front = HQ->front->next;           free(p);           p = HQ->front;      }      HQ->rear = NULL;  //置队尾指针为空   }      //主函数   void main()   {       struct QueueLk q;       int a[8] = {3,8,5,17,9,30,15,22};       int i;       InitQueue(&q);       for (i = 0; i < 8; i++)           EnQueue(&q, a[i]);       printf("%d ", OutQueue(&q));       printf("%d \n", OutQueue(&q));       EnQueue(&q, 68);       printf("%d ", PeekQueue(&q));       printf("%d \n", OutQueue(&q));       while (!EmptyQueue(&q))           printf("%d ", OutQueue(&q));       printf("\n");       ClearQueue(&q);   }   运行结果同循环队列相同，只是链队无需考虑内存空间的大小。