1. 定义：

  1.         一种可是实现“先进先出”的存储结构

2. 分类：

2.1 链式队列：用链表实现

2.2 静态队列：用数组实现

静态对流通常都必须是循环队列，为了减少内存浪费。

2.2.1 循环队列的讲解：

1、 静态队列为什么必须是循环队列

2、 循环队列需要几个参数来确定及其含义

需要2个参数来确定

  • front
  • rear

    3、 循环队列各个参数的含义

    2个参数不同场合不同的含义不同? 建议初学者先记住，然后慢慢体会
    1）队列初始化
    front和rear的值都是零
    2）队列非空
    front代表队列的第一个元素
    rear代表了最后一个有效元素的下一个元素
    3）队列空
    front和rear的值相等，但是不一定是零
    4、 循环队列入队伪算法讲解
    两步完成：
    1）将值存入r所代表的位置
    2）将r后移，正确写法是 rear = (rear+1)%数组长度
    错误写法：rear=rear+1;
    5、 循环队列出队伪算法讲解
    front = (front+1) % 数组长度
    6、 如何判断循环队列是否为空
    如果front与rear的值相等，则队列一定为空
    7、 如何判断循环队列是否已满
    预备知识：
    front的值和rear的值没有规律， 即可以大，小，等。
    两种方式：
    1、多增加一个表标识当前队列有效元素个数的参数
    2、少用一个队列中的元素（才一个，不影响的）
    通常使用第二种方法
    如果rear和front的值紧挨着，则队列已满
    用C语言伪算法表示就是：
    if( (rear+1)%数组长度== fron )
    已满
    else
    不满

    3. 队列算法：

    3.1 入队

    3.2 出队

    3.3 队列的具体应用：

    所有和事件有关的操作都有队列的影子。
    （例如操作系统认为先进来的先处理）

    4. 静态队列（循环队列）数组实现code

    ```c /*
    • @Descripttion: This case is a sub which the loop queue was created by using an array.
    • @version: Beta-v1.0.0
    • @Author: jhong.tao
    • @Date: 2020-12-03 20:59:32
    • @LastEditTime: 2020-12-15 18:57:28 */

include

include

include

/**

  • @name: struct ArrayQueue
  • @brief: A queue variate of the struct type is defined which include array, length,front and rear.
  • @param {pArr:The pArr is a array of the new queue.}
  • @param {lenght:The param of the length is the length of the array, but the effective max length of this queue is the number of this length - 1.}
  • @param {front:The param of the front is the head pointer of this queue.}
  • @param {rear:The param of the rear is the rear pointer of this queue.} / typedef struct ArrayQueue{ int pArr; int lenght; int front; int rear; }queue,*pQueue;

// function declaration bool initQueue(pQueue pq, int length); bool isEmptyQueue(pQueue pq); bool isFullQueue(pQueue pq); bool putQueue(pQueue pq, int val); int pollQueue(pQueue pq); int getLenghtQueue(pQueue pq); void traverseQueue(pQueue pq); void clearQueue(pQueue pq); void destroyQueue(pQueue pq);

int main(void){ queue q; initQueue(&q,5); putQueue(&q,1); putQueue(&q,2); traverseQueue(&q);

  1. printf("poll:%d\n",pollQueue(&q));
  2. putQueue(&q,3);
  3. printf("length:%d\n",getLenghtQueue(&q));
  5. traverseQueue(&q);
  6. destroyQueue(&q);
  7. return 0;

}

/**

  • @name: void destroyQueue(pQueue pq)
  • @brief:The task of this function is to destroy this current queue.
  • @param {pQueue pq:pq is the pointer of the current queue.}
  • @return {void} */ void destroyQueue(pQueue pq){ if(pq == NULL || pq->pArr == NULL)
    1.  return;
    free(pq->pArr); pq->pArr = NULL; free(pq); pq = NULL; }

/**

  • @name: void clearQueue(pQueue pq)
  • @brief: The task of this function is to clear this current queue.
  • @param {pQueue pq:pq is the pointer of the current queue.}
  • @return {void} */ void clearQueue(pQueue pq){ if(pq == NULL || isEmptyQueue(pq))
    1.  return;
    pq->front = pq->rear = 0; }

/**

  • @name: void traverseQueue(pQueue pq)
  • @brief: The task of this function is to traverse the current queue.
  • @param {pQueue pq:pq is the pointer of the current queue.}
  • @return {void} */ void traverseQueue(pQueue pq){ if(pq == NULL || isEmptyQueue(pq))
    1.  printf("队列长度为0\n");
    int tempFront = pq->front; while(tempFront != pq->rear){
    1.  printf("%d  ",*(pq->pArr+tempFront));
    2.  tempFront = (tempFront+1) % pq->lenght;
    } printf(“\n”); }

/**

  • @name: int getLenghtQueue(pQueue pq)
  • @brief: The task of this function is to get the effective length of this current queue.
  • @param {pQueue pq:pq is the pointer of the current queue.}
  • @return {return the length of this current queue or return false.} */ int getLenghtQueue(pQueue pq){ if(pq == NULL)
    1.  return false;
    if(pq->rear >= pq->front)
    1.  return pq->rear - pq->front;
    return pq->rear + pq->lenght - pq->front; }

/**

  • @name: int pollQueue(pQueue pq)
  • @brief: The task of this function is to poll an element from the current queue.
  • @param {pQueue pq:pq is the pointer of the current queue.}
  • @return {int element:the element is the element of current polling or returns false } */ int pollQueue(pQueue pq){ if(pq == NULL || isEmptyQueue(pq))
    1.  return false;
    int element = *(pq->pArr+pq->front); pq->front = (pq->front+1) % pq->lenght; return element; }

/**

  • @name: bool putQueue(pQueue pq, int val)
  • @brief: The task of this function is to put a value in this queue.
  • @param {pQueue pq:}
  • @param {int val:}
  • @return {true or false} */ bool putQueue(pQueue pq, int val){ if(pq == NULL || isFullQueue(pq))
    1.  return false;
    *(pq->pArr+pq->rear) = val; pq->rear = (pq->rear+1) % pq->lenght; return true; }

/**

  • @name: bool initQueue(pQueue pq, int length)
  • @brief: The task of this function is to create a queue.
  • @param {pQueue pq:pq is the pointer of the current queue.}
  • @param {int length:The param of length is the length of the new queue.}
  • @return {true or false} */ bool initQueue(pQueue pq, int length){ if(pq == NULL)
    1.  return  false;
    pq->pArr = (int)malloc(sizeof(int)length);
    if(pq->pArr == NULL)
    1.  return false;
    pq->front = 0; pq->rear = pq->front; pq->lenght = length; return true; }

/**

  • @name: bool isEmptyofQueue(pQueue pq)
  • @brief: The task of this function is to determine whether the current queue is empty.
  • @param {pQueue pq:pq is the pointer of the current queue.}
  • @return {true of false} */ bool isEmptyQueue(pQueue pq){ if(pq == NULL || pq->pArr == NULL)
    1.  exit(-1);
    if(pq->front == pq->rear)
    1.  return true;
    return false; }

/**

  • @name: bool isFullQueue(pQueue pq)
  • @brief: The task of this function is to determine whether the current queue is full.
  • @param {pQueue pq:pq is the pionter of the current queue.}
  • @return {true or false} */ bool isFullQueue(pQueue pq){ if(pq == NULL || pq->pArr == NULL)
    1.  exit(-1);
    if(pq->front == (pq->rear+1)%pq->lenght)
    1.  return true;
    return false; } ```