【数据结构】队列 循环队列 双端队列——顺序队列+链式队列完整代码（创建、入队、出队）

2.队列

2.1 队列的定义

• 定义

  只允许在一���进行插入，另一端删除的线性表。

  • 特征：先进先出（First In First Out->FIFO）

  • 重要术语：队头、队尾、空队列

    2.2 队列的顺序存储

    2.2.1 初始化

    • 结构体

      typedef struct{    ElemType data[MaxSize]; //静态数组存放队列元素    int front; //队头指针    int rear; //队尾指针}SqQueue;

      • 初始化

        void InitQueue(SqQueue &Q){    Q.rear=Q.front=0;}

      • 判空

        bool QueueEmpty(SqQueue &Q){    if(Q.rear==Q.front)        return true;    else        return false;}

        2.2.2 循环队列

        • 假溢出问题

          当rear走到队尾，队头出栈后仍然有存储空间。

          所以，根据rear==MaxSize判溢出会导致存储空间的浪费。

        • 用循环队列解决假溢出问题：

          把队列看成一个环，rear走到最后一个存储空间时，会重新回到第一个存储空间重新判断。

          • 用取模运算实现环。

          • 队满实现

            • 注：不能以rear==front来判断队满，因为已经用rear==front这个条件判断空队列，所以判满必须牺牲一个存储单元。

            • 另外一些操作

              • 队首指针进1：Q.front=(Q.front+1)%MaxSize
              • 队尾指针进1：Q.rear=(Q.rear+1)%MaxSize
              • 队列长度：(Q.rear+MaxSize-Q.front)%MaxSize

              • 若要求不能浪费那一块存储空间：

                • 方法一：设置size变量记录队中的元素个数：

                  typedef struct{    ElemType data[MaxSize];     int front,rear;     int size; //队列当前长度}SqQueue;//初始化时rear=front=0;size=0;//队满条件size=MaxSize;//队空条件size=0;

                • 方法二：设置tag记录最新一次的操作是删除还是插入

                  typedef struct{    ElemType data[MaxSize];     int front,rear;     int tag; //最近进行的是删除/插入操作}SqQueue;//tag的定义：//插入操作成功时：tag=1；//删除操作成功时：tag=0。//只有删除操作，才可能导致队空//只有插入操作，才可能导致队满//初始化rear=front=0;tag=0;//队空条件front==rear&&tag==0//队满条件front==rear&&tag==1

                  2.2.3 入队

                  bool EnQueue(SqQueue &Q,ElemType x){    if((Q.rear+1)%MaxSize==Q.front)return false; //队列已满        Q.data[Q.rear]=x; //新元素插入    Q.rear=(Q.rear+1)%MaxSize; //队尾加一取模    return true;}

                  2.2.4 出队

                  bool DeQueue(SqQueue &Q,ElemType &x){    if(Q.rear==Q.front)return false; //队空报错        x=Q.data[Q.front]; //返回出队元素    Q.front=(Q.front+1)%MaxSize; //队头指针后移    return true;}

                  2.2.5 获取队头元素

                  bool GetHead(SqQueue Q,ElemType &x){    if(Q.rear==Q.front)return false;        x=Q.data[Q.front];    return true;}

                  *完整代码 顺序队列

                  #define  _CRT_SECURE_NO_WARNINGS#include#include#define ElemType int#define MaxSize 5typedef struct {ElemType data[MaxSize];int front, rear;}SqQueue;void InitQueue(SqQueue& Q) {Q.front = Q.rear = 0;}bool QueueEmpty(SqQueue& Q) {if (Q.rear == Q.front)return true;elsereturn false;}int Length(SqQueue& Q) {return (Q.rear + MaxSize - Q.front) % MaxSize;}bool EnQueue(SqQueue& Q, ElemType x) {if ((Q.rear + 1) % MaxSize == Q.front)return false;Q.data[Q.rear] = x;Q.rear = (Q.rear + 1) % MaxSize;return true;}bool DeQueue(SqQueue& Q,ElemType &x) {if (Q.rear == Q.front)return false;x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;return true;}bool GetHead(SqQueue Q, ElemType& x) {if (Q.rear == Q.front)return false;x = Q.data[Q.front];return true;}//从队头开始打印void PrintQ(SqQueue Q) {int p = Q.front;while (p!=Q.rear) {printf("%d ", Q.data[p]);p = (p +1) % MaxSize;}printf("\n\n");}int main(){SqQueue Q;InitQueue(Q);printf("入栈：\n");EnQueue(Q, 1);EnQueue(Q, 2);EnQueue(Q, 3);EnQueue(Q, 4);PrintQ(Q);printf("队列长度：%d\n", Length(Q));printf("出栈：\n");int x;DeQueue(Q, x);printf("出栈元素为：%d\n", x);DeQueue(Q, x);printf("出栈元素为：%d\n", x);PrintQ(Q);GetHead(Q, x);printf("栈顶元素：%d\n", x);printf("循环队列测试：\n");EnQueue(Q, 5);EnQueue(Q, 6);EnQueue(Q, 7);PrintQ(Q);DeQueue(Q, x);PrintQ(Q);}

                  2.3 队列的链式存储

                  • 就是一个有队头指针和队尾指针的单链表。

                    //链式队列结点typedef struct LinkNode{    ElemType data;    struct LinkNode *next;}LinkNode;//链式队列typedef struct{    LinkNode *front,*rear;}LinkQueue;

                    *完整代码 链队

                    #define  _CRT_SECURE_NO_WARNINGS#include#include#define ElemType inttypedef struct LinkNode{ElemType data;struct LinkNode* next;}LinkNode;typedef struct {LinkNode* front, * rear;}LinkQueue;void InitQueue(LinkQueue& Q) {Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));Q.front->next = Q.rear->next = NULL;}bool isEmpty(LinkQueue& Q) {if (Q.front == Q.rear)return true;elsereturn false;}void EnQueue(LinkQueue& Q, ElemType x) {LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode));p->data = x;p->next = NULL;Q.rear->next = p;Q.rear = p;}bool DeQueue(LinkQueue& Q, ElemType& x) {if (Q.front == Q.rear)return false; //空栈LinkNode* p = Q.front->next;x = p->data;Q.front->next = p->next;if (Q.rear == p)Q.rear = Q.front; //若原队列中只有一个结点，则删除后变空free(p);return true;}void PrintQ(LinkQueue& Q) {LinkNode* p = Q.front->next;while (p != NULL) {printf("%d ", p->data);p = p->next;}printf("\n\n");}int main() {LinkQueue Q;InitQueue(Q);printf("入栈：\n");EnQueue(Q, 1);EnQueue(Q, 2);EnQueue(Q, 3);EnQueue(Q, 4);PrintQ(Q);printf("出栈：\n");int x;DeQueue(Q, x);printf("出栈元素为：%d\n", x);DeQueue(Q, x);printf("出栈元素为：%d\n", x);PrintQ(Q);}

                    2.4 双端队列

                    • 定义

                      也是插入和删除受限的线性表：

                      • 还有输入受限或输出受限的双端队列：