- 浏览: 691671 次
- 性别:
- 来自: 北京
博客专栏
-
读金庸故事,品程序人生
浏览量:47234
文章分类
最新评论
-
hty881008:
LZ,你的json返回是怎么出来的,我的怎么是No messa ...
使用CXF暴露您的REST服务 -
jxFY:
赞
Apache的对象池化工具commons-pool -
wangyudong:
新版本的Wisdom RESTClient地址https:// ...
使用CXF暴露您的REST服务 -
wangyudong:
由CXF实现的微服务需要有比较好的工具去测试RESTful A ...
使用CXF暴露您的REST服务 -
spring_springdata:
可以参考最新的文档:如何在eclipse jee中检出项目并转 ...
Maven3实战笔记01环境配置与使用入门
1. 队列
队列又是一种比较特殊的线性表,和栈一样在线性表的基础上进行了一些限制操作。就是队列了。顾名思义,队列就是咱们排队买火车票一样,排在最前面的先买到,排到后面的后买到。先进先出、后进后出。 2. 队列的操作 队列的操作一般包括:进队列、出队列,访问队列头元素、删除队列头元素、判断队列是否为空、获得队列大小这些核心操作。Sun为Java的队列规定了一个规范、反映出来的的就是java.util.Queue,实现了此接口的所有方法,相当于“你按照Sun的Java规范为自己写了一个符合规范的队列实现类”。 3. 队列的使用场景 队列的使用场景其实个人感觉比栈要广泛一些,比如开发网络服务中间件,处理并发消息的时候就需要将这些消息组成队列的方式一个一个处理,再比如对象池的应用,底层完全可以做成一个对象队列,将一个用完的对象放回池中后,就是放到等待队列中,先归还的对象,下次再使用的时候就比后放入的对象优先调用,因为先归还的对象肯定是休息了很久了,该对象应当回收的资源也都回收了。 4. 队列的顺序实现 和栈结构一样队列也有两种实现方式,先来看顺序的实现方式,顺序实现方式就是利用数组,记录当前队列头标记nowTopIndex以及下一个、新的队列结尾元素的标记newTailIndex。 程序如下:
测试代码如下
运行后效果如下
5. 队列的链表实现 相对于顺序实现方式,链式实现相对比较简单,只需要利用Node结构,记录下队列的头Node和尾巴Node,在记录下元素个数就可以了。算法如下
测试代码和顺序实现的测试代码相同,在此不再赘述。 6. 总结 队列是一种比较简单线性表,使用场景很多,尤其是开发自己的类库层次。使用队列这种结构存储临时数据的情况比较多。顺序实现与链表实现各有利弊。一般元素个数比较固定用顺序实现方式,如果使用元素个数变化十分频繁,还是使用链表效率好一些。顺序实现方式存在一种隐患就是“假满现象”,所以顺序实现还可以采用循环队列,循环队列的原理就是如果头索引=尾索引,并且头索引不等于0,并且此时数组大小已经都用完了,那么将头、尾索引都置为0即可,这里就不给出代码了。当然以上2种方式的实现都是没有做安全检查的,而且顺序实现元素最大个数也只能拥有和数组一样的元素个数。Java有个常用的队列java.util.concurrent.ConcurrentLinkedQueue。
package dateStructer.queue;
/**
* 顺序队列
*
* @author liuyan
* @param <E>
*/
public class MyArrayQueue<E> implements Queue<E> {
// 默认大小
private final static int DefSize = 32;
// 临时数组
private Object[] objects;
// 当前队列头元素索引
private int nowTopIndex;
// 下一个队列新元素的索引
private int newTailIndex;
public MyArrayQueue() {
objects = new Object[DefSize];
}
/**
* 添加元素
*/
@Override
public boolean add(E e) {
int elementSize = newTailIndex - nowTopIndex;
if (elementSize == 0 && newTailIndex == 0) {
objects[0] = e;
nowTopIndex = 0;
newTailIndex = 1;
return true;
}
objects[newTailIndex++] = e;
return true;
}
/**
* 获取队头元素
*/
@Override
public E element() {
return (E) objects[nowTopIndex];
}
/**
* 返回头元素,不删除头元素
*/
@Override
public E peek() {
return (E) objects[nowTopIndex];
}
/**
* 返回头元素,删除头元素
*/
@Override
public E poll() {
if (objects[nowTopIndex] == null) {
return null;
}
E date = (E) objects[nowTopIndex];
objects[nowTopIndex++] = null;
return date;
}
@Override
public E remove() {
if (nowTopIndex == 0) {
return null;
}
E date = (E) objects[nowTopIndex];
objects[nowTopIndex--] = null;
return date;
}
@Override
public void clear() {
Arrays.fill(objects, null);
nowTopIndex = 0;
newTailIndex = 0;
}
@Override
public boolean contains(Object object) {
for (int i = 0; i < objects.length; i++) {
if (object == objects[i]) {
return true;
}
}
return false;
}
@Override
public boolean isEmpty() {
int elementSize = newTailIndex - nowTopIndex;
return elementSize == 0;
}
@Override
public int size() {
return newTailIndex - nowTopIndex;
}
@Override
public String toString() {
StringBuffer str = new StringBuffer("[");
int elementSize = newTailIndex - nowTopIndex;
for (int i = nowTopIndex; i < newTailIndex; i++) {
str.append("[" + objects[i].toString() + "],");
}
if (elementSize > 0) {
return str.substring(0, str.lastIndexOf(",")) + "]";
}
return str.append("]").toString();
}
}
public static void main(String[] args) {
MyArrayQueue<String> myQueue = new MyArrayQueue<String>();
myQueue.add("1");
myQueue.add("2");
myQueue.add("3");
System.out.println(myQueue.toString());
String e = myQueue.poll();
System.out.println(e);
System.out.println(myQueue.toString());
myQueue.add("4");
e = myQueue.peek();
System.out.println("是否为空队列" + myQueue.isEmpty());
System.out.println("队列大小" + myQueue.size());
System.out.println(e);
System.out.println(myQueue.toString());
System.out.println("是否包含相关元素" + myQueue.contains("1"));
System.out.println("是否包含相关元素" + myQueue.contains("2"));
myQueue.clear();
System.out.println("是否为空队列" + myQueue.isEmpty());
}
[[1],[2],[3]]
1
[[2],[3]]
是否为空队列false
队列大小3
2
[[2],[3],[4]]
是否包含相关元素false
是否包含相关元素true
是否为空队列true
package dateStructer.queue;
/**
* 实现自己的队列
* @author liuyan
* @param <E>
*/
public class MyQueue<E> implements Queue<E> {
/**
* 双向链表结构
*/
public class LinkNode {
// 真正的数据域
private E date;
// 记录上一个节点
private LinkNode prevLinkNode;
// 记录下一个节点
private LinkNode nextLinkNode;
public LinkNode() {
}
public LinkNode(E date, LinkNode prevLinkNode, LinkNode nextLinkNode) {
this.date = date;
this.prevLinkNode = prevLinkNode;
this.nextLinkNode = nextLinkNode;
}
}
// 结点个数
private int nodeSize;
// 头结点
private LinkNode headNode;
// 尾巴节点
private LinkNode tailNode;
public MyQueue(){
headNode = null;
tailNode = null;
}
/**
* 添加元素
*/
@Override
public boolean add(E element) {
if (nodeSize == 0) {
headNode = new LinkNode(element, null, tailNode);
}else {
if (tailNode == null) {
tailNode = new LinkNode(element, headNode, null);
headNode.nextLinkNode = tailNode;
nodeSize++;
return true;
}
LinkNode linkNode = tailNode;
tailNode = new LinkNode(element, linkNode, null);
linkNode.nextLinkNode = tailNode;
}
nodeSize++;
return true;
}
/**
* 访问队列头元素
*/
@Override
public E element() {
return headNode.date;
}
/**
* 返回头元素,不删除头元素
*/
@Override
public E peek() {
return headNode.date;
}
/**
* 返回头元素,删除头元素
*/
@Override
public E poll() {
LinkNode headNodeTemp = headNode;
E date = headNodeTemp.date;
if(headNode.nextLinkNode == null){
headNode.date = null;
headNode = null;
nodeSize--;
return date;
}else{
headNode = headNode.nextLinkNode;
if(headNode == tailNode){
tailNode = null;
}
}
nodeSize--;
return headNodeTemp.date;
}
/**
* 清除所有元素
*/
@Override
public void clear() {
LinkNode linkNodeNowTemp = headNode;
for (int i = 0; i < nodeSize; i++) {
if (linkNodeNowTemp != tailNode && linkNodeNowTemp != headNode) {
linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
linkNodeNowTemp.prevLinkNode.nextLinkNode = null;
linkNodeNowTemp.prevLinkNode.prevLinkNode = null;
linkNodeNowTemp.prevLinkNode.date = null;
linkNodeNowTemp.prevLinkNode = null;
} else if (linkNodeNowTemp == tailNode) {
linkNodeNowTemp.prevLinkNode = null;
} else if (linkNodeNowTemp == headNode) {
linkNodeNowTemp.nextLinkNode = null;
}
}
headNode = null;
tailNode = null;
nodeSize = 0;
}
/**
* 判断是否存在
*/
@Override
public boolean contains(Object object) {
LinkNode linkNodeNowTemp = headNode;
for (int i = 0; i < nodeSize; i++) {
if (object == linkNodeNowTemp.date) {
return true;
}
linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
}
return false;
}
/**
* 队列是否为空
*/
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return nodeSize == 0;
}
@Override
public int size() {
// TODO Auto-generated method stub
return nodeSize;
}
/**
* 根据索引号查找节点
*
* @param index
* @return
*/
public LinkNode findLinkNodeByIndex(int index) {
LinkNode linkNodeNowTemp = headNode;
for (int i = 0; i < nodeSize; i++) {
if (i == index) {
return linkNodeNowTemp;
}
linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
}
return null;
}
@Override
public String toString() {
StringBuffer str = new StringBuffer("[");
LinkNode linkNode = null;
for (int i = 0; i < nodeSize; i++) {
linkNode = findLinkNodeByIndex(i);
str.append("[" + linkNode.date + "],");
}
if (nodeSize > 0) {
return str.substring(0, str.lastIndexOf(",")) + "]";
}
return str.append("]").toString();
}
}
发表评论
-
Web应用单点压力测试调优-第6季-阶段性总结
2014-03-14 12:24 3253阶段性总结 <! ... -
Web应用单点压力测试调优-第5季
2014-03-13 09:32 4017各项配置: my.cnf [clien ... -
Web应用单点压力测试调优-第4季
2014-03-12 14:55 3038调整5-Tomcat的启动JVM参数 首先先启动 ... -
单点网站压力测试调优-第3季
2014-03-11 16:21 3298调整2-调整配置,数据库连接池数量 mysql ... -
Web应用单点压力测试调优-第2季
2014-03-07 16:52 8751并发1000,准备时间1s,让它产生大量的等待请求 ... -
单点网站压力测试调优-第1季
2014-03-07 10:36 3829环境介绍 虚拟机配置 ... -
编程质量提高建议总结1(持续总结)
2014-03-05 19:42 1217编程质量提高建议总结1(持续总结) 1.混淆字母要明显 ... -
关于博客文章内容显示不全的问题
2011-06-14 09:36 2268关于博客文章内容显示不全的问题,我发现有些文章显示内容不全。 ... -
Maven3实战笔记05仓库依赖解析与插件解析
2011-06-07 09:00 33671. Maven仓库依赖解析机 ... -
Apache的对象池化工具commons-pool
2011-05-16 09:21 129561. 前言 当我们的应用中创建一个十分最重量级的 ... -
将Sun的Open Message Queue与Spring集成
2011-05-06 09:01 34221. 前言 基于JMS标准的消息中间件实现的产品 ... -
要不要池化是个艰难的选择(转)-我觉得很生动就转载了下来
2011-05-05 09:50 1532转自http://www.ixpub.net/thre ... -
java.lang.IllegalStateException: STREAM错误的理解(转)
2011-05-04 18:09 13768转自http://dimple.iteye.com/blog/ ... -
Spring3配置声明式事务
2011-05-02 16:52 45021. 配置Spring3声明式事务 在Sprin ... -
Java基础复习笔记11基本排序算法
2011-04-25 13:20 20791. 排序 排序是一个历来都是很多算法家热衷的领 ... -
Java基础复习笔记08数据结构-二叉树和二叉树的遍历
2011-04-22 09:10 24721. 二叉树 一 ... -
Java基础复习笔记07数据结构-树的概述
2011-04-19 17:35 18541. 树的概念 如果线性表、栈、队列是线性结构( ... -
Java基础复习笔记04数据结构-线性表
2011-04-15 14:14 22391. 线性表 线性表是数据结构的一种逻辑结构,其 ... -
Java基础复习笔记03面试、笔试、开发中我们不太注意的陷阱之流程控制、面向对象、异常处理
2011-04-13 09:59 21681. switch语句的用法 有人说:“笔者基础 ... -
Java基础复习笔记03面试、笔试、开发中我们不太注意的陷阱之多线程
2011-04-13 09:51 19151. 什么样的对 ...
相关推荐
Java基础复习笔记09数据结构-哈夫曼树
Java基础复习笔记04数据结构-线性表。
Java基础复习笔记10数据结构-排序二叉树
Java基础复习笔记07数据结构-树的概述。
Java基础复习笔记05数据结构-栈~~~~~~~~~~
Java基础复习笔记08数据结构-二叉树和二叉树的遍历。
java基础笔记数据结构-队列,详细描述了队列的原理及其实现方式,基础数据结构。
Java基础每日复习笔记-JavaSE高级阶段.2020-10-13-211312.edf
Java基础每日复习笔记-JavaSE基础阶段.edf
Java基础每日复习笔记-JavaSE高级阶段.edf
JAVA学习经典笔记-----1JAVA学习经典笔记-----1JAVA学习经典笔记-----1JAVA学习经典笔记-----1JAVA学习经典笔记-----1
软考中级 - 软件设计师 - 专题复习笔记3软考中级 - 软件设计师 - 专题复习笔记3软考中级 - 软件设计师 - 专题复习笔记3软考中级 - 软件设计师 - 专题复习笔记3软考中级 - 软件设计师 - 专题复习笔记3软考中级 - 软件...