1、队列的基本概念

队列（Queue）：限定仅允许在表中的一端进行插入，而在表中的另一端进行删除的线性表，简称队。向队列插入元素称为入队，向队列删除元素称为出队。基操作的特征是先进先出，故又称为FIFO（First In First Out）的线性表。

2、队列的存储结构与基本运算

2-1 （循环）顺序队列的存储结构与基本运算

队列的基本设定也是不一定都是相同的，这里如下设定：

• 初始时：Q.front = Q.rear = 0；
• 队首指针进1：Q.front = (Q.front+1)%MaxSize;
• 队尾指针进1：Q.rear = (Q.rear+1)%MaxSize;
• 队列长度，元素个数：(Q.rear+MaxSize-Q.front)%MaxSize;
• 队空条件：Q.rear == Q.front
• 队满条件：(Q.rear+1)%MaxSize == Q.front

2-1-1 （循环）顺序队列的存储结构

#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int front, rear;
}SqQueue;
SqQueue Q;

2-1-2 （循环）顺序队列的基本运算

• 初始化队列的代码片段

Q.rear = Q.front = 0;

• 判断队空的代码片段

if(Q.rear == Q.front) return true;
else return false;

• 入列操作的代码片段

if((Q.rear+1)%MaxSize == Q.front)return false;
Q.data[Q.rear] = x;
Q.rear = (Q.rear+1)%MaxSize;

• 出队操作的代码片段

if(Q.rear == Q.front)return false;
x = Q.data[Q.front];
Q.front = (Q.front+1)%MaxSize;

2-2 链式队列的存储结构与基本运算

2-2-1 链式队列的存储结构

typedef struct{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{
    LinkNode *front, *rear;
}LinkQueue;

2-2-2 （双端）链式队列的例子

https://github.com/skywind3000/kcp/blob/master/ikcp.h

//=====================================================================
// QUEUE DEFINITION                                                  
//=====================================================================
#ifndef __IQUEUE_DEF__
#define __IQUEUE_DEF__

struct IQUEUEHEAD {
    struct IQUEUEHEAD *next, *prev;
};

typedef struct IQUEUEHEAD iqueue_head;


//---------------------------------------------------------------------
// queue init                                                         
//---------------------------------------------------------------------
#define IQUEUE_HEAD_INIT(name) { &(name), &(name) }
#define IQUEUE_HEAD(name) \
    struct IQUEUEHEAD name = IQUEUE_HEAD_INIT(name)

#define IQUEUE_INIT(ptr) ( \
    (ptr)->next = (ptr), (ptr)->prev = (ptr))

#define IOFFSETOF(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

#define ICONTAINEROF(ptr, type, member) ( \
        (type*)( ((char*)((type*)ptr)) - IOFFSETOF(type, member)) )

#define IQUEUE_ENTRY(ptr, type, member) ICONTAINEROF(ptr, type, member)


//---------------------------------------------------------------------
// queue operation                     
//---------------------------------------------------------------------
#define IQUEUE_ADD(node, head) ( \
    (node)->prev = (head), (node)->next = (head)->next, \
    (head)->next->prev = (node), (head)->next = (node))

#define IQUEUE_ADD_TAIL(node, head) ( \
    (node)->prev = (head)->prev, (node)->next = (head), \
    (head)->prev->next = (node), (head)->prev = (node))

#define IQUEUE_DEL_BETWEEN(p, n) ((n)->prev = (p), (p)->next = (n))

#define IQUEUE_DEL(entry) (\
    (entry)->next->prev = (entry)->prev, \
    (entry)->prev->next = (entry)->next, \
    (entry)->next = 0, (entry)->prev = 0)

#define IQUEUE_DEL_INIT(entry) do { \
    IQUEUE_DEL(entry); IQUEUE_INIT(entry); } while (0)

#define IQUEUE_IS_EMPTY(entry) ((entry) == (entry)->next)

#define iqueue_init     IQUEUE_INIT
#define iqueue_entry    IQUEUE_ENTRY
#define iqueue_add      IQUEUE_ADD
#define iqueue_add_tail IQUEUE_ADD_TAIL
#define iqueue_del      IQUEUE_DEL
#define iqueue_del_init IQUEUE_DEL_INIT
#define iqueue_is_empty IQUEUE_IS_EMPTY

#define IQUEUE_FOREACH(iterator, head, TYPE, MEMBER) \
    for ((iterator) = iqueue_entry((head)->next, TYPE, MEMBER); \
        &((iterator)->MEMBER) != (head); \
        (iterator) = iqueue_entry((iterator)->MEMBER.next, TYPE, MEMBER))

#define iqueue_foreach(iterator, head, TYPE, MEMBER) \
    IQUEUE_FOREACH(iterator, head, TYPE, MEMBER)

#define iqueue_foreach_entry(pos, head) \
    for( (pos) = (head)->next; (pos) != (head) ; (pos) = (pos)->next )


#define __iqueue_splice(list, head) do {    \
        iqueue_head *first = (list)->next, *last = (list)->prev; \
        iqueue_head *at = (head)->next; \
        (first)->prev = (head), (head)->next = (first);     \
        (last)->next = (at), (at)->prev = (last); } while (0)

#define iqueue_splice(list, head) do { \
    if (!iqueue_is_empty(list)) __iqueue_splice(list, head); } while (0)

#define iqueue_splice_init(list, head) do { \
    iqueue_splice(list, head);  iqueue_init(list); } while (0)

3、队列的应用

3-1 队列在树的层次遍历中应用

3-2 队列在图的广度优先搜索中应用

3-3 队列在计算机系统中的应用

Wu_Being 博客声明：本人博客欢迎转载，请标明博客原文和原链接！谢谢！
《【数据结构4】队列》
http://blog.csdn.net/u014134180/article/details/55506242

如果你看完这篇博文，觉得对你有帮助，并且愿意付赞助费，那么我会更有动力写下去。