3队列

3.1队列定义：先进先出

队列是一种只允许前端（front，队首）进行删除操作，而在后端（rear，队尾）进行插入操作的数据结构。正是因为规定了从队首删除队尾插入的性质，因此最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的数据结构。

队列是一种使用很广泛的数据结构，比如操作系统的进程调度就是用的队列，图的广度优先遍历也使用的是队列。

队列也是一种很好理解的数据结构。比如人们去银行办事，就是排成一队，新到的人从队尾插入，而银行工作人员都是从队首开始受理业务，受理完，队首的人就离开队列（从队列中删除）。

3.2队列结构：尾部插入，前端删除

如下图所示，队列底层数据结构可以使用链表或者数组。在使用链表的时候，如下图左边部分所示，用front和rear两个指针分别指向队列的前端和后端。在使用数组的时候，分别用2个整数front和rear做数组的下标，指向数组的前端和尾端。

需要注意的是，如果用数组作为队列的底层结构，那么在不断的插入元素和删除元素的时候，数组的内存空间将会不断的向上滑动（如下图中间部分所示），这在实际应用过程中肯定是不好的，因此假如数组的长度为MAX，通过用rear=(rear+1)%MAX和front=(front+1)%MAX来移动数组的前端和尾端，可以限制它们在数组的当前空间，这样就构成了一个循环队列（如下图右边部分所示）。

3.3队列基本操作

队列包含创建，入队，出队，队空判断，对满判断等操作。

1. 创建

int CreateQue();

用于创建一个队列，一般需要初始化队列的前端和后端指针。

2. 入队

int EnQueue(int e);

将特定的元素e从队列的尾部插入。

3. 出队

int DeQueue(int *e);

获取队列头部的数据并从队列删除。

4. 判断队列满

int IsQueueFull();

判断队列是否已满，如果队列满了就不能再从尾部插入数据了，只对基于数组的队列有效。

5. 判断队列空

int IsQueueEmpty();

判断队列是否为空，如果队列为空，就不能从队首删除数据了，在构造基于链表的队列的时候，队列为空，插入第一个元素的时候，也需要特别的处理。

3.4基于链表的链队

链表结点的存储结构如下：

typedef struct _node
{
    int value;
    struct _node *next;
}node,*pnode;

其中值的部分存放的是一个整数data，这部分数据可以自己再定义，增减。

node  *front=NULL;   // 队头指针，由于是全局变量，请注意多线程安全
node  *rear=NULL;    // 队尾指针，由于是全局变量，请注意多线程安全

在实现队列的基本操作的时候，最好是先画出队列的图形，如上图所示，然后按照图形来写各种操作的代码，思路就会比较清晰（注意，在多线程环境下，下面的代码没有提供加锁机制，需要另外处理）。

// 创建队列
int CreateQueue()
{
    front = rear = NULL; // 将front和rear置为NULL
    return 1;
}
// 判断队列是否为空
int IsQueueEmpty()
{
    if(front==NULL&&rear==NULL) // front和rear等于NULL是队列为空的标志
    {
        return 1;
    }
    return 0;
}
// 入队
int EnQueue(int e)
{
    node *p = (node *)malloc(sizeof(node));
    if(p==NULL)
    {
        return -1;
    }
    memset(p,0,sizeof(node));
    p->value = e;
    p->next = NULL;
    if(IsQueueEmpty()) // 队列为空，直接将rear和front指向该结点
    {
        rear=front=p;
        return 1;
    }
    rear->next = p;   // 队列不为空，插入尾部
    rear = p;
    return 1;
}
// 出队
int DeQueue(int *e)   // 必须传指针，否则出队的值无法获取
{
    if(IsQueueEmpty())
    {
        return -1;
    }
    if(e==NULL)
    {
        return -1;
    }
    // 只有一个结点的时候
    if(rear==front && rear!=NULL)
    {
        *e = rear->value;
        free(rear);
        front=rear=NULL;
        return 1;
    }
    // 多个结点的时候
    *e = front->value;
    node *q = front;
    front = front->next;
    free(q);
    return 1;
}
// 遍历队列
void TraverseQueue()
{
    while(!IsQueueEmpty())
    {
        int value;
        DeQueue(&value);
        printf("%d ",value);
    }
    printf("\n");
}
// 队列测试代码
int _tmain(int argc, _TCHAR* argv[])
{
    int value;
    CreateQueue();
    EnQueue(3);
    EnQueue(1);
    EnQueue(0);
    EnQueue(5);
    DeQueue(&value);
    printf("value:%d\n", value);
    EnQueue(18);
    EnQueue(27);
    DeQueue(&value);
    printf("value:%d\n", value);
    DeQueue(&value);
    printf("value:%d\n", value);
    TraverseQueue();
    return 0;
}

3.5 基于数组的循环队列

如下图所示，基于数组的循环队列，有3种形态：

1 队列为空，这个时候front等于rear，如下图左边部分所示。

2 正常形态，这个时候，front指向队首元素，rear指向队尾元素的下一个位置，如下图中间部分所示。

3 队列满，这个时候，队尾指针指向队首指针的前一个位置（空位）。如下图右边部分所示。

因此，循环队列在队列满的时候，会浪费一个空间，这主要是为了区分队列空和队列满的2个状态的。否则，如果最后一个空间也存放元素，那么rear在加1后，就和front相等了，这和队列为空的判断条件是冲突的。

在实现基于数组的队列的基本操作的时候，结合上面3个队列的基本形态来写代码，会显得思路清晰。下面是具体的代码与数据结构（注意，在多线程环境下，下面的代码没有提供加锁机制，需要另外处理）：

#define MAXSIZE 100    // 数组的元素个数
int Queue[MAXSIZE]={0};// 队列的底层数据结构，数组，支持100个元素
int rear = 0;  // 队列后端，插入的位置
int front = 0; // 队列前端，删除的位置
// 创建队列，将前端和后端置0
int CreateQueue()
{
    rear = front = 0;
    return 1;
}
// 判断队列是否为空
int IsQueueEmpty()
{
    return rear==front?1:0; // front等于rear，队列即为空
}
// 判断队列是否满
int IsQueueFull()
{
    return (rear+1)%MAXSIZE == front?1:0;// 注意判断标准
}
// 入队：
int EnQueue(int e)
{
    if(IsQueueFull())
    {
        return -1;
    }
    Queue[rear]=e;
    rear = (rear+1)%MAXSIZE;
    
    return 1;
}
// 出队
int DeQueue(int *e)
{
    if(IsQueueEmpty())
    {
        return -1;
    }
    if (e==NULL)
    {
        return -1;
    }
    *e = Queue[front];
    front = (front + 1)%MAXSIZE;
    
    return 1;
}
// 队列遍历：
void TraverseQue()
{
    while(!IsQueueEmpty())
    {
        int val;
        DeQueue(&val);
        printf("%d ",val);
    }
    printf("\n");
}
// 接口测试：
int _tmain(int argc, _TCHAR* argv[])
{
    for(int i=0;i<200;i++)
    {
        EnQueue(i);
    }
    int val = 0;
    DeQueue(&val);
    printf("val:%d\n",val);
    DeQueue(&val);
    printf("val:%d\n",val);
    TraverseQue();
    
    return 0;
}

本页共219段，4662个字符，7755 Byte(字节)



大

中

小

∧

↑

↓

∨