对于队列的应用的很多,但是我觉得理解队列最重要的是要记住,先进先出,一端插入,一端删除。
(1)队列的定义:队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,进行插入操作的端称为队尾, 进行删除操作 的端称为队头。
理解好定义,那么我们就通过代码再来分析一下:
public class Queue<E> { private int front;//队头一端,只允许删除 private int rear;//队尾一端,只允许插入操作 private int max_size =16; private Object[] data; public Queue() { this(10); } public Queue(int size){ if(size<0){ throw new IllegalArgumentException("队列初始化失败,原因是:"+size); } this.max_size = size; front = rear = 0; data = new Object[max_size]; } //判断是否为空 public boolean isEmpty(){ return rear==front?true:false; } //入队 public boolean add(E e){ if(rear==max_size){ throw new RuntimeException("队列满了"); }else{ data[rear++] = e; return true; } } //返回队首元素,不删除元素 public E peek(){ if(isEmpty()){ return null; } return (E) data[front]; } //出队 public E poll(){ if(isEmpty()){ throw new RuntimeException("队列为空"); } else{ E e = (E) data[front]; data[front++] = null; return e; } } //长度 public int length(){ return rear-front; } }
接着来测试一下:
public class Main { public static void main(String[] args) { Queue queue = new Queue(); queue.add("h"); queue.add("e"); queue.add("l"); queue.add("l"); queue.add("o"); int length = queue.length(); for(int i=0;i<length;i++){ System.out.println(queue.poll()); } //System.out.println(queue.poll()); } }结果:
h
e
l
l
o
其实队列的实现是比较好处理的,关键是怎么处理好溢出的问题,因为这个会造成内存的浪费。
有不对的地方欢迎指出,谢谢。