FIFO 队列的链表和数组实现

数据结构

FIFO （First-in, First-out，先进先出）队列：当执行delete操作时删除那些呆在队列中时间最长的元素。
FIFO 队列是这样一个ADT，包含两个基本操作：插入（put）一个新的项、删除（get）一个最早插入的项。

一、FIFO队列的链表实现

FIFO 队列和下堆栈的区别在于新项的插入是在尾部，而不是在头部。因此实现程序要保存一个指向链表最后一个节点的尾指针tail ，因此当Put操作时，将tail 指针指向的next 指向新节点，然后更新tail指针，让它指向那个新的节点。

FIFO_LinkList.cpp

/************************************************************* 
功能：先进先出队列的链表形式实现：Init、Put、Get操作 
说明：  从头部Get，从尾部Put 
时间： 2015/02/03 
作者： quinn 
**************************************************************/  
#include<stdio.h>  
#include<malloc.h>  
#include<stdlib.h>  
typedef int Item;  
typedef struct Node Node;  
typedef Node* Queue;  
struct Node //节点结构  
{  
    Item item;  
    Node* next;  
};  
static int maxN = 10;  
static Queue q = NULL;  
static Node* tail = NULL;  
//新建一个节点  
Node* NewNode(Item item, Node* Next) // Next为插入的后一节点  
{  
    Node* x = (Node*)malloc(sizeof(*x));//被插入的节点  
    x->item = item;  
    x->next = Next;  
    return x;  
}  
//队列初始化  
void QueueInit(int maxN)  
{  
    q =  NULL;  
}  
//判断队列是否为空  
int QueueIsEmpty()  
{  
    return (q == NULL);  
}  
//put操作  
void QueuePut( Item item)  
{  
    if(QueueIsEmpty())  
    {  
        q = (tail = NewNode(item, q));  
    }  
    else  
    {  
        tail->next = NewNode(item, tail->next);  
        tail = tail->next;  
    }  
    printf("Put: %d\n", item);  
}  
//get操作  
Item QueueGet()  
{  
    if(q == NULL)  
    {  
        printf("序列为空！\n");  
        return -1;  
    }  
    Item firstItem = q->item;//序列的头元素  
    Node* tmpNode = q;  
    q = q->next;  
    free(tmpNode);  
    return firstItem;  
}  
//测试程序  
int main()  
{  
    QueueInit(maxN);  
    QueuePut(2);  
    QueuePut(3);  
    QueuePut(4);  
    printf("\n");  
    printf("Get: %d\n", QueueGet());  
    printf("Get: %d\n", QueueGet());  
    printf("Get: %d\n", QueueGet());  
    printf("Get: %d\n", QueueGet());  
    system("pause");  
    return 0;  
}  

运行结果：

二、FIFO队列的数组实现

队列中的内容是数组中从head到tail的所有元素，到tail到达数组尾部时回卷到0，此程序的实现过程需要考虑队列满和队列空两种特殊状态，
本文采用2种方式实现：

1）设定FIFO队列的数组大小比客户将在队列放置的元素最大数目大1

（From：《算法：C语言实现》P93）

当head和tail重合时为空；当tail+1和head重合时为满
FIFO_Array_1.cpp

/************************************************************* 
From：《算法：C语言实现》 P93 
功能：先进先出队列的数组形式实现：Init、Put、Get操作 
说明：  1）队列中的内容是数组中从head到tail的所有元素，到tail到达数组尾部时回卷到0 
    2）设定FIFO队列的数组大小比客户将在队列放置的元素最大数目大1， 
    当head和tail重合时为空；当head和tail+1重合时为满 
时间： 2015/02/03 
作者： quinn 
**************************************************************/  
#include<stdio.h>  
#include <stdlib.h>  
const int maxN = 10; //FIFO size  
typedef int Item;  
static Item *q; //队列  
static int head, tail, N;  
//队列初始化，初始化数组、头尾索引  
void QueueInit(int maxN)  
{  
    q = (Item*)malloc(sizeof(*q) * (maxN+1));  
    N = maxN + 1;  
    head = N;  
    tail = 0;  
}  
//检查队列是否为空  
int QueueIsEmpty()  
{  
    return (head % N) == tail;  // Get操作中head++位于%操作之后；Put操作中tail++位于%操作之前  
}  
int QueueIsFull()  
{  
        return (tail + 1)%N == head % N;  
}  
//推入队列，Put操作  
void QueuePut(Item item)  
{  
    if (QueueIsFull())  
    {  
        printf("队列已满，Put: %d 操作失败\n", item);  
        return;  
    }  
    q[tail++] = item;  
    tail %= N;  
    printf("Put: %d\n", item);  
}  
//出队列，Get操作  
Item QueueGet()  
{  
    if (QueueIsEmpty())  
    {  
        printf("此队列现为空，Get操作失败，返回-1\n");  
        return -1;  
    }  
    head %= N;  
    return q[head++];  
}  
//测试程序  
int main()  
{  
    QueueInit(maxN);  
    for (int i = 0; i <= 10; i++)  
    {  
        QueuePut(i);  
    }  
    printf("\n");  
    printf("Get: %d\n\n", QueueGet());  
    for (int i = 0; i < 10; i++)  
    {  
        printf("Get: %d\n", QueueGet());  
    }  
    system("pause");  
    return 0;  
}  

运行结果

2）设定FIFO队列的数组大小和客户将在队列放置的元素最大数目相等

当put操作导致tail和head重合时，设定满标志flag_full = 1;(初始化设定flag_full
= 0)
当get操作导致tail和head重合时，设定空标志flag_empty = 1；(初始化设定flag_empty = 1)

FIFO_Array_2.cpp

/************************************************************* 
功能：先进先出队列的数组形式实现：Init、Put、Get操作 
说明：1）设定FIFO队列的大小，队列中的内容是数组中从head到tail的 
            所有元素，到tail到达数组尾部时回卷到0 
时间： 2015/02/03 
作者： quinn 
**************************************************************/  
#include<stdio.h>  
#include <stdlib.h>  
const int maxN = 10; //FIFO size  
typedef int Item;  
static Item *q;  
static int head, tail;  
static int flag_full = 0, flag_empty = 1; //队列满空标志  
//队列初始化，初始化数组、头尾索引  
void QueueInit(int maxN)  
{  
    printf("初始化FIFO大小为%d\n",maxN);  
    q = (Item*)malloc(sizeof(*q) * maxN);  
    head = 0;  
    tail = 0;  
}  
//推入队列，Put操作  
void QueuePut(Item item)  
{  
    if (flag_full)  
    {  
        printf("队列已满，Put：%d 操作失败\n",item);  
        return;  
    }  
    q[tail++] = item;  
    tail %= maxN;  
    printf("Put: %d\n", item);  
    flag_empty = 0; //put后非空  
    if (tail  == head)//Put操作导致的head和tail重合时，队列满  
    {  
        flag_full = 1;  
    }  
}  
//出队列，Get操作  
Item QueueGet()  
{  
    if (flag_empty)  
    {  
        printf("队列为空，Get操作失败，返回-1\n");  
        return -1;  
    }  
    head %= maxN;  
    flag_full = 0; //Get操作成功，满标志设为0  
    if ((head+1) % maxN == tail) //Get导致head+1和tail重合，队列空  
    {  
        flag_empty = 1;  
    }  
    return q[head++];  
}  
//测试程序  
int main()  
{  
    QueueInit(maxN);  
    for (int i = 0; i <= 10; i++)  
    {  
        QueuePut(i);  
    }  
    printf("\n");  
    printf("Get: %d\n\n", QueueGet());  
    for (int i = 0; i <= 10; i++)  
    {  
        printf("Get: %d\n", QueueGet());  
    }  
    system("pause");  
    return 0;  
}  

运行结果：

FIFO队列ADT的get操作和put操作不论使用数组还是链表都能在常数时间内实现。

参考资料：《算法：C语言实现》 P93