基础数据结构学习记录：队列

队列（queue）是一种基本的数据结构，属于动态集合（集合在算法操作的过程中能增大、缩小或者发生其他其他变化），实现的是一种先进先出（firdt-in first-out，FIFO）的策略，最先进入的数据最先出来。

关于队列的基本操作有：入队ENQUEUE（属于INSERT操作），出队DEQUEUE（属于DELETE操作）。

可以用一个数组Q[1,...,n]来实现一个最多可以容纳 n-1 个元素的栈。队中包含元素为Q[Q.head,...,Q.tail-1]，其中Q[Q.head]是队头元素，Q[Q.tail-1]是队尾元素。

属性：Q.head指向队头元素；Q.tail指向下一个新元素将要插入的位置（注意这里）。队列的头和尾不一定是断裂的，而是可以形成一个环。

image.png

初始化：Q.head = Q.tail = 1。如果Q.head = Q.tail ，队列为空，此时删除元素则发生数据下溢；Q.head = Q.tail+1，队列为满，此时插入元素则发生数据上溢。

算法：

image.png

程序实现（C）:

#include<stdio.h>
#include<stdbool.h>

// initial
int head = 0;
int tail = 0;

bool Empty(int length)
{
    if((head%length)== (tail%length))
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool Full(int length)
{
    if((head%length) == (tail+1)%length)
    {
        return true;
    }
    else
    {
        return false;
    }
}

int Enqueue(int Q[],int x,int length)
{
    if(Full(length))
    {
        printf("The queue is overflow !\n");
    }
    else
    {
        Q[tail] = x;
        //printf("%d\t",tail);
        printf("%d\n",Q[tail]);
        tail = tail + 1;
    }
}

int Dequeue(int Q[],int length)
{
    if(Empty(length))
    {
        printf("The queue is downflow !\n");
    }
    else
    {
        printf("%d\n",Q[head]);
        head = head + 1;
    }
}

int main()
{
    int Q[10] = {0};
    int i,length;
    
    length = sizeof(Q)/sizeof(Q[0]);
    printf("%d\n",length);
    printf("\n****************tail****************\n");
    if(Empty(length)) printf("The queue is empty now !\n");
    for(i=0; i<11; i++)
    {
        //printf("%d\t",tail);
        Enqueue(Q,i,length);
    }
    if(Full(length)) printf("\nThe queue is full now !\n");
    printf("\n****************head****************\n");
    for(i=0; i<11; i++)
    {
        //printf("%d\t",head);
        Dequeue(Q,length);
    }
    return 0;
}

---

参考《算法导论》