1.队列的基本知识
和栈相反,队列是一种先进先出(First In First Out,缩写为FIFO)的线性表,它只允许一端进行插入,而在另外一端删除元素。这和我们日常生活中的排队是一致的,最早进入队列的元素最早离开。在队列中,允许插入的一端叫做队尾(rear),允许删除的一端称之为队头(front)。
2.队列的基本操作
InitQueue:构造一个空队列
DestroyQueue:销毁队列
ClearQueue:清空队列
QueueEmpty:判断队列是否为空
QueueLength:队列长度
GetHead:获取队列头部元素
EnQueue:入列
DeQueue:出列
3.java中阻塞队列 -
ArrayBlockingQueue
的实现
阻塞队列的概念是,一个指定长度的队列,如果队列满了,添加新元素的操作会被阻塞等待,直到有空位为止。同样,当队列为空时候,请求队列元素的操作同样会阻塞等待,直到有可用元素为止。
利用数组来实现阻塞队列
/**
*初始化一个长度为capacity的数组
*采用非公平策略:让线程自由竞争锁,不保证等待最长的线程优先获取锁
*采用公平策略:让等待时间最长的线程优先获取锁
*/
public ArrayBlockingQueue(int capacity) {
this(capacity, false);
}
/**
*出列:
*将数组的中第一个有值的元素至空
*如果数组元素的实际长度为0,则等待
*直到获得通知
*/
public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
try {
while (count == 0)
notEmpty.await();
} catch (InterruptedException ie) {
notEmpty.signal(); // propagate to non-interrupted thread
throw ie;
}
E x = extract();
return x;
} finally {
lock.unlock();
}
}
/**
*入列:
*将新的元素插入队尾
*如果队列已满,则等待
*
*/
public void put(E e) throws InterruptedException {
if (e == null) throw new NullPointerException();
final E[] items = this.items;
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
try {
while (count == items.length)
notFull.await();
} catch (InterruptedException ie) {
notFull.signal(); // propagate to non-interrupted thread
throw ie;
}
insert(e);
} finally {
lock.unlock();
}
}
/**
*获取队列头元素
*
*/
public E peek() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return (count == 0) ? null : items[takeIndex];
} finally {
lock.unlock();
}
}
/*
*获取队列长度
*
*/
public int size() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return count;
} finally {
lock.unlock();
}
}
4.Sample
- 大小: 23.8 KB
分享到:
相关推荐
java面试笔试资料包括JAVA基础核心知识点深度学习Spring面试题等资料合集: JAVA核心知识点整理-282页 Java与哈希算法.docx Java中Lambda表达式的使用.docx JAVA多线程之线程间的通信方式.docx Java注解详解.docx ...
数组、链表、栈、队列、哈希表、树、堆、图等数据结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。 算法:搜索、排序、分治、回溯、动态规划、贪心等算法的定义、优缺点、效率、应用场景、解题步骤...
面试题包括以下十九部分:Java 基础、容器、多线程、反射、对象拷贝、Java Web 模块、异常、网络、设计模式、Spring/Spring MVC、Spring Boot/Spring Cloud、Hibernate、Mybatis、RabbitMQ、Kafka、Zookeeper、MySql...
13.4. CAS的缺点 35 14. Map数据结构? 35 14.1. 一、定义 36 14.2. 二、构造函数 36 14.3. 三、数据结构 36 14.4. 四、存储实现:put(key,vlaue) 38 14.5. 五、读取实现:get(key) 41 15. 一百万数据放Arraylist...
Java并发编程最全面试题,包括并发编程基础知识、并发理论、线程池、并发容器、并发队列、并发工具类等方面的常见面试题。例如线程池的概念、优缺点、创建方式、线程池原理等等。 本文档适用于将要参加Java开发相关...
【数据结构】数组与链表的优缺点 139 【算法】什么是hash? 140 【算法】排序 141 【算法】冒泡排序 141 【算法】快速排序 142 【算法】归并排序的过程?时间复杂度?空间复杂度? 143 【算法】什么是一致性哈希?...
使用JAVA中效率高的类,比如Array List比Vector性能好.>高并发 - 需要解决的问题一:应用缓存二:缓存三:多级缓存四:池化五:异步并发六:扩容七 :队列高并发-应用缓存堆缓存 使用Java堆内存来存储缓存对象....
25 JAVA8 与元数据.................................................................................................................................25 2.4. 垃圾回收与算法 .................................
25 JAVA8 与元数据.................................................................................................................................25 2.4. 垃圾回收与算法 .................................
6.25 堆栈与队列 138 6.26 真正的递归 140 6.27 树与单链表,图 145 6.28 树 146 6.29 真正的散列表 148 6.30 算法设计方法 148 第7章 抽象之高级语法机制 149 7.1 真正的OO解 149 7.2真正的对象 151 7.3真正的继承 ...
数据结构与算法 排序算法 内排序 八大基础排序 选择排序 简单选择排序 思想 每次选择最大的数插入到末尾中 做法 外层for循环控制次数 内层for循环找出最大的值的角...
目前市场业务中在产品以及其他项目的认证和检测方面存在诸多不便,用户需要实地考察并频繁与检测单位沟通,填写繁琐的纸质检测报告、当面送递样品,对于检测环节中存在的问题难以及时交互并处理。市场上相应的检测...
运算表达式类的原理及其实现 #实现的18位身份证格式验证算法 身份证15To18 的算法(C#) 一组 正则表达式 静态构造函数 忽略大小写Replace效率瓶颈IndexOf 随机排列算法 理解C#中的委托[翻译] 利用委托机制处理.NET中...
链表取代数组作为堆栈和队列的基础结构。 这就是我们为 LRU 缓存使用链表的原因。 事实上,您可以在许多使用数组的情况下使用链表,除非您需要使用索引频繁随机访问单个项目。 class Link { public int data; public...