疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

Java数据结构队列


 

        队列类似于现实生活中的排队。队列是先进先出的原则,只允许在队列头部去除元素,队列尾部添加元素。
 
  下面是分别用数组和链表为存储结构实现的队列
 
  public interface Queue<T> {
 
  int size();
 
  T remove();
 
  void add(T element);
 
  boolean isEmpty();
 
  void clear();
 
  boolean hasElement();
 
  }
 
  public class ArrayQueue<T> implements Queue<T>{
 
  //数组的默认大小
 
  private static final int DEFAULT_SIZE = 10;
 
  //默认用数组存储
 
  private Object[] values = new Object[DEFAULT_SIZE];
 
  private int arrayLength = DEFAULT_SIZE;
 
  //
 
  private int top = -1;
 
  private int bottom = -1;
 
  @Override
 
  public int size() {
 
  return (top - bottom) + 1;
 
  }
 
  //队列顶端删除元素
 
  @SuppressWarnings("unchecked")
 
  @Override
 
  public T remove() {
 
  if(isEmpty()){
 
  throw new NullPointerException();
 
  }
 
  T value = (T)values[++top];
 
  return  value;
 
  }
 
  //在对列底添加元素
 
  @Override
 
  public void add(T element) {
 
  if(bottom >= arrayLength-1){
 
  resize();
 
  }
 
  values[++bottom] = element;
 
  }
 
  @Override
 
  public boolean isEmpty() {
 
  return top > bottom;
 
  }
 
  @Override
 
  public void clear() {
 
  top = bottom = -1;
 
  }
 
  @Override
 
  public boolean hasElement() {
 
  return top < bottom;
 
  }
 
  public void resize(){
 
  arrayLength = arrayLength + DEFAULT_SIZE;
 
  Object[] temp = new Object[arrayLength];
  for(int i=0;i<VALUES.LENGTH;I++){ ArrayQueue<Integer args[]){ main(String void static public } values="temp;" temp[i]="values[i];"> arrayQueue = new ArrayQueue<INTEGER>();
 
  arrayQueue.add(1);
 
  arrayQueue.add(2);
 
  arrayQueue.add(3);
 
  arrayQueue.add(4);
 
  arrayQueue.add(5);
 
  arrayQueue.add(6);
 
  arrayQueue.add(7);
 
  arrayQueue.add(8);
 
  arrayQueue.add(9);
 
  arrayQueue.add(10);
 
  arrayQueue.add(11);
 
  while(arrayQueue.hasElement()){
 
  System.out.println(arrayQueue.remove());
 
  }
 
  }
 
  }
 
  public class LinkedList<T> implements Queue<T> {
 
  private int size = 0;
 
  private Item top ;
 
  private Item bottom;
 
  private class Item{
 
  private T data;
 
  private Item next;
 
  Item(T data,Item next){
 
  this.data = data;
 
  this.next = next;
 
  }
 
  }
 
  @Override
 
  public int size() {
 
  return size;
 
  }
 
@Override
 
  public T remove() {
 
  if(--size < 0){
 
  throw new NullPointerException();
 
  }
 
  T value = top.data;
 
  top = top.next;
 
  return value;
 
  }
 
  @Override
 
  public void add(T element) {
 
  if(top == null){
 
  top = new Item(element,null);
 
  }else if(bottom == null){
 
  bottom = new Item(element,null);
 
  top.next = bottom;
 
  }else{
 
  Item item = new Item(element,null);
 
  bottom.next = item;
 
  bottom = item;
 
  }
 
  size ++;
 
  }
 
  @Override
 
  public boolean isEmpty() {
 
  return size == 0;
 
  }
 
  @Override
 
  public void clear() {
 
  top = bottom = null;
 
  }
 
  @Override
 
  public boolean hasElement() {
 
  if(top == null){
 
  return false;
 
  }
 
  return top.data != null;
 
  }
 
  public static void main(String args[]){
 
  LinkedList<INTEGER> linkedList = new LinkedList<INTEGER>();
 
  linkedList.add(1);
 
  linkedList.add(2);
 
  linkedList.add(3);
 
  linkedList.add(4);
 
  linkedList.add(5);
 
  linkedList.add(6);
 
  linkedList.add(7);
 
  linkedList.add(8);
 
  linkedList.add(9);
 
  linkedList.add(10);
 
  linkedList.add(11);
 
  while(linkedList.hasElement()){
 
  System.out.println(linkedList.remove());
 
  }
 
  }
 
  }