数据结构之队列

1 队列的定义

队列是先进先出（FIFO）的线性表，允许队列的一段删除元素，另外一赌博插入元素。插入元素一端叫队尾，删除元素的一端叫对头。

2 队列的存储结构

2.1 顺序存储结构

和栈一样也是通过一组连续存储地址用来存储队列的元素，不同是队列的元素删除和插入操作是两段进行的，需要设置队头指针和队尾指针，分别指向当前的对头元素和队尾元素。

我们可以将用顺序存储的队列称为顺序队列，下面通过一组图示来看看顺序队尾指针、队头指针和元素之间的关系。

空队列 a1,a2,a3入队 a1,a2出队

由于顺序队列的存储空间是提前设定好的,队尾指针会有一个上限值(???),就不能通过修改队尾指针插入新的元素了,如果将顺序队列想象成一个环状结构,则会使得入队和出队的操作简单,也不会出现队尾出现上限值的情况,可以将这种队列称为循环队列。

循环队列是特殊的顺序队列,是构想出来的,在初始化队列时也需要设定存储空间大小(MAXSIZE),空队列或者队满时都有Q.front = Q.rear,队尾插入元素有Q.rear = (Q.rear + 1)% MAXSIZE,队头删除元素有O.front = ( O.front + 1)% MAXSIZE。

#include <stdio.h>
#include <stdlib.h>

#define QUEUEMAXNUM  100

typedef struct{
    
    // 队列存储空间的首地址
    int *base;
    int front,rear;

}TestQueue;

// 初始化一个循环队列 队列元素是个int型

void initQueue(TestQueue*queue){

   queue ->base =(int *) malloc(QUEUEMAXNUM *sizeof(int));

   queue->front = 0;
   queue->rear = 0;
}

// 判断队列是否为空

int isEmptyQueue(TestQueue *queue){

  // 1 为空
  return queue->front  == queue->rear;
}

// 入队 -1 失败 0 成功

int enQueue(TestQueue *queue,int elem){
  

  // 判断是否队满 规则:,牺牲存储空间,如果队尾指针指向下一个位置为队头指针 则为堆满

  if((queue->rear + 1)%QUEUEMAXNUM == queue->front)  return -1;

  queue->base[queue->rear] = elem;
 
  printf("入队元素 %d\n",queue->base[queue->rear]);

  queue->rear = (queue->rear + 1)%QUEUEMAXNUM;
    
    return 0;

}

// 出队

int delQueue(TestQueue *queue,int *e){
 
   if(isEmptyQueue(queue)) return -1;

   *e = queue->base[queue->front];
    

   queue->front =( queue->front + 1)%QUEUEMAXNUM;
    
    return 0;

}

int main(int argc,char *argv[]){

    TestQueue *queue;
    
    queue = (TestQueue *)malloc(sizeof(TestQueue));

    initQueue(queue);
    // 1  2  3入队
    printf("入队 %d\n",enQueue(queue,1));
 
    printf("入队 %d\n",enQueue(queue,2));
    
    printf("入队 %d\n",enQueue(queue,3));

    //  1 2  出队
    int *elemet = (int *)malloc(sizeof(int)) ;
    printf("出队 删除队头元素 %d\n",delQueue(queue,elemet));
    printf("出队 删除队头元素 %d\n",delQueue(queue,elemet));
   
    printf("出队 %d\n",elemet[0]);
    //// ????????
     printf("queue 的头队列的值%d\n",queue->base[0]);
    
    return 0;

}

2.2 链式存储

队列通过链式存储也叫做链队列,为了便于操作,可给链队列添加一个头结点,令头指针指向头节点。

3 队列的使用

适用于排队,操作系统处理打印机等,在iOS也有很多应用,比如事件传递过程中,UIApplication的事件列表就是通过队列来管理,并分发给keywindow的。