java队列实现方法(顺序队列,链式队列,循环队列)
作者:jiutianhe 发布时间:2023-06-24 01:43:17
标签:java,队列,顺序,链式,循环
双向顺序队列ArrayDeque和双向链式队列LinkedList,JDK已经包含,在此略。ArrayDeque包括顺序栈和顺序队列,LinkedList包含链式栈和链式队列。ArrayDeque和LinkedList都是线程不安全的。PriorityQueue优先队列也在JDK。
1.顺序队列的实现
package lang;
import java.io.Serializable;
import java.util.Arrays;
/**
* @ClassName: ArrayQueue
* @Description: 顺序队列
* @date 2014年1月20日 下午3:46:19
* @param <T>
*/
public class ArrayQueue<T> implements Serializable{
/**
* @Fields serialVersionUID : TODO
*/
private static final long serialVersionUID = 7333344126529379197L;
private int DEFAULT_SIZE = 10;
private int capacity;//保存数组的长度
private Object[] elementData;//定义一个数组用于保存顺序队列的元素
private int front = 0;//队头
private int rear = 0;//队尾
//以默认数组长度创建空顺序队列
public ArrayQueue() {
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
//以一个初始化元素来创建顺序队列
public ArrayQueue(T element) {
this();
elementData[0] = element;
rear++;
}
public ArrayQueue(int initSize) {
elementData = new Object[initSize];
}
/**
* 以指定长度的数组来创建顺序队列
* @param element 指定顺序队列中第一个元素
* @param initSize 指定顺序队列底层数组的长度
*/
public ArrayQueue(T element, int initSize) {
this.capacity = initSize;
elementData = new Object[capacity];
elementData[0] = element;
rear++;
}
/**
* @Title: size
* @Description: 获取顺序队列的大小
* @return
*/
public int size() {
return rear - front;
}
/**
* @Title: offer
* @Description: 入队
* @param element
*/
public void offer(T element) {
ensureCapacity(rear + 1);
elementData[rear++] = element;
}
private void ensureCapacity(int minCapacity) {
//如果数组的原有长度小于目前所需的长度
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
/**
* @Title: poll
* @Description: 出队
* @return
*/
public T poll() {
if (isEmpty()) {
throw new IndexOutOfBoundsException("空队列异常");
}
//保留队列的front端的元素的值
T oldValue = (T) elementData[front];
//释放队列的front端的元素
elementData[front++] = null;
return oldValue;
}
/**
* @Title: peek
* @Description: 返回队列顶元素,但不删除队列顶元素
* @return
*/
public T peek() {
if (isEmpty()) {
throw new IndexOutOfBoundsException("空队列异常");
}
return (T) elementData[front];
}
/**
* @Title: isEmpty
* @Description: 判断顺序队列是否为空队列
* @return
*/
public boolean isEmpty() {
return rear == front;
}
/**
* @Title: clear
* @Description: 清空顺序队列
*/
public void clear() {
//将底层数组所有元素赋为null
Arrays.fill(elementData, null);
front = 0;
rear = 0;
}
public String toString() {
if (isEmpty()) {
return "[]";
} else {
StringBuilder sb = new StringBuilder("[");
for (int i = front; i < rear; i++) {
sb.append(elementData[i].toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2, len).append("]").toString();
}
}
}
2. 链式队列的实现
package lang;
import java.io.Serializable;
/**
* @ClassName: LinkQueue
* @Description: 链式队列
* @date 2014年1月21日 下午3:24:38
* @param <T>
*/
public class LinkQueue<T> implements Serializable{
/**
* @Fields serialVersionUID : TODO
*/
private static final long serialVersionUID = -6726728595616312615L;
//定义一个内部类Node,Node实例代表链队列的节点。
private class Node {
private T data;//保存节点的数据
private Node next;//指向下个节点的引用
//无参数的构造器
public Node() {
}
//初始化全部属性的构造器
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
private Node front;//保存该链队列的头节点
private Node rear;//保存该链队列的尾节点
private int size;//保存该链队列中已包含的节点数
/**
* <p>Title: LinkQueue </p>
* <p>Description: 创建空链队列 </p>
*/
public LinkQueue() {
//空链队列,front和rear都是null
front = null;
rear = null;
}
/**
* <p>Title: LinkQueue </p>
* <p>Description: 以指定数据元素来创建链队列,该链队列只有一个元素</p>
*/
public LinkQueue(T element) {
front = new Node(element, null);
//只有一个节点,front、rear都指向该节点
rear = front;
size++;
}
/**
* @Title: size
* @Description: 获取顺序队列的大小
* @return
*/
public int size() {
return size;
}
/**
* @Title: offer
* @Description: 入队
* @param element
*/
public void offer(T element) {
//如果该链队列还是空链队列
if (front == null) {
front = new Node(element, null);
rear = front;//只有一个节点,front、rear都指向该节点
} else {
Node newNode = new Node(element, null);//创建新节点
rear.next = newNode;//让尾节点的next指向新增的节点
rear = newNode;//以新节点作为新的尾节点
}
size++;
}
/**
* @Title: poll
* @Description: 出队
* @return
*/
public T poll() {
Node oldFront = front;
front = front.next;
oldFront.next = null;
size--;
return oldFront.data;
}
/**
* @Title: peek
* @Description: 返回队列顶元素,但不删除队列顶元素
* @return
*/
public T peek() {
return rear.data;
}
/**
* @Title: isEmpty
* @Description: 判断顺序队列是否为空队列
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* @Title: clear
* @Description: 清空顺序队列
*/
public void clear() {
//将front、rear两个节点赋为null
front = null;
rear = null;
size = 0;
}
public String toString() {
//链队列为空链队列时
if (isEmpty()) {
return "[]";
} else {
StringBuilder sb = new StringBuilder("[");
for (Node current = front; current != null; current = current.next) {
sb.append(current.data.toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2, len).append("]").toString();
}
}
public static void main(String[] args) {
LinkQueue<String> queue = new LinkQueue<String>("aaaa");
//添加两个元素
queue.offer("bbbb");
queue.offer("cccc");
System.out.println(queue);
//删除一个元素后
queue.poll();
System.out.println("删除一个元素后的队列:" + queue);
//再次添加一个元素
queue.offer("dddd");
System.out.println("再次添加元素后的队列:" + queue);
//删除一个元素后,队列可以再多加一个元素
queue.poll();
//再次加入一个元素
queue.offer("eeee");
System.out.println(queue);
}
}
3. 循环队列的实现
package lang;
import java.io.Serializable;
import java.util.Arrays;
/**
* @ClassName: LoopQueue
* @Description: 循环队列
* @date 2014年1月20日 下午3:47:14
*/
public class LoopQueue<T> implements Serializable{
/**
* @Fields serialVersionUID : TODO
*/
private static final long serialVersionUID = -3670496550272478781L;
private int DEFAULT_SIZE = 10;
private int capacity;//保存数组的长度
private Object[] elementData;//定义一个数组用于保存循环队列的元素
private int front = 0;//队头
private int rear = 0;//队尾
//以默认数组长度创建空循环队列
public LoopQueue() {
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
//以一个初始化元素来创建循环队列
public LoopQueue(T element) {
this();
elementData[0] = element;
rear++;
}
/**
* 以指定长度的数组来创建循环队列
* @param element 指定循环队列中第一个元素
* @param initSize 指定循环队列底层数组的长度
*/
public LoopQueue(T element, int initSize) {
this.capacity = initSize;
elementData = new Object[capacity];
elementData[0] = element;
rear++;
}
//获取循环队列的大小
public int size() {
if (isEmpty()) {
return 0;
}
return rear > front ? rear - front : capacity - (front - rear);
}
//插入队列
public void add(T element) {
if (rear == front && elementData[front] != null) {
throw new IndexOutOfBoundsException("队列已满的异常");
}
elementData[rear++] = element;
//如果rear已经到头,那就转头
rear = rear == capacity ? 0 : rear;
}
//移除队列
public T remove() {
if (isEmpty()) {
throw new IndexOutOfBoundsException("空队列异常");
}
//保留队列的rear端的元素的值
T oldValue = (T) elementData[front];
//释放队列的rear端的元素
elementData[front++] = null;
//如果front已经到头,那就转头
front = front == capacity ? 0 : front;
return oldValue;
}
//返回队列顶元素,但不删除队列顶元素
public T element() {
if (isEmpty()) {
throw new IndexOutOfBoundsException("空队列异常");
}
return (T) elementData[front];
}
//判断循环队列是否为空队列
public boolean isEmpty() {
//rear==front且rear处的元素为null
return rear == front && elementData[rear] == null;
}
//清空循环队列
public void clear() {
//将底层数组所有元素赋为null
Arrays.fill(elementData, null);
front = 0;
rear = 0;
}
public String toString() {
if (isEmpty()) {
return "[]";
} else {
//如果front < rear,有效元素就是front到rear之间的元素
if (front < rear) {
StringBuilder sb = new StringBuilder("[");
for (int i = front; i < rear; i++) {
sb.append(elementData[i].toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2, len).append("]").toString();
}
//如果front >= rear,有效元素为front->capacity之间、0->front之间的
else {
StringBuilder sb = new StringBuilder("[");
for (int i = front; i < capacity; i++) {
sb.append(elementData[i].toString() + ", ");
}
for (int i = 0; i < rear; i++) {
sb.append(elementData[i].toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2, len).append("]").toString();
}
}
}
public static void main(String[] args) {
LoopQueue<String> queue = new LoopQueue<String>("aaaa", 3);
//添加两个元素
queue.add("bbbb");
queue.add("cccc");
//此时队列已满
System.out.println(queue);
//删除一个元素后,队列可以再多加一个元素
queue.remove();
System.out.println("删除一个元素后的队列:" + queue);
//再次添加一个元素,此时队列又满
queue.add("dddd");
System.out.println(queue);
System.out.println("队列满时的长度:" + queue.size());
//删除一个元素后,队列可以再多加一个元素
queue.remove();
//再次加入一个元素,此时队列又满
queue.add("eeee");
System.out.println(queue);
}
}
来源:http://blog.csdn.net/jiutianhe/article/details/18606295
0
投稿
猜你喜欢
- 委托给了C#操作函数的灵活性,我们可使用委托像操作变量一样来操作函数,其实这个功能并不是C#的首创,早在C++时代就有函数指针这一说法,而在
- 具体实现过程请看下面代码:简单的调用了一下系统的拍照功能代码如下所示://拍照的方法 private void openTakePhoto(
- 一、前言在日常工作中,如果涉及到与第三方进行接口对接,有的会使用WebService的方式,这篇文章主要讲解在.NET Framework中
- resultType 与 parameterType 的基本使用的区别1、使用 resultType:主要针对于从数据库中提取相应的数据出来
- reduce()简介Reduce 原意:减少,缩小根据指定的计算模型将Stream中的值计算得到一个最终结果解释:reduce 操
- 上文对数据结构与算法,有了一个简单的概述与介绍,这篇文章,我们介绍一中典型数据结构——线性结构。什么是线性结构,线性结构是最简单、最基本、最
- 前言回老家,实在太无聊,于是乎给自己整了一套台式机配置,总价 1W+,本以为机器到位后可以打打游戏,学学技术打发无聊的时光。但是我早已不是从
- 大多数网站会设置用户权限,如过滤非法用户,用户不登录时不能进行访问,或者设置访问的权限,如部分内容仅对VIP开放等等,这些权限的控制都可以用
- 前言本文主要给大家介绍了关于利用Spring Data MongoDB持久化文档数据的相关内容,分享出来供大家参考学习,下面话不多说了,来一
- SpringMVC的数据响应SpringMVC的数据响应方式①页面跳转直接返回字符串(如在一个方法中,return了一个"xxx.
- 本文实例为大家分享了Unity3D UGUI实现缩放循环拖动卡牌展示的具体代码,供大家参考,具体内容如下需求:游戏中展示卡牌这种效果也是蛮酷
- 前言Google终于发布了一个和SQLite相关的库了。之前一直都是在SQLite、XUtils、greenDao、Realm这些数据库之间
- 一、理解slf4j(Simple Logging Facade for Java),表示为java提供的简单日志门面,更底层一点说就是接口。
- 声明一个客户端对象:protected RedisClient Redis = new RedisClient("127.0.0
- 一、什么是CharacterEncodingFilter官方解释如下是spring内置过滤器的一种,用来指定请求或者响应的编码格式。在web
- 场景重现:1.微信小程序向后台发送请求 ——而后台web采用的springSecuriry没有token生成,就会拦截请求,,所以小编记录下
- 背景笔者使用 Spring Security 5.8 时,发现网上很多教程所教的 Spring Security 配置类 SecurityC
- 方法一第一步:添加引用using System.Printing;第二步:代码public static List<string>
- 1:普通实现99乘法表太简单,是个程序员都会,实现如下:package test.ms;public class Test99 {publi
- 简介Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩