数据结构之队列

队列，是一个特殊的线性表。它有两个位置，头部 front 和末端 end。在队列的末端进行插入元素，称为enqueue。在队列的头部进行删除元素，称为dequeue。

队列遵循着 FIFO(First-In-First-Out)的原则。队列常见的实现方式是圆形缓冲区(circular buffer)和线性表(linked list)。

链表实现

// 单个链表结点存储单个队列项
struct QNode {
  int key;
  struct QNode *next;
}

// 队列，front存储前结点，rear存储后结点
struct Queue {
  struct QNode *front, *rear;
}

// 功能函数创建新的队列结点
struct QNode* newNode(int k) {
  struct QNode *temp = (struct QNode*)malloc(sizeof(struct QNode));
  temp->key = k;
  temp->next = NULL;
  return temp;
}

// 功能函数创建新的队列
struct Queue *createQueue() {
  struct Queue *q = (struct Queue*)malloc(sizeof(struct Queue));
  q->front = q->next = NULL;
  return q;
}

// 入列操作
void enQueue(struct Queue *q, int k) {
  struct QNode *temp = newNode(k);
  if (q->rear = NULL) {
    q->front = q->rear = temp;
    return;
  }
  q->rear->next = temp;
  q->rear = temp;
}

// 出列操作
struct QNode *deQueue(struct Queue *q) {
  if (q->front == NULL) {
    return NULL;
  }
  struct QNode *temp = q->front;
  q->front = q->front->next;

  if (q->front == NULL) {
    q->rear = NULL;
  }
  return temp;
}

循环实现

设循环队列 Q 的容量为 MAXSIZE，初始化队列为空，且 Q.rear 和 Q.front 都等于 0

元素入列时，修改队尾指针 Q.rear = (Q.rear + 1) % MAXSIZE

元素出列时，修改对头指针 Q.front = (Q.front + 1) % MAXSIZE

根据队列操作的定义，当出列操作导致队列为空时，则有 Q.rear==Q.front。若入列操作导致队列满，则 Q.rear==Q.front。所以无法根据 Q.rear 和 Q.front 判断队列状态。两种方式处理：一.设置一个标志 flag。二.牺牲一个存储单元，以’队列的尾指针所指位置的下一个位置是队头指针’表示队列满。

// 循环队列的类型定义
#define MAXSIZE 100
typeof struct {
  int *base;    /* 循环队列的存储空间 */
  int front;    /* 指示队头 */
  int rear;     /* 指示队尾 */
}SqQueue;

// 创建空的循环队列
int InitQueue(SqQueue *Q) {
  Q->base = (int *)malloc(MAXSIZE * sizeof(int));
  if(!Q->base) return -1;
  Q->front = 0;
  Q->rear = 0;
  return 0;
}

// 入列操作
int EnQueue(SqQueue *Q, int e)  {
  if((Q->rear + 1) % MAXSIZE == Q->front) return -1;
  Q->base[Q->rear] = e;
  Q->rear = (Q->rear + 1) % MAXSIZE;
  return 0;
}

// 出列操作
int DeQueue(SqQueue *Q, int *e) {
  if (Q->rear == Q->front) return -1;
  *e = Q->base[Q->front];
  Q->front = (Q->front + 1) % MAXSIZE;
  return 0;
}