数据结构之队列

一、队列

队列的定义：只允许在一端进行插入操作，而在另一端进行删除操作。

与栈相反：队列是一种先进先出的线性表。例如输入缓冲区接受键盘的输入就是按队列来进行，按上表的顺序，用栈来存储，出栈顺序为，ABCDE。按照队列的顺序，EDCBA。
队列一般用链表来实现，简称链队列。

1.队列的定义：

队列结合了链表，整合出一个带有头尾指针的结构体，front指针用来出队，rear指针用来入队，从而完整的定义了队列的功能。

typedef struct QNode
{
ElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,rear; //队头队尾指针
}LinkQueue ;

2.创建一个队列：

内存中创建一个头结点、将队列的头指针和尾指针都指向这个节点。

void initQueue(LinkQueue *q)
{
q->front = q->rear = (QueuePtr)malloc(sizeof(QNode));
if (!q->front)
exit(0);
q->front->next = NULL;
}

初始化队列其实初始化的是其头尾节点，给头尾节点分配出空间，然后将头尾节点的next节点置为NULL。

3.入队列操作

熟悉前面链表的知识看起来特别简单，在队尾追加一个节点，这里要注意一下：队头指针front其实是在链表第一个元素之前。

void InsertQueue(LinkQueue *q,ElemType e)
{
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if ( p == NULL)
exit(0);
p->data = e;
p->next = NULL;
q->rear->next = p;
q->rear = p;
}

4.出队列操作

出队列操作，先检查队列是否已经空了，即头尾指针是否相等，然后出队列一个元素，这个元素其实是front指针的下一个指向的元素。

void DeleteQueue(LinkQueue *q,ElemType *e)
{
QueuePtr p;
if (q->front == q->rear)
return;
p = q->front->next;
*e = p->data;
q->front->next = p->next;
if( q->rear == p)
q -> rear = q->front;
free(p);
}

5.销毁队列

遍历free。

void DestroyQueue(LinkQueue *q)
{
while (q->front)
{
q->rear = q->front->next;
free(q->front);
q->front = q->rear;
}
}

二、队列的应用：无聊的约瑟夫

问题是这样的：n个人(n<=100)围成一圈,从第一个人开始报数,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出圈,……依次类推,直到所有的人都出圈,请输出依次出圈人的编号。

很容易联想到队列的知识，不过这里用到的是循环队列，也很好理解，只需要将队列的头尾接起来。

三、总结

栈与队列总结：
栈：
栈是一端受限，一段允许进行操作的线性表。我自己理解时，会将它理解成一个装书的盒子。放书，取书，就是进行的操作。这个的特点就是，你放了一沓书，现在你想取书，你只能先把上面的书一个个取出来，即：先放的后取，后放的先取。放在栈上说，就是先进后出。
明白了栈的定义，现在要实际的实际，首先是它的逻辑结构：线性表。它是线性的。
现在是它的存储结构：最常采用的是顺序存储和链式存储（见好多书或资料都说的最常采用的是顺序存储和链式存储，百度了下不常见的没有找到）。其中顺序存储用数组，链式存储用链表。
顺序存储：
先进行分析下：首先要分配一个足够大的数组（这里就出现了一个问题，要是分配的空间小，就会出现溢出的情况，这是一个潜在的隐患，但是要是分配的太过大，又会出现浪费空间，这里要做好一个估计，所以呢，我还是喜欢链式存储，要多少就给多少，不用担心空间太小或浪费），现在有了这个数组，需要的还有，必须有个东西能一个控制一端不让操作(数组的前端从下标为0开始)，一端要进行增删，这样就可以说是具备了栈有的特点，不让操作的叫栈底，进行操作的是栈顶
链式存储：
控制入栈出栈的端口，栈顶一般是链表的头，第一个节点，栈底一般是最后一个节点。（可以避免顺序存储的溢出），同时节省空间，要多少，申请多少。链表的运用中同时要注意一旦申请了，最后要记得释放，不然会带来不可预计的后果。
队列：是一种限定性的线性表。这样理解比较好，学生排队买饭。有什么特点呢？当然，你先来，就先打饭，先吃饭。抽象到队列上说，有队头，队尾，要想加入（入队），只能从队尾加，想走（出队），只能从队头走。即：先进先出。
和栈一样，它常见的两种存储是顺序存储和链式存储。
用顺序存储时，会遇到这样的情况，数组并没有满，却入不了队（假溢出），原因在于队头没有在数组的0下标处。一般情况下，因为队列会存在假溢出的情况，所以采用循环队列。

最后

以上就是谨慎飞机为你收集整理的数据结构之队列的全部内容，希望文章能够帮你解决数据结构之队列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。