在栈中，我们将指向栈顶的标志称为栈顶指针，在队列中同理： 指向队尾的标志称为队尾指针（rear）； 指向队头的标志称为队头指针（front）； 这两个指针的主要做用就是告诉我们元素从哪里入队，从哪里出队...，我们可以通过静态数组来实现一块连续的存储空间； 既然是静态数组，那么我们要想找到数组中不同位置的元素那就需要数组下标，因此队头指针与队尾指针就需要是两个存放数组下标的整型变量，因此我们可以将其用C语言表述为...这里我们先放一放，后面再来讨论； 在定义好数据类型后，我们只需要通过类型来定义一个变量并即将该变量进行初始化，即可完成队列的创建。定义变量都很简单，关键是这个初识我们应该如何表示？...我们来看一下下面的图片： 从上图中我们可以看到按照前面的分析，在创建数据类型时只定义静态数组与两个指针并将指针初始化为0的情况下，我们要实现一个队列，那我们的入队操作与出队操作都应该选择先执行入队或者出队...也就是说我们前面的分析只适合与创建好队列后从初始化开始到销毁结束，中间的流程都不能发生任何变化，即入队就要全部元素入满，出队就要直接到销毁。
遇到开括号时将其推入栈中，遇到闭括号时尝试从栈中弹出一个开括号并检查是否匹配。 页面访问：在Web浏览器中，栈常用来实现前进和后退功能。当用户访问新页面时，前一个页面会被推入栈中。...递归过程的每一步都在栈上有自己的存储空间，直到达到基本情况。 数制转换：在进行数制转换时，如十进制转八进制或其他进制，可以利用栈来临时存储转换过程中产生的余数，最后从栈顶开始依次输出即得到转换结果。...常见的方法及功能： 方法 功能 boolean offer(E e) 入队列 E poll() 出队列 peek() 获取队头元素 int size() 获取队列中有效元素的个数 boolean isEmpty...):index=(index+array.length-offset)%array.length 如何区分空与满 通过添加size属性记录 保留一个位置 使用标记 3.4双端队列 双端队列是指允许两端都可以进行入队和出队操作的队列...，那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
但是对于链表就不是了，链表也没有下标的概念，只能通过头节点指针，从每一个节点，依次往下找，因为下个节点的位置信息只能通过上个节点知晓(这里只考虑单向链表)，所以访链表中的List(3)与List(10000...–静态链表– 使用静态链表存储数据，需要预先申请足够大的一整块内存空间，也就是说，静态链表存储数据元素的个数从其创建的那一刻就已经确定，后期无法更改。 ...报数而不被杀的人：相当于从队首出队再从队尾入队； 被杀的人：只出队； 留到最后的人：当队列长度为1时，再出队一次，返回。...当数据项加入队列，首先出现在队尾，随着队首数据项的移除，它逐渐接近队首。 队列特征 (1)先进先出或先到先服务； (2)队列只有一个入口和一个出口。 ...图中的每个顶点，都是字典中的键，该键对应的值为“该顶点所指向的图中其他的顶点”。
本文介绍队列的基本概念和实现。 队列常见操作 队列最常见的操作是入队和出队，拿排队买东西来说，入队就是新来一个人排在队伍后面，而出队就是一个人已经结账离开。...队列基本实现考虑 与实现栈不同，它需要两个指针，一个指向队头（front），一个指向队尾（rear），这样才能方便地进行入队或出队操作，因此队列的实现要比栈难一些。...并且队列中的数据如下： 0 1 2 3 4 10 11 12 13 14 front rear 这个时候从队头front处删除一个数据，是很容易的。...这里就说明了队列实现需要考虑的两个问题： 如何高效地将元素入队 如何判断队列为空或队列为满 当然了，如果你使用链表实现队列，那么入队也完全不需要搬移数据。...2时，表明队列满 入队，入队前检查队列是否已满，如未满，队尾加1取模，并赋值 出队，出队前检查队列是否为空，如不空，则取值，并加1取模 代码 完整可运行代码实现如下： //arrayQueue.c #include
点击链接直达【拜托，面试别再问我堆（排序）了！】...为0，相当于解锁； （6）其它线程在扩容的过程中要让出CPU； （7）再次加锁； （8）新数组创建成功，把旧数组元素拷贝过来，并返回到offer()方法中继续添加元素操作； 出队 阻塞队列的出队方法也有四个...; }} 出队的过程与PriorityQueue基本类似： （1）加锁； （2）判断是否出队成功，未成功就阻塞在notEmpty条件上； （3）出队时弹出堆顶元素，并把堆尾元素拿到堆顶； （4）再做自上而下的堆化...； （5）解锁； 总结 （1）PriorityBlockingQueue整个入队出队的过程与PriorityQueue基本是保持一致的； （2）PriorityBlockingQueue使用一个锁+一个...notEmpty条件控制并发安全； （3）PriorityBlockingQueue扩容时使用一个单独变量的CAS操作来控制只有一个线程进行扩容； （4）入队使用自下而上的堆化； （5）出队使用自上而下的堆化
1 18 --count; 19 notFull.signal(); //唤醒入队条件的等待队列中的线程 20 return x; 21 } 从源码可以看出，出队的大致步骤如下...4）出队完成后，释放锁，唤醒同步队列的后继节点， offer(e)&poll() 返回特殊值 当不能满足入队或出队条件时，返回特殊值。...为了提高并发度和吞吐量，使用两把锁，takeLock只负责出队，putLock只负责入队，入队和出队可以同时进行，提高入队和出队操作的效率，增大队列的吞吐量。...而LinkedBlockingQueue的入队和出队操作使用的是不同的锁，会有对count变量并发修改的情况，所以使用原子变量保证线程安全。...例如：入队线程使用put方法在队列尾部插入一个元素，怎么保证出队线程能看到这个元素？ArrayBlockingQueue的入队和出队使用同一个锁，所以没有可见性问题。
对于队列这样一个数据结构来说，它有两个常见的动作： enqueue，我个人喜欢把它译作入队，指的是把元素放入队列这个动作。 dequeue，出队，指的是把元素从队列中移除这个动作。...明白了队列的基本操作后，我们来深入地思考一下，队列是如何工作的。 1） 建立顺序的队列结构需要为其静态分配或者动态申请一串连续的存储空间。...4）出队时 检查队列是否为空，需要一个 isEmpty() 的方法来判断； 用一个临时变量来保存队首的元素，以便出队后返回； 每次在队首删除一个元素时，FRONT 加 1； 如果是最后一个元素，重置 FRONT...可以把问题归咎于我们实现队列的方式上，也可以浅显地认为基本类型的队列存在有局限性。随着入队和出队的连续操作，队列中的元素在不停地变化，队列所占的存储空间也在分配的连续空间中不停的移动。...当队列第一次被填满了以后，出队了两个元素，此时下标为 0 和 1 的两个位置空了出来，然后入队元素 6，意味着 6 变成了队尾，也就是 REAR 等于 0 了；再入队元素 7，7 变成了队尾，也就是 REAR
允许插入的一段称作队尾 (rear)，允许删除的的一端称为队头 (front) 队列的数据元素又叫做队列元素，在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队 ，也正是因为队列只允许在一段插入...我们一步步分析一下： 我们先按照我们一般的想法画出队列元素进出队的过程，例如队列元素出队 ?...这样的设想，也就是根据我们前面食堂排队的例子画出来的，但是我们可以清晰的看到，当a0出队后，a0后的元素全部需要前移，将空位补上，但我们在计算机中讲究性能二字，如何可以提高出队的性能呢？...问题一 这个时候我们就需要考虑这样的问题了： ① 如何为了解决只有一个元素的时候，队头和队尾重合使得处理变得麻烦？...+ maxSize) % MaxSize 入队：rear = (rear + 1) % maxSize 出队：front = (front + 1) % maxSize (一) 顺序队列的类型定义
head永远指向该队列的队头元素，tail则指向该队列最后一个元素的下一位置，当有入队操作时： 当有出队操作时： 当遇到出队操作时，head会移向下一元素位置。...当然，对于这种方式入队和出队，队空的判断条件显然是head=tail，队满的判断条件是tail=array.length（数组最后一个位置的下一位置）。...但是如果你传入一个小于8的参数，那么会默认使用我们上述介绍的静态属性值作为的长度。至于为什么这么做，因为这么做会大大提高我们在入队时候的效率，我们等会儿会看到。 ...入队操作 由于实现了Deque，所以它是一个双向队列，支持从头部或者尾部添加节点，由于内部操作类似，我们只简单介绍从尾部添加入队操作。...其实，虽然我们这个它实现了双端队列，并且我们本篇主要把他当做队列来研究，其实该类完全可以作为栈或者一些其他结构来使用，所以提供了一些其他的方法循环队列出队，但本质上还是某几个方法。
使用阻塞算法的队列可以用一个锁（入队和出队用同一把锁）或两个锁（入队和出队用不同的锁）等方式来实现，而非阻塞的实现方式则可以使用循环CAS的方式来实现，本节我们就来研究下ConcurrentLinkedQueue...这个特性把入队 / 出队时，原本需要一起原子化执行的两个步骤分离开来，从而缩小了入队 / 出队时需要原子化更新值的范围到唯一变量。这是非阻塞算法得以实现的关键。...以批处理方式来更新head/tail，从整体上减少入队 / 出队操作的开销。 ?...上面的分析从单线程入队的角度来理解入队过程，但是多个线程同时进行入队情况就变得更加复杂，因为可能会出现其他线程插队的情况。...3.出队列 出队列的就是从队列里返回一个节点元素，并清空该节点对元素的引用。让我们通过每个节点出队的快照来观察下head节点的变化。 ?
概述 ConcurrentLinkedQueue是一种基于链表实现的无界非阻塞线程安全队列，遵循先入先出规则。 线程安全队列有两种实现方式： 阻塞方式：对入队和出队操作加锁。...从类图可以看出，ConcurrentLinkedQueue有head和tail两个volatile域，节点是用静态内部类Node表示，每个Node含有元素item和指向下一个节点的指针next，都是volatile...其实它是一种低级别的优化手段，就是在不需要让共享变量的修改立刻让其他线程可见的时候，以设置普通变量的方式来修改共享状态，可以减少不必要的内存屏障，从而提高程序执行的效率。 ...出队 和入队相似，出队时也不是每次都会更新head节点，当head节点的item不为null时，直接弹出item；否则会更新head节点。...并且如果在遍历的过程中，Queue有入队或出队的操作，会导致该方法统计的结果不准确。所以size()方法不太有用。那如何判断Queue是否为空呢？
正如上图一样，我们使用管程把共享变量和对应的入队enq和出队dep封装起来，线程A和线程B要进行队列的操作就要使用管程提供的enq和dep实现，enq和dep保持了互斥，同一时刻只有一个线程进入管程...., 而条件变量和条件变量等待队列就是实现同步的，这里我要注意一个问题，就是用管程实现阻塞队列和管程内的等待队列是不一样的东西，我们举个例子，一个线程1对管程实现的阻塞队列进行出队的操作,出队的前提条件就是阻塞队列不能为空...，而这个前提条件就是管程里面的条件变量，当从阻塞队列出队的时候，发现阻塞队列为空，怎么办呢，此时就会进入等待，而这个等待就是管程里面的条件变量等待队列,然后又有一个线程2要对管程实现的阻塞队列进行入队操作...，如果入队成功之后,此时阻塞队列不为空的条件，对于线程1就已经满足了，线程2就会通知线程1，线程1就会从条件变量等待队列出队，但是并不会直接执行,而是进入管程入口的等待队列， 使用管程写一个线程安全的队列...对于阻塞队列出队操作,如果阻塞队列为空，就需要等待阻塞对垒不为空，使用notEmpty.await 当入队成功，阻塞队列就不为空了，此时就要通知条件变量:notEmpry的等待队列 当出队成功，阻塞队列不满
队列这种数据结构，无论你是用链表实现，还是用数组实现，它都是要有两个指针分别指向队头和队尾。在我们数组的实现方式中，用两个int型变量用于记录队头和队尾的索引。 ?...当遇到出队操作时，head会移向下一元素位置。当然，对于这种方式入队和出队，队空的判断条件显然是head=tail，队满的判断条件是tail=array.length（数组最后一个位置的下一位置）。...但是如果你传入一个小于8的参数，那么会默认使用我们上述介绍的静态属性值作为elements的长度。至于为什么这么做，因为这么做会大大提高我们在入队时候的效率，我们等会儿会看到。...入队操作 由于ArrayDeque实现了Deque，所以它是一个双向队列，支持从头部或者尾部添加节点，由于内部操作类似，我们只简单介绍从尾部添加入队操作。...出队操作 出队操作和入队一样，具有着多个不同的方法，但是内部调用的还是一个pollFirst方法，我们主要看下该方法的具体实现即可： public E pollFirst() { int h
ConcurrentLinkedQueue使用的是CAS原语无锁队列实现，是一个异步队列，入队的速度很快，出队进行了加锁，性能稍慢。...LinkedBlockingQueue也是阻塞的队列，入队和出队都用了加锁，当队空的时候线程会暂时阻塞。...在请求预处理阶段，由于我们的系统入队需求要远大于出队需求，一般不会出现队空的情况，所以我们可以选择ConcurrentLinkedQueue来作为我们的请求队列实现 请求接口的合理设计 一个秒杀或者抢购页面...，通常分为2个部分，一个是静态的HTML等内容，另一个就是参与秒杀的Web后台请求接口。...当然，也有一些秒杀和抢购采用“滞后反馈”，就是说秒杀当下不知道结果，一段时间后才可以从页面中看到用户是否秒杀成功。但是，这种属于“偷懒”行为，同时给用户的体验也不好，容易被用户认为是“暗箱操作”。
ConcurrentLinkedQueue使用的是CAS原语无锁队列实现，是一个异步队列，入队的速度很快，出队进行了加锁，性能稍慢。...LinkedBlockingQueue也是阻塞的队列，入队和出队都用了加锁，当队空的时候线程会暂时阻塞。...在请求预处理阶段，由于我们的系统入队需求要远大于出队需求，一般不会出现队空的情况，所以我们可以选择ConcurrentLinkedQueue来作为我们的请求队列实现 1....请求接口的合理设计 一个秒杀或者抢购页面，通常分为2个部分，一个是静态的HTML等内容，另一个就是参与秒杀的Web后台请求接口。...当然，也有一些秒杀和抢购采用“滞后反馈”，就是说秒杀当下不知道结果，一段时间后才可以从页面中看到用户是否秒杀成功。但是，这种属于“偷懒”行为，同时给用户的体验也不好，容易被用户认为是“暗箱操作”。
如图ArrayBlockingQueue内部有个数组items用来存放队列元素，putindex下标标示入队元素下标，takeIndex是出队下标，count统计队列元素个数，从定义可知道并没有使用volatile...另外有个独占锁lock用来对出入队操作加锁，这导致同时只有一个线程可以访问入队出队，另外notEmpty，notFull条件变量用来进行出入队的同步。...0: i; } 这里由于在操作共享变量前加了锁，所以不存在内存不可见问题，加过锁后获取的共享变量都是从主内存获取的，而不是在CPU缓存或者寄存器里面的值，释放锁后修改的共享变量值会刷新会主内存中。...cast(items[i]); } 八、 size操作 获取队列元素个数，非常精确因为计算size时候加了独占锁，其他线程不能入队或者出队或者删除元素 publicintsize() {...其中offer,poll操作通过简单的加锁进行入队出队操作，而put,take则使用了条件变量实现如果队列满则等待，如果队列空则等待，然后分别在出队和入队操作中发送信号激活等待线程实现同步。
管程就是来解决这两个问题的。 互斥：同一时刻只允许一个线程访问共享资源。 同步：线程之间如何通信、协作。 管程互斥与同步实现 它的思路很简单，将共享变量以及对共享变量的操作统一封装起来。...如下图所示，管程 A 将共享变量 data 和相关的操作入队enq()、出队deq() 封装起来。线程 A 和线程 B想访问共享变量 data ，只能通过调用管程提供的 enq() 和 deq() 。...我们通过一段代码说明，实现一个阻塞队列，队列分别有出队与入队，都是要先获取互斥锁，就像管程中的入口。...如果入队成功，那么队列就不空了，就需要通知条件变量：队列不空notEmpty对应的等待队列。 如果出队成功，那就队列就不满了，就需要通知条件变量：队列不满notFull对应的等待队列。...notEmpty.await(); } // 省略出队操作... // 出队后，通知可入队 notFull.signal(); }
新元素被添加到队尾，而元素的删除操作总是从队头进行。...使用两个指针，一个指向队头，一个指向队尾，来标记队列中元素的位置。 入队操作时，将新元素添加到队尾，同时更新队尾指针。 出队操作时，从队头删除元素，同时更新队头指针。...无论队列的大小如何，入队操作只涉及对队尾指针的更新以及对数组中指定位置的赋值操作。因此，入队操作的时间复杂度是常数级别的，与队列中元素的数量无关。...4.2 出队操作 出队操作的实现 出队操作用于从队列中删除并返回队头元素，以下是一个示例的 C 语言代码实现： int dequeue(Queue* queue) { if (queue->front...无论队列中有多少个元素，出队操作所需的额外空间都是固定的。 4.3 队列的其他操作 队列的大小获取 要获取队列的大小，可以定义一个函数来返回队列中元素的数量。
image.png 如图ArrayBlockingQueue内部有个数组items用来存放队列元素，putindex下标标示入队元素下标，takeIndex是出队下标，count统计队列元素个数，从定义可知道并没有使用...另外有个独占锁lock用来对出入队操作加锁，这导致同时只有一个线程可以访问入队出队，另外notEmpty，notFull条件变量用来进行出入队的同步。...0 : i; } 这里由于在操作共享变量前加了锁，所以不存在内存不可见问题，加过锁后获取的共享变量都是从主内存获取的，而不是在CPU缓存或者寄存器里面的值，释放锁后修改的共享变量值会刷新会主内存中。...cast(items[i]); } 八、 size操作 获取队列元素个数，非常精确因为计算size时候加了独占锁，其他线程不能入队或者出队或者删除元素 public int size() {...其中offer,poll操作通过简单的加锁进行入队出队操作，而put,take则使用了条件变量实现如果队列满则等待，如果队列空则等待，然后分别在出队和入队操作中发送信号激活等待线程实现同步。
在函数体，一个被声明为静态的变量在这一函数被调用过程中维持其值不变。 2). 一个被声明为静态的变量可以被模块内所用函数访问，但不能被其他文件函数访问。它是一个本地的全局变量。 3)....对于静态成员函数，只能访问静态成员函数和静态成员变量，不能访问非静态成员函数或者变量。...入队: 将新元素push入栈A; 出队: (1)判断栈B是否为空； (2)如果不为空，则将栈A中所有元素依次pop出并push到栈B； (3)将栈B的栈顶元素pop出； 这样实现的队列入队和出队的平摊复杂度都还是...入队: 将新元素push入栈A; 出队: (1)判断栈B是否为空； (2)如果不为空，则将栈A中所有元素依次pop出并push到栈B； (3)将栈B的栈顶元素pop出； 36....='\0' ) { len++; } return len; }' ) { len++; } return len; } 这样实现的队列入队和出队的平摊复杂度都还是O(1), 比上面的几种方法要好
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
