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);
 }
}

以上这篇java队列实现方法(顺序队列,链式队列,循环队列)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持。