数据结构-队列

概述

队列(Queue)和栈一样，也是 线性数据结构，它属于逻辑结构，物理实现既可以用 数组，也可以用 链表来完成。和栈不同的是，链表中的元素 先进先出 (First In First Out, 简称 FIFO)。队列的出口端叫 对头 (front), 队列的入口端叫 队尾 (rear)。

基本方法

添加元素

• put: 如果队列满，则阻塞
• add: 如果队列已满，则抛出一个IIIegaISlabEepeplian异常
• offer: 如果队列已满，则返回false

移除并返回队列头部元素

• remove: 如果队列为空，则抛出一个NoSuchElementException异常
• poll: 如果队列为空，则返回null
• take: 如果队列为空，则阻塞

返回队列头部的元素

• element: 如果队列为空，则抛出一个NoSuchElementException异常
• peek: 如果队列为空，则返回null

基于数组实现队列

public class ArrayQueue<E> {
    private E[] queue;//队列数组
    private int head=0;//头下标E
    private int tail=0;//尾下标
    private int count=0;//元素个数
    public ArrayQueue() {
        queue=(E[])new Object[10];
        this.head=0;//头下标为零
        this.tail=0;
        this.count=0;
    }
    public ArrayQueue(int size)
    {
        queue=(E[])new Object[size];
        this.head=0;
        this.tail=0;
        this.count=0;
    }
    //入队
    public boolean offer(E t)
    {
        if(count==queue.length)
            return false;
        queue[tail++%(queue.length)]=t;//如果不为空就放入下一个
        count++;
        return true;
    }
    //出队
    public E poll()
    {
        if(count==0)//如果是空的那就不能再出栈了
            return null;
        count--;
        return queue[head++%(queue.length)];
    }
    //查队头
    public E showHead()
    {
        if(count==0) return null;
        return queue[head];
    }
    //判满
    public boolean isFull()
    {
        return count==queue.length;
    }
    //判空
    public boolean isEmpty()
    {
        return count==0;
    }


    public static void main(String[] args) throws Exception{
        ArrayQueue queue = new ArrayQueue<Object>(3);
        for (int i=0; i<3; i++) {
            queue.offer(i);
        }

        for (int i=0; i<4; i++) {
            System.out.print(queue.poll());
        }
        // 输出: 012null
    }
}

基于链表实现队列

public class LinkedListQueue {
    class Node{
        public Object data;
        public Node next;

        public Node(Object data) {
            this.data = data;
        }
    }

    private Node head;
    private Node tail;

    public LinkedListQueue() {
        this.head = null;
        this.tail = null;
    }

    public void offer(Object data) {
        Node node = new Node(data);
        if (tail != null) {
            tail.next = node;
        }
        tail = node;
        if (head == null) {
            head = tail;
        }
    }

    public Object poll() throws Exception {

        if (head != null) {
            Object data = head.data;
            head = head.next;
            return data;
        } else {
            return null;
        }
    }

    public static void main(String[] args) throws Exception{
        LinkedListQueue queue = new LinkedListQueue();
        for (int i=0; i<3; i++) {
            queue.offer(i);
        }

        for (int i=0; i<4; i++) {
            System.out.print(queue.poll());
        }
        // 输出：012null
    }
}