数据结构队列之java实现

队列：
队列是一种先进先出的线性表（FIFO），它只允许在表的一端进行插入，而在另一端删除元素。在队列中，允许插入数据一端成为队尾（rear），允许删除的那一端称为队头（front）。
队列的基本操作：
isEmpty() 判断空队列
isFull() 判断满队列
put() 入队列
get() 出队列
取队首元素（返回队首元素，不修改队首指针）
清空队列

-顺序队列：
顺序队列利用一组地址连续的存储单元依次存放自队首到队尾的数据元素，同时由于队的操作的特殊性，还必须附两个位置指针front和rear来动态地指示队首元素和队尾元素在顺序队列中的位置。通常front=rear表示空队列。（rear+1）%maxSize = front表示队满。

-链式队列：
采用链表作为存储结构实现的队列。为便于操作，采用带头结点的单链表实现队列。因为队列的插入和删除操作位置不同，所以链表需要设置表头指针和表尾指针分别指队首和队尾。

-循环队列：
假设向量的空间是m,只要在入出队列时，将队首和队尾的指针对m做求模运算即可实现队首和队尾指针的循环，即队首和队尾指针的取值范围是0到m-1之间。

java值demo实现：

/**
 * Created by g-Linlf on 2017/5/26.
 * 顺序队列
 * 链式队列
 * 循环队列
 **/
public class TestQueue {
    public static void main(String args[]) throws Exception {
        LinkedListQueue queue1 = new LinkedListQueue();
        queue1.put(1);
        //queue1.put(1);
        queue1.clear();
        System.out.println(queue1.size());
        queue1.put(1);
        System.out.println(queue1.get());
        System.out.println(queue1.isEmpty());
        System.out.println("====================");
        ArrayQueue arrayQueue = new ArrayQueue(2);
        arrayQueue.put(2);
        arrayQueue.put(7);
        System.out.println(arrayQueue.isFull());
        System.out.println(arrayQueue.size());
        System.out.println(arrayQueue.get());
        System.out.println(arrayQueue.isEmpty());
        arrayQueue.clear();
        arrayQueue.put(3);
        System.out.println("====================");
        Queue queue3 = new LinkedBlockingQueue();//
        Queue queue4 = new ArrayBlockingQueue(2);//
        Object[] objects = new Object[2];
        System.out.println(objects[1] == null);
    }
}
//使用LinkedList实现
class LinkedListQueue {
    private LinkedList ll = new LinkedList();
    //入队操作
    public void put(Object o) {
        ll.addLast(o);
    }
    //使用removeFirst()方法，返回队列中第一个数据，然后将它从队列 中删除
    //出队操作
    public Object get() {
        return ll.removeFirst();
    }
    public boolean isEmpty() {
        return ll.isEmpty();
    }
    //队列大小
    public int size() {
        return ll.size();
    }
    //清空队列
    public void clear() {
        ll = null;
        ll = new LinkedList();
    }
}
//使用数组实现
class ArrayQueue {
    private int maxSize;
    private Object[] queue;
    private int front; //头指针 允许删除
    private int rear; //尾指针 允许插入数据
    public ArrayQueue(int size) {
        maxSize = size + 1; //尾指针指向下一个位置（该位置为空）
        queue = new Object[maxSize];
        front = 0;
        rear = 0;
    }
    public void put(Object value) {
        if (isFull()) {
            System.out.println("Full!");
            //throw new RuntimeException("queue is full!");
            return;
        }
        queue[rear] = value;
        rear = (rear + 1) % queue.length;
    }
    public Object get() throws Exception {
        Object value;
        if (isEmpty()) {
            throw new RuntimeException("Empty!");
        }
        value = queue[front];
        queue[front] = null; //释放对象
        front = (front + 1) % queue.length;
        return value;
    }
    //获取实际存储数据大小
    public int size() {
        return (rear - front);
    }
    //清空队列
    public void clear() {
        queue = null;
        queue = new Object[maxSize];
    }
    public boolean isEmpty() {
        return rear == front;
    }
    public boolean isFull() {
        return rear + 1 - front == queue.length;
        //return (rear + 1) % maxSize == front;
    }
}

数据结构 队列 之java实现

数据结构队列之java实现