Java实现队列

队列是一种先进先出的数据结构，和栈刚好相反，队列在算法中也应用广泛。本文，我们主要探讨Java实现队列。

队列

队列是一种先进先出的数据结构，就像排队打饭一样，先排队的会先打饭。队列的结构如下，分为队头和队尾。队列的实现分为动态实现和静态实现

队列结构

Java实现静态队列

通过数组实现队列和通过数组实现栈类似。代码实现如下：

public class Queue {

    private Object[] data;
    private int front;//队列头
    private int rear;//队列尾
    private int size;//队列大小

    public Queue(int size) {
        this.size = size;
        data = new Object[size];
    }

    /**
     * 入队
     * @param value
     */
    public void in(Object value) throws Exception {
        if(rear == size){
            throw  new Exception("队列已满异常");
        }

        data[rear ++] = value;
    }

    /**
     * 出队
     */
    public Object out() throws Exception {
        if(isEmpty()){
            throw  new Exception("空队列异常");
        }
        Object value = data[front];
        data[front++] = null;

        return value;
    }

    /**
     * 是否为空队列
     * @return
     */
    public boolean isEmpty(){
        return  front == rear;
    }

    /**
     * 遍历队
     */
    public void traverse(){
        for(int i = front; i < rear; i++){
            System.out.println(""+data[i]);
        }
    }
}

Java实现动态队列

动态队列是通过链表实现的，有个头指针指向队头

public class LinkQueue {

    private Node front;
    private Node rear;
    private int size;

    public LinkQueue() {
        this.front = new Node();
        this.rear = new Node();
    }

    /**
     * 入队
     * @param value
     */
    public void in(Object value)throws  Exception{
      Node newNode = new Node(value);
      Node temp = front;

      while (temp.next != null){
          temp = temp.next;
      }

      temp.next = newNode;
      rear = newNode;
      size ++;
    }

    /**
     * 出队
     * @throws Exception
     */
    public Object out()throws  Exception{
        if(front.next == null){
            throw new  Exception("队列为空异常");
        }
        Node firstNode = front.next;
        front.next = firstNode.next;
        size--;

        return firstNode.data;
    }

    /**
     * 遍历队列
     */
    public void traverse(){
        Node temp = front.next;
        while ( temp != null){
            System.out.println(""+temp.data);

            temp = temp.next;
        }
    }
}

代码链接