队列

特点

只允许在表的一端插入，而在另一端删除
允许插入的一端被称为队尾（rear），允许删除的一端被称为队头（front）
队列遵循先进先出（FIFO）的原则

顺序表实现

建表

typedef int ElemType;
typedef struct {
  ElemType data[MAXSIZE];
  int front;
  int rear;
}Queue;

初始化

void initQueue(Queue *Q){
  Q->front = 0;
  Q->rear = 0;
}

判空

判断首尾相遇即为空（并非为0）

// 判空
int isEmpty(Queue *Q){
  if (Q->front == Q->rear){
    printf("Empty");
    return 1;
  }
  else {
    return 0;
  }
}

出队

// 出队
ElemType dequeue(Queue *Q){
  if (isEmpty(Q)){
    printf("Empty");
    return 0;
  } 
  ElemType e = Q->data[Q->front];
  Q->front++;
  return e;
}

入队

队列不满时才能入队，但有一种特殊情况：

此时队尾在最后，但队头在中间，意味着已经有数据出队，此时队列里仍有位置

这时我们需要将数据移到队头，使队尾向前以便插入元素

// 判断队列是否满
int queueFull(Queue *Q){
  if (Q->front >0){ //说明front在中间，前面还有位置
    int step = Q->front; // 取front的位置
    for (int i = Q->front; i<=Q->rear; i++){ // 遍历已经有元素的位置
      Q->data[i-step] = Q->data[i]; // 向前移动到头
    }
    Q->front = 0; // 让front指向0
    Q->rear = Q->rear - step; // rear往前调整
    return 1;
  }
  else {
    return 0;
  }
}
// 入队
int enqueue(Queue *Q, ElemType e){
  if (Q->rear >=MAXSIZE){
    if (!queueFull(Q)){
      return 0;
    }
  }
  Q->data[Q->rear] = e;
  Q->rear++;
  return 1;
}

注意，该方法时间复杂度较大，对于大量数据可能效率会很低

获取队头元素

// 获取队头元素
int getHead(Queue *Q, ElemType *e){
  if (isEmpty(Q)){
    printf("Empty");
    return 0;
  }
  *e = Q->data[Q->front];
  return 1;
}

动态分配内存

typedef int ElemType;
typedef struct {
  ElemType *data;
  int front;
  int rear;
}Queue;

// 初始化队列
Queue* initQueue(Queue *Q){
  Queue *q = (Queue*)malloc(sizeof(Queue));
  q->data = (ElemType)malloc(sizeof(ElemType)*MAXSIZE);
  Q->front = 0;
  Q->rear = 0;
  return q;
}

循环队列

循环队列可以避免整体移动位置的情况

即让front指向队头的前一个元素，rear指向队尾元素

入队

// 入队
int enqueue(Queue *Q, ElemType e){
  if ((Q->rear+1)%MAXSIZE == Q->front){ // 循环队列判满
    printf("Full");
    return 0;
  }
  Q->data[Q->rear] = e;
  Q->rear = (Q->rear+1)%MAXSIZE; // 循环在队尾加1
  return 1;
}

取余保证在0到MAXSIZE-1的范围内循环下标

填不满的循环队列

有这么一种情况：

在上次入队后，rear+1，队尾到达0位置

此时若再进行入队操作，首先判断(Q->rear+1)%MAXSIZE，结果为1，此时正好满足rear==front意为堆满

但实际上还留有一个位置，用于判断堆满（与队空区分），若不留空则队满与队空的判断条件一样，无法判断

计算元素个数

rear>front

此时元素个数=rear-front

rear>front

分两块计算：0到rear与front到maxsize

即元素个数=rear+1+MAXSIZE-front-1=rear-front+MAXSIZE

综上，计算公式可以写作(rear-front+MAXSIZE)%MAXSIZE

另两种循环队列

此时front指向当前队头元素，rear指向队尾元素的后一个元素

队空：front==rear

队满：front=(rear+1)%MAXSIZE，也要空出一个位置

元素个数：与上一种一样

此时front指向队头元素，rear指向队尾元素

队空：front=(rear+1)%MAXSIZE

入队情况有两种：

第一种是先入队再判满

可以发现当rear==front时，队中有一个元素

为了留一个空位判断队空队满，所以当front==(rear+2)%MAXSIZE时有队满

元素个数：

rear>front

此时元素个数=rear-front+1
rear<front

分两块讨论，0到rear与front到maxsize

即元素个数=rear+1+MAXSIZE-front

综上，元素个数=(rear-front+1+MAXSIZE)%MAXSIZE

链表实现

构建队列

typedef int ElemType;
typedef struct QueueNode{
  ElemType data;
  struct QueueNode *next;
}QueueNode;

typedef struct Queue
{
  QueueNode *front;
  QueueNode *rear;
}Queue;

这里多定义了一个结构体Queue，记录队头与队尾指针，而QueueNode为存储数据的链表

初始化

// 初始化
Queue* initQueue(){
    Queue* q = (Queue*)malloc(sizeof(Queue));
    QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode)); // 定义一个头节点
    node->data = 0; // 头节点的data为0
    node->next = NULL; // 空队列
    q->front = node; // 队头指向头节点
    q->rear = node; // 队尾指向头节点
    return q;
}

入队

使用尾插法，此时认为队头为首节点，队尾为尾节点

创建新节点

让头节点的next指向该节点

尾指针后移一位

// 入队
void enqueue(Queue *q, ElemType e){
  QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
  node->data = e;
  node->next = NULL;
  q->rear->next = node; // 原来队尾指针指向节点的next指向新节点
  q->rear = node; // 队尾指针移到新节点
}

出队

// 出队
void dequeue(Queue *q, ElemType *e){
  QueueNode* node = q->front->next; // 要删除的节点是头节点的后一个节点（对头结点）
  *e = node->data; // 取出要删除的元素
  q->front->next = node->next; // 让头节点的下一个元素指向要删除节点的下一个元素
  if (q->rear == node){ // 若只有一个节点（删除的是尾节点）
    q->rear == q->front; // 讲队列设为空
  }
  free(node);
}

单调队列

假设有一个数组(如[5,2,6,3,7,2,5,3])，使用滑动窗口，通过对l++, r++实现让数字进入进出窗口

单调队列可以实现在滑动窗口每一时刻获得窗口中的最大最小值，以低成本

单调队列通过双端队列实现，假设要求最大值，则双端队列从头到尾依次是从大到小，存储的是元素下标

右侧拓展：

队列为空时，第一个元素的下标进入(0->5)

若下一个元素进入满足严格从大到小，则进入，否则将最尾端元素弹出，直到满足从大到小

左侧收缩：

滑动窗口滑动，则不在指定范围内的下标从队头弹出

由此可以发现，每时最大值应为队头下标对应元素

How？

单调队列维持了每次最值的可能性

满足严格从大到小的顺序的队列保证了在前一个元素从队头弹出的情况下，下一个元素成为最大值

由于窗口不回退，当更大的数进入时，前面比它小的数便没有机会成为某时刻的最大值了，故可以弹出

时间复杂度：最坏\(O(N)\)

红魔咖啡馆

【数据结构】队列

队列

特点