数据结构与算法-队列
线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储方式。同样，队列作为一种特殊的线性表，也同样存在这两种存储方式。
我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为 。
与栈不同的是，队列元素的出列是在队头，即下标为0的位置，那也就意味着，队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为 。
可有时想想，为什么出队列时一定要全部移动呢，如果不去限制队列的元素必须存储在数组的前n个单元这一条件，出队的性能就会大大增加。也就是说，队头不需要一定在下标为0的位置，
为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列。
假设是长度为5的数组，初始状态，空队列列如图所示，front与rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4，front指针依然指向下标为0位置，而rear指针指向下标为4的位置。
出队a1、a2，则front指针指向下标为2的位置，rear不变，如图4-12-5的左图所示，再入队a5，此时front指针不变，rear指针移动到数组之外。嗯？数组之外，那将是哪里？如下图的右图所示。
假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做“假溢出”。
所以解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。
如果将rear的指针指向下标为0的位置，那么就不会出现指针指向不明的问题了，如下图所示。
接着入队a6，将它放置于下标为0处，rear指针指向下标为1处，如下图的左图所示。若再入队a7，则rear指针就与front指针重合，同时指向下标为2的位置，如下图的右图所示。
由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。
所以若队列的最大尺寸为QueueSize，那么队列满的条件是(rear+1)%QueueSize==front（取模“%”的目的就是为了整合rear与front大小为一圈问题）。比如上面这个例子，QueueSize=5，上图的左图中front=0，而rear=4，(4+1)%5=0，所以此时队列满。
再比如图下图中的，front=2而rear=1。(1+1)%5=2，所以此时队列也是满的。
而对于下图，front=2而rear=0，(0+1)%5=1，1≠2，所以此时队列并没有满。
另外，当rear>front时，此时队列的长度为rear-front。
但当rear<front时，，队列长度分为两段，一段是QueueSize-front，另一段是0+rear，加在一起，队列长度为rear-front+QueueSize。因此通用的计算队列满队公式为：
单是顺序存储，若不是循环队列，算法的时间性能是不高的，但循环队列又面临着数组可能会溢出的问题，所以我们还需要研究一下不需要担心队列长度的链式存储结构。
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。
空队列时，front和rear都指向头结点。
链队列的结构为：
初始化一个空队列
入队操作时，其实就是在链表尾部插入结点，如图所示。
出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点，如图所示。
对于循环队列与链队列的比较，可以从两方面来考虑，从时间上，其实它们的基本操作都是常数时间，即都为O(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。
总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。
栈和队列也都可以通过链式存储结构来实现，实现原则上与线性表基本相同如图所示。
数据结构与算法大学没学明白的来
答：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。 相关术语 在数据结构与算法中,数据、数据对象、数据元素、数据项有一些同学搞不懂其中的关系。通过画一张图来捋一捋: 数据三要素 数据结构三要素...
这学期学数据结构,写链队列算法,遍历函数的时候有个问题,哪位解答下...
答：实验结果：include<stdio.h>#include<stdlib.h> define OK 1 define ERROR 0 define OVERFLOW -2 typedef int Status;typedef int QElemType;typedef struct QNode { QElemType data;QNode *next;}*QueuePtr;struct LinkQueue { QueuePtr front;QueuePtr rear;};//新建一个空队列 void InitQueue(...
数据结构与算法是学什么的
答：数据结构与算法是北京大学于2018年02月26日首次在中国大学MOOC开设的慕课课程，是国家精品在线开放课程。数据结构与算法课程内容包括数据结构与抽象数据类型、算法特性及分类、算法效率与度量、线性结构、顺序表、链表、栈与队列、栈与递归、递归转非递归、字符串的存储结构、字符串运算的算法实现、字符串的...
线性数据结构小百科
答：你是否曾好奇过,电脑是如何快速又准确地存储和处理海量数据的?秘密就在于各种神秘的数据结构,其中线性数据结构是入门款!本文将为你详细介绍线性数据结构的特点和常见类型。关系明确线性数据结构中的数据元素之间有一对一或一对多的关系,就像你在队伍中只能有一个前面的人和多个后面的人。顺序排列线性数据结构中...
栈与队列的区别
答：3、遍历数据速度不同。栈只能从头部取数据，也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性。队列则不同，它基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影像数据结构...
数据结构有什么?
答：Clifford A.Shaffer在《数据结构与算法分析》一书中的定义是：“数据结构是ADT（抽象数据类型Abstract Data Type） 的物理实现。”Robert L.Kruse在《数据结构与程序设计》一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算...
数据结构(C语言编写完整可运行程序):设有队列Q、栈S,设计算法利用栈S将...
答：Queue Q;//建立循环队列Q init_q(&Q);Enqueue(&Q, 1);Enqueue(&Q, 2);Enqueue(&Q, 3);printf("逆置后对列中的元素是\n");OutQpushS(&Q, &S);//出对入栈 PopOut(&S, &Q);//出栈并入队 Out(&Q);//对Q出对 return 0;} void init_s(stack *pS){ pS->ptop = NULL;}...
数据结构C语言版 银行业务队列模拟 必须使用栈和队列相关算法 网上的会...
答：include<stdio.h> include<stdlib.h> include define MAX 1000 define error -1 typedef struct node{ int customer[MAX];int rear;int front;}queue;void add(queue *q,int item){ if((q->rear+1)%MAX==q->front){ printf("队列满\n");return;} q->rear=(q->rear+1)%MAX;q->...
计算机专业的考研考什么科目呢?
答：计算机专业考试内容 一、数据结构与算法 线性表、栈和队列、串、数组和广义表、树和二叉树、图、动态存储管理、查找、内部排序、外部排序、文件。二、计算机组成原理 基本概念（计算机组成、性能指标、工作过程等），数据的机器层次表示，指令系统、数值的机器运算、存储系统和结构、中央处理器、总线系统、...
计算机专业的学生如何提高就业能力
答：2、数据结构与算法:链表,队列,堆,二叉树,排序,查找,贪心,回溯等。推荐配合某个具体语言食用,感受数据结构与算法的美。 3、操作系统:进程与线程,乐观锁与悲观锁,缓存一致性,CPU时间片调度,工作中常常用到高并发以及高数据库读写的情况,熟悉操作系统才能开发出更好的方案。 4、计算机网络:工作中会开发各种接口以...
