简介队列是计算机科学中一种重要的线性数据结构它遵循先进先出FIFO - First In First Out的原则。队列的原理和现实生活中的排队现象是一样的比如你在超市买了菜排队去结账刚来的人只能在队尾排着在队列中叫入队结完账的人走出去在队列中叫出队。队列在计算机系统中有着广泛的应用从操作系统的进程调度、磁盘I/O管理到网络数据包传输、消息队列系统再到算法中的广度优先搜索等队列都扮演着不可或缺的角色。理解队列的原理和实现对于编写高效、可靠的程序至关重要。一、队列的基本概念队列是具有一定操作约束的线性表。具体的操作有以下插入和删除只能在一端插入(队尾插入)另一端删除(队头删除)。数据插入入队列数据删除出队列先进先出FIFO先来先服务二、队列的抽象类型操作集长度为MaxSize的队列Q Queue队列元素item ElementType1.Queue CreatQueue(int MaxSize) //生成长度为MaxSize的空队列2.int IsFullQ(Queue Q,int MaxSize) //判断队列Q是否已满3.void AddQ(Queue Q,ElementType item) //将数据元素item插入队列Q中4.int IsEmptyQ(Queue Q) //判断队列Q是否为空5.ElementType DeleteQ(Queue Q) //将队列数据元素从队列中删除并返回三、什么是队列的顺序存储队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front及一个记录队列尾位置的变量rear组成。这是一个顺序环状队列结构如下图顺序环状队列的数据从尾部插入过程如下图所示这里仅使用n-1个数组空间便于判断队列状态是否空或满。四、顺序循环队列实现4.1 数据结构定义#define MaxSize //存储元素的最大个数 struct Qnode { ElementType Data[MaxSize]; int rear; int front; }; typedef struct Qnode *Queue;4.2 入队列void AddQ(Queue Q,ElementType item) { if((Q-rear1)%MaxSize Q-front) //队列满 { printf(队列满\r\n); return; } Q-rear (Q-rear1)%MaxSize; Queue-Data[Q-rear] item; }4.3 出队列ElementType DeleteQ(Queue Q) { if(Q-rear Q-front) { printf(队列空\r\n); return; } Q-front (Q-front1)%MaxSize; return Q-Data[Q-front]; }五、队列的链式存储实现队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行队列指针front和rear应该分别指向链表哪一头呢4.1 定义struct Node { ElementType Data; struct *Next; }; struct QNode //链队列结构 { struct Node *rear; //指向队尾结点 struct Node *front; //指向对头节点 }; typedef struct QNode *Queue; Queue PtrQ;队列的链式存储结构入下图所示4.2 不带头结点的链式队列出队操作示例ElementType DeleteQ(Queue PtrQ) { struct Node *FrontCell; ElementType FrontElem; if(PtrQ-front NULL) { printf(队列空); return ERROR; } FrontCell PtrQ-front; if(PtrQ-front PtrQ-rear) //若队列只有一个元素 { PtrQ-front PtrQ-rear NULL; //删除后队列置位空 } else { PtrQ-front PtrQ-front-Next; } FrontElem FrontCell-Data; free(FrontCell-Data); //释放被删除的结点空间 return FrontElem; }六、总结数据队列的概念理解起来并不是很难重要的时理解了基本概念之后一定要去运用只有实际应用了才能真正的懂。队列的应用无非是初始化、数据插入、数据删除这几步操作应用其实倒是蛮简单的。