本文目录
- 栈和队列数据结构的特点,什么情况下用到栈,什么情况下用到队列(各举3个例子)
- 队列的应用实例
- 数据结构—队列
- 数据结构 第7讲 循环队列
- 数据结构之-队列
- 数据结构与算法-队列
- 用C++版数据结构写出一个顺序队列要求：键盘输入10个入队，例如输入0123456789输出9876543210求大神帮忙
- 「漫步计算机系统」之数据结构与算法（10）：堆和队列
- 数据结构篇|队列
栈和队列数据结构的特点,什么情况下用到栈,什么情况下用到队列(各举3个例子)
栈：特点就是一个先进后出的结构。队列：特点就是一个先进先出的结构。//一般只要你满足这个特点就可以称之为栈或队列。栈的应用：非常广泛，在CPU内部就有提供栈这个机制。主要用途：函数调用和返回，数字转字符，表达式求值，走迷宫等等。在CPU内部栈主要是用来进行子程序调用和返回，中断时数据保存和返回。在编程语言中：主要用来进行函数的调用和返回。可以说在计算机中，只要数据的保存满足先进后出的原理，都优先考虑使用栈，所以栈是计算机中不可缺的机制。队列的应用：队列主要用在和时间有关的地方，特别是操作系统中，队列是实现多任务的重要机制。windows中的消息机制就是通过队列来实现的。进程调度也是使用队列来实现，所以队列也是一个重要的机制。只要满足数据的先进先出原理就可以使用队列。
队列的应用实例
队列的应用 舞伴问题
问题叙述 假设在周末舞会上 男士们和女士们进入舞厅时 各自排成一队 跳舞开始时 依次从男队和女队的队头上各出一人配成舞伴 若两队初始人数不相同 则较长的那一队中未配对者等待下一轮舞曲 现要求写一算法模拟上述舞伴配对问题
问题分析 先入队的男士或女士亦先出队配成舞伴 因此该问题具体有典型的先进先出特性 可用队列作为算法的数据结构 在算法中 假设男士和女士的记录存放在一个数组中作为输入 然后依次扫描该数组的各元素 并根据性别来决定是进入男队还是女队 当这两个队列构造完成之后 依次将两队当前的队头元素出队来配成舞伴 直至某队列变空为止 此时 若某队仍有等待配对者 算法输出此队列中等待者的人数及排在队头的等待者的名字 他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人
具体算法及相关的类型定义 typedef struct{ char name; if(p sex== F ) EnQueue(&Fdancers p); //排入女队 else EnQueue(&Mdancers p); //排入男队 } printf( The dancing partners are: \n \n ); while(!QueueEmpty(&Fdancers)&&!QueueEmpty(&Mdancers)){ //依次输入男女舞伴名 p=DeQueue(&Fdancers); //女士出队 printf( %s p name);//打印出队女士名 p=DeQueue(&Mdancers); //男士出队 printf( %s\n p name); //打印出队男士名 } if(!QueueEmpty(&Fdancers)){ //输出女士剩余人数及队头女士的名字 printf( \n There are %d women waitin for the next round \n Fdancers count); p=QueueFront(&Fdancers); //取队头 printf( %s will be the first to get a partner \n p name); }else if(!QueueEmpty(&Mdancers)){//输出男队剩余人数及队头者名字 printf( \n There are%d men waiting for the next round \n Mdacers count); p=QueueFront(&Mdancers); printf( %s will be the first to get a partner \n p name); } }//DancerPartners
lishixinzhi/Article/program/sjjg/201311/22670
数据结构—队列
队列 (queue)是一种先进先出的线性表。它只允许在表的一端进行插入，在另一端进行删除，这如同我们日常生活中的排列是一致的，最早入队的元素最早离开。 队尾 (rear)是队列中允许插入的一端， 队头 (front)是队列中允许删除的一端。队列如同栈一样，也同样有两种存储表示，分别是顺序表示和链式表示。 和顺序栈类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到对列尾的元素之外，需要设置两个指针front和rear分别指示队列头元素和尾元素的位置。 队列的顺序存储结构表示如下： 为方便C语言描述起见，约定：初始化建空队列时，front=rear=0,每当插入新元素至队尾时，“尾指针增一”，每当删除头元素时，“头指针增一”。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队尾元素的下一个位置。 循环对列 是将顺序队列变成一个环状的空间，用这种方法可以解决队列“假溢出”问题。 “假溢出” 是指队列实际可用空间没有占满，但是不能向队列中添加新的队尾元素，否则会出现溢出的现象的情况。 在循环队列中，头尾指针以及队列元素之间的关系不发生改变，只是在循环队列中头尾指针“依次循环增一”的操作可用模运算实现。通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式“循环”移动。 循环队列的基本操作算法描述：链队是指采用链式存储结构实现的队列。通常链队用单链表来表示，一个链队显然需要两个分别指示对头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。为了操作方便，同线性表的单链表一样，为链队添加头结点，并规定头指针始终指向头结点。 链队列存储结构表示如下： 链队操作即为单链表插入和删除操作的特殊情况，只是需要进一步修改尾指针或头指针。 链队列的基本操作算法描述：
数据结构 第7讲 循环队列
数据结构 第7讲 循环队列 过了一段时间，小张再也受不了这种"起早贪黑"的有车生活。为了解决胡同停车问题，小张跑了无数次居委会，终于将挡在胡同口的建筑清除，这样住在胡同尽头的小张，就可以早早回家停在家门口，每天第一个开车上班去了。 现在胡同打通了，但仍然很窄，只能通过一辆车，但是可以从一端进，另一端出，画图：小汽车是线性排列，而且只能从一端进，另一端出，这就是"队列"，队列也是一种线性表，只不过它是操作受限的线性表，只能在两端操作，先进先出（First In First Out，FIFO）。进的一端称为队尾（rear），出的一端称为队头（front）。队列可以用顺序存储，也可以用链式存储。 1. 顺序队列 队列的顺序存储形式，可以用一个一维数组存储数据元素，用两个整型变量记录队头和队尾元素的下标。 顺序存储方式：顺序队列的结构体定义： 2. 完美图解 接下来看看顺序队列的入队和出队情况： 假设现在顺序队列Q分配了6个空间，然后进行入队出队操作，过程如图所示： (1)开始时为空队，Q.front=Q.rear，如图所示：(2)元素 a 1进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位，如图所示：(3)元素 a 2进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位，如图所示：(4)元素 a 3， a 4， a 5分别按顺序进队，尾指针Q.rear依次后移，如图所示：(5)元素 a 1出队，头指针Q.front（整型下标）后移一位，如图所示：(6) 元素 a 2出队，头指针Q.front（整型下标）后移一位，如图所示：(7)元素 a 6进队，放入尾指针rear（整型下标）的位置，rear后移一位，如图所示：(8) 元素 a 7进队，此时尾指针Q.rear已经超过了数组的下标，无法再存储进队，但是我们发现前面明明有2个空间，却出现了队满的情况，这种情况称为"假溢出"。 那么如何解决该问题呢？ 能否利用前面的空间继续存储入队呢？ 试试看…～ 上面第（7）步元素 a 6进队之后，尾指针Q.rear要后移一个位置，此时已经超过了数组的下标，即Q.rear+1=Maxsize（最大空间数6），那么如果前面有空闲，Q.rear可以转向前面0的位置，如图所示：然后元素 a 7进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位，如图所示：元素 a 8进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位，如图所示：这时候虽然队列空间存满了，但是出现了一个大问题，队满时Q.front=Q.rear，这和队空的条件一模一样，无法区分队空还是队满，如何解决呢？有两种办法：一是设置一个标志，标记队空和队满；另一种办法是浪费一个空间，当尾指针Q.rear的下一个位置Q.front是时，就认为是队满。如图所示：3. 循环队列 上述到达尾部又向前存储的队列称为循环队列，为了避免"假溢出"，我们通常采用 循环队列。 循环队列无论入队还是出队，队尾、队头加1后都要取模运算，例如入队后队尾后移一位：Q.rear =(Q.rear+1)%Maxsize。 为什么要%Maxsize呢？ 主要是为了处理临界状态，即Q.rear向后移动一个位置Q.rear+1后，很有可能超出了数组的下标，这时它的下一个位置其实是0，如果将一维数组画成环形图，如图所示：上图中最大空间Maxsize，当Q.rear=Maxsize-1时，(Q.rear+1)%Maxsize=0，而且Q.front=0，正好满足队满的条件：(Q.rear+1) %Maxsize= Q.front，此时为队满。 因此无论是front还是rear向后移动一个位置时，都要加1与最大空间Maxsize取模运算，处理临界问题。 总结： 队空 ：Q.front=Q.rear; // Q.rear和Q.front指向同一个位置 队满 ： (Q.rear+1) %Maxsize=Q.front; // Q.rear向后移一位正好是Q.front 入队 ： Q.base=x; //将元素放入Q.rear所指空间， Q.rear =( Q.rear+1) %Maxsize; // Q.rear向后移一位 出队 ： e= Q.base; //用变量记录Q.front所指元素， Q.front=(Q.front+1) %Maxsize // Q. front向后移一位 循环队列中到底存了多少个元素呢？ 因为队列是循环的，所以存在两种情况： （1）Q.rear》= Q.front，如下图所示：这种情况队列中元素个数为：Q.rear-Q.front=4-1=3。 （2）Q.rear《 Q.front，如下图所示：此时，Q.rear=4，Q.front=Maxsize-2，Q.rear-Q.front=6-Maxsize。但是我们可以看到循环队列中的元素实际上为6个，那怎么办呢？当两者之差为负数时，可以将差值+Maxsize计算元素个数，即：Q.rear-Q.front+Maxsize=6-Maxsize+Maxsize =6，元素个数为6。 那么在计算元素个数时，可以分两种情况判断： Q.rear》= Q.front：元素个数为Q.rear-Q.front； Q.rear《Q.front：元素个数为Q.rear-Q.front+ Maxsize； 也可以采用取模的方法把两种情况统一为一个语句： 队列中元素个数 ：(Q.rear-Q.front+Maxsize)% Maxsize 当Q.rear-Q.front为负数时，加上Maxsize再取余正好是元素个数，如(-2+6)%6=4；当Q.rear-Q.front为正数时，加上Maxsize超过了最大空间数，取余后正好是元素个数，如(3+6)%6=3。4. 队列的基本操作 队列的基本操作包括初始化、入队、出队、取队头元素、求队列长度。 (1)初始化 bool InitQueue(SqQueue &Q)//注意使用引用参数，否则出了函数，其改变无效 { Q.base=new int;//分配空间 if(!Q.base) return false; Q.front=Q.rear=0;//头指针和尾指针置为零，队列为空 return true; } (2)入队 bool EnQueue(SqQueue &Q,int e)//将元素e放入Q的队尾 { if((Q.rear+1)%Maxsize==Q.front) //尾指针后移一位等于头指针，表明队满 return false; Q.base =e;//新元素插入队尾 Q.rear=(Q.rear+1)%Maxsize;//队尾指针后移一位 return true; } (3)出队 bool DeQueue(SqQueue &Q, int &e) //删除Q的队头元素，用e返回其值 { if (Q.front==Q.rear) return false; //队空 e=Q.base;//保存队头元素 Q.front=(Q.front+1)%Maxsize;//队头指针后移一位 return true; } (4)取队头元素 int GetHead(SqQueue Q)//返回Q的队头元素，不修改队头指针 { if (Q.front!=Q.rear) //队列非空 return Q.base; return -1; } (5)循环队列的长度 int QueueLength(SqQueue Q) { return (Q.rear-Q.front+Maxsize)%Maxsize; }
数据结构之-队列
队列 一种特殊的 线性表 ，也是常见的一种数据类型。特殊之处在于它只能在表的前端(front)进行删除，而在表的后端(rear)进行插入操作。进行插入操作的端称为 队尾 ，进行删除操作的端称为 队头 。
队列 又称为先进先出（FIFO—first in first out）线性表。
线性表 分为 顺序存储 和 链式存储 ，栈是线性表，所以也有这两种存储方式。同样，队列作为一种特殊的线性表，也同样存在这两种存储方式。
顾名思义，顺序存储采用数组的方式，而链式存储采用链表的方式。
顺序存储的队列 又分为 顺序队列 和 循环队列 。
首选说一下顺序队列的坏话，顺序队列在 入队列 的时候可以保持O(1)的时间复杂度，而在 出队列 的时候队头后边的元素需要依次往前移动，以保证队头不为空,时间复杂度就变成了O(n);
为什么出队列时一定要全部移动呢，那么我们是否可以解决 出队列 所带来的问题呢，当然可以。
如果不去限制队列的元素必须存储在数组的前n个单元这一条件，出队的性能就会大大增加。这也就意味着队头不一定位于index=0的位置了。
假设是长度为5的数组，初始状态，空队列如所示，front与 rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4, front指针依然指向下标为0位置，而rear指针指向下标为4的位置。
出队a1、a2，则front指针指向下标为2的位置，rear不变，如下图所示，再入队a5，此时front指针不变，rear指针移动到数组之外。嗯？数组之外，那将是哪里？
如上图所示，添加a5元素之后，rear已经无家可归了，于此同时0和1位置的空间却被拜拜浪费了，这个中情况被称之为 假溢出 。
为了解决 假溢出 的情况也就引出了我们接下来要讲的 循环队列 。
接着上图的来讲，为了把无家可归的rear有个好的落脚点，我们就把它放置在index=0的位置。
但是如果继续进行入队操作的话，比如继续插入a6、a7，则rear指针就与front指针重合，同时指向下标为2的位置。
此时问题又出来了，我们刚才说，空队列时，等于rear，现在当队列满时，也是from等于rear，那么如何判断此时的队列究竟是空还是满呢？
办法一 是设置一个标志变量flag，当front == rear,且flag = 0时为队列空，当front == rear,且flag= 1时为队列满。
办法二 是当队列空时，条件就是from = rear,当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。 如下图所示，我们就认为此队列已经满了，也就是说，我们不允许上图情况出现。
在第二种情况下，由于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，因此通用的计算队列长度公式为：
(rear—front + QueueSize) % QueueSize
从上面的图我们不难看出顺序存储存在着数组可能会溢出的问题，所以也就引出了链式存储结构。
在链队列中，队头指针指向头结点，队尾指针指向终端结点，一个普通的链队列如下图所示：
当队列为空时，front和rear都指向头结点。
数据结构与算法-队列
同样是线性表，队列也有类似线性表的各种操作，不同的就是插入数据只能在队尾进行，删除数据只能在队头进行。 线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储方式。同样，队列作为一种特殊的线性表，也同样存在这两种存储方式。 我们假设一个队列有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)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。 总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。 栈和队列也都可以通过链式存储结构来实现，实现原则上与线性表基本相同如图所示。
用C++版数据结构写出一个顺序队列要求：键盘输入10个入队，例如输入0123456789输出9876543210求大神帮忙
队列的头文件如下：#ifndef QUEUE_H#define QUEUE_H#include 《iostream》using std::cout;using std::endl;using std::ostream;template 《class Type》class Queue {friend ostream & operator《《 (ostream &, const Queue《Type》 &);public:static const int DefaultSize;Queue(int = DefaultSize);//创建一个最大容量为MaxQueueSize的空队列Queue(Type , int, int = DefaultSize);~Queue() {delete queue;}bool IsFull();//若元素个数等于队列的最大容量则返回true，否则返回falsevoid Add(const Type &);//若IsFull()为true，调用外处理函数QueueFull()，否则将item插入队尾bool IsEmpty() const;//若队列中元素个数等于0，则返回true，否则返回falseType * Delete(Type &);//若IsEmpty()为true，调用QueueEmpty()并返回0，否则删除队列前段元素并返回其指针void Empty();//清空队列void QueueFull();//扩充1倍的存储空间void QueueEmpty();//提示队列已空，元素不能出队private:int front, rear;Type * queue;int maxSize;};template 《class Type》const int Queue《Type》::DefaultSize = 10;template 《class Type》Queue《Type》::Queue(int pMaxSize) {queue = new Type ;maxSize = pMaxSize;front = rear = -1;}template 《class Type》Queue《Type》::Queue(Type pArray, int pSize, int pMaxSize) {queue = new Type ;for (int i = 0; i 《 pSize; i++) {queue;}front = -1; rear = pSize - 1;maxSize = pMaxSize;}template 《class Type》bool Queue《Type》::IsFull() {if ( rear == maxSize - 1 ) return true;else return false;}template 《class Type》bool Queue《Type》::IsEmpty() const {if ( rear == front ) return true;else return false;}template 《class Type》void Queue《Type》::Add(const Type & pX) {if (IsFull()) {QueueFull();queue = pX;}else{queue = pX;}}template 《class Type》Type * Queue《Type》::Delete(Type & pX) {if (IsEmpty()){QueueEmpty();return 0;}else{pX = queue;return &pX}}template 《class Type》void Queue《Type》::QueueEmpty() {cout 《《 "队列为空，不能进行出队操作！" 《《 endl;}template 《class Type》void Queue《Type》::QueueFull() {Type * newQueue = new Type ;for ( int i = front + 1; i 《= rear; i++ ){newQueue;}maxSize = maxSize * 2;delete queue;queue = newQueue;cout 《《 "队列已满，现已增加空间为原来的2倍 " 《《 maxSize;}template 《class Type》void Queue《Type》::Empty() {front = rear = -1;}template 《class Type》ostream & operator《《 (ostream & pOutput, const Queue《Type》 & pQ) {if (pQ.IsEmpty()) {cout 《《 "空队列" 《《 endl;return pOutput;}for ( int i = pQ.front + 1; i 《= pQ.rear; i++ ) {pOutput 《《 pQ.queue 《《 " ";}cout 《《 endl;return pOutput;}#endif
「漫步计算机系统」之数据结构与算法（10）：堆和队列
问题一： 给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
代码如下：
public ArrayList GetLeastNumbers_Solution(int nums, int k) {
if (k 》 nums.length || k 《= 0)
return new ArrayList》();
PriorityQueue maxHeap = new PriorityQueue》((o1, o2) -》 o2 - o1);
for (int num : nums) {
maxHeap.add(num);
if (maxHeap.size() 》 k)
maxHeap.poll();
}
return new ArrayList》(maxHeap);
}
算法描述：
问题二： 得到一个数据流中的中位数
代码如下：
/* 大顶堆，存储左半边元素 */
private PriorityQueue left = new PriorityQueue》((o1, o2) -》 o2 - o1);
/* 小顶堆，存储右半边元素，并且右半边元素都大于左半边 */
private PriorityQueue right = new PriorityQueue》();
/* 当前数据流读入的元素个数 */
private int N = 0;
public void Insert(Integer val) {
/* 插入要保证两个堆存于平衡状态 */
if (N % 2 == 0) {
/* N 为偶数的情况下插入到右半边。
* 因为右半边元素都要大于左半边，但是新插入的元素不一定比左半边元素来的大，
* 因此需要先将元素插入左半边，然后利用左半边为大顶堆的特点，取出堆顶元素即为最大元素，此时插入右半边 */
left.add(val);
right.add(left.poll());
} else {
right.add(val);
left.add(right.poll());
}
N++;
}
public Double GetMedian() {
if (N % 2 == 0)
return (left.peek() + right.peek()) / 2.0;
else
return (double) right.peek();
}
算法描述：
问题三：字符流中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 "go" 时，第一个只出现一次的字符是 "g"。当从该字符流中读出前六个字符“google" 时，第一个只出现一次的字符是 "l"。
代码如下：
private int;
private Queue queue = new LinkedList》();
public void Insert(char ch) {
cnts++;
queue.add(ch);
while (!queue.isEmpty() && cnts 》 1)
queue.poll();
}
public char FirstAppearingOnce() {
return queue.isEmpty() ? ’#’ : queue.peek();
}
算法描述：
问题四：滑动窗口的最大值
例如，如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，他们的最大值分别为 {4, 4, 6, 6, 6, 5}。
代码如下：
public ArrayList maxInWindows(int num, int size) {
ArrayList ret = new ArrayList》();
if (size 》 num.length || size 《 1)
return ret;
PriorityQueue heap = new PriorityQueue》((o1, o2) -》 o2 - o1); /* 大顶堆 */
for (int i = 0; i 《 size; i++)
heap.add(num);
ret.add(heap.peek());
for (int i = 0, j = i + size; j 《 num.length; i++, j++) { /* 维护一个大小为 size 的大顶堆 */
heap.remove(num);
heap.add(num);
ret.add(heap.peek());
}
return ret;
}
算法描述：
数据结构篇|队列
实现这个队列在这里我选择复用之前实现的数组的一些方法，链接如下：
将实现的Array类拷贝过来之后，然后我们再创建一个接口，这个接口的方法如上所示， getSize() 方法是获取队列中元素的个数， isEmpty() 是判断队列中是否为空， enqueue() 方法是向队列中添加一个E类型的元素e， dequque() 方法是让队列中队首的元素进行出队， getFront() 是查看队首的元素。
创建完接口之后再创建一个实现类ArrayQueue，因为需要复用引入进来的Array类，所以先声明一个Array类型的参数array，然后进行构造方法的编写。第一个构造方法是有参的，适用于用户已知需要多大容量的情况下，参数为整形的 capacity ，意思是可以传入队列的容量，所以在方法中就直接实例化Array类并将capacity传入进去。再编写一个无参的构造方法，这个方法适用于不知道容量的情况，所以再方法中直接实例化Array类。
getSize()方法是为了获取队列中元素的个数，所以直接调用array类的getSize()方法即可。isEmpty()方法是为了判断队列中是否为空，所以也就是直接调用Array类中的方法即可。
getCapacity()方法是为了获取队列中的容量，那么是同样的调用Array类的getCapacity方法即可。
第一个方法是入队方法，因为队列的特性是先入先出的，所以添加元素要向队列的对位添加，所以调用Array类的addLast()方法即可，同样的dequeue()方法是需要从队首删除一个元素的，所以调用Array类的removeFirst()方法即可。第三个方法是获取队首的元素并进行返回，因为这个队列是基于数组进行实现的，所以直接适用get()方法，参数传入0即可。
这个方法主要用于进行函数的测试。
注意：实现的队列的方法中出队操作是比较耗时的，虽然在元素个数较少的时候这种时间的消耗可以忽略不计，但是在元素非常多的情况下对效率的影响是很大的，所以接下来我们要对队列进行改进。这就是下面要介绍的循环队列。
创建一个类LoopQueue实现Queue接口，其中包含三个属性，首先是创建了一个E类型的数组data，然后是设置了队首和队尾，第三个是统计队列元素个数的size属性。定义完属性之后再来编写循环队列的构造方法，首先第一个是一个有参的构造方法，参数是整形的capacity，也就是容量。 在方法中首先是将数组data进行初始化，这里可能有人会想，为什么要把容量加1呢？原因是因为循环队列需要有意的浪费一个空间，所以需要将数组的容量设置为用户传入的容量+1，然后将fornt、tail和size都初始化为0。接着是无参构造方法，这里就直接复用有参构造方法将容量设置为10。
getCapacity()方法是为了获取队列的容量，因为在初始化数组时容量设置的比用户传入的容量多1个，所以在这里应该将数组的长度-1，这样便可以计算出队列可用的容量。isEmpty()方法可以通过第五点循环队列的设想看出当数组为空时，front和tail是相等的。getSize()方法就很简单啦，直接返回size即可。
resize()方法用于进行数组的扩容操作，在这里需要传入扩容需要的容量。在方法中首先需要创建一个E类型的数组newData，并将容量传入，具体为什么需要将容量+1，还是因为循环队列需要对1个空间进行浪费。然后对原数组也就是data进行循环，将newData的第1个元素也就是0的位置，赋值为data的front。这里为什么要这么写，也是因为队列是循环的。循环结束后只需要将data指向newData，front赋值为0，tail与元素个数一致即可。
enqueue方法是向队列中添加元素，首先需要判断数组是否为满，因为队列是循环的，所以需要使用 (tail + 1) % data.length == front 计算数组的容量情况，当数组为满时需要进行扩容，这里我就将新的数组扩容为原来的2倍了。然后将e添加到数组中的最后一个位置，然后对tail和size进行维护。
在进行出队方法编写时首先需要判断当前数组是否为空，如果为空就抛出异常。因为需要将出队的元素进行返回，所以先将队首的元素进行保存。然后将队首的元素置为null。然后对front和size进行维护。因为是出队操作，所以可能需要进行缩容的操作，在这里先进行判断如果条件满足的话就将容量缩小至原来的二分之一。最后将保存的结果返回。
getFront()方法非常简单，首先将数组进行判断，如果为空抛出异常。不为空就将数组中的front位置的元素进行返回。
最后为了方便测试，我们将toString方法进行重写，在这里特别要注意的一点就是循环的时候，需要从front位置开始，到tail位置结束，可是因为是循环队列的缘故tail很有可能小于front。那么就使用 i != tail 进行判断，然后对i进行增加。然后将data进行append。最后将res进行返回即可。
