模拟实现队列（顺序队列和链式队列）

1.顺序队列

/**
 * 用数组模拟实现Queue
 * 采取浪费一个空间来区别满和空
 */
public class MySqQueue {
    private int[] elem;
    private int head;
    private int tail;

    public MySqQueue() {
        this.elem = new int[5];
    }

    //入队
    public boolean offer(int data) {
        if (full()) {
            System.out.println("队列已满");
            return false;
        }
        elem[tail] = data;
        tail = (tail + 1) % elem.length;
        return true;
    }

    //出队
    public int poll() {
        if (empty()) {
            throw new EmptyExeception("队列空！");
        }
        int res = elem[head];
        head = (head + 1) % elem.length;
        return res;
    }

    //获取队首元素
    public int head() {
        if (empty()) {
            throw  new EmptyExeception("队列空！");
        }
        return elem[head];
    }

    //获取队尾元素
    public int rear() {
        if (empty()) {
            throw  new EmptyExeception("队列空！");
        }
        int index = tail == 0 ? elem.length - 1 : tail - 1;
        return elem[index];
    }

    //判满
    public boolean full() {
        return ((tail + 1) % elem.length == head);
    }

    //判空
    public boolean empty() {
        return head == tail;
    }
}


//异常类
public class EmptyExeception extends RuntimeException{
    public EmptyExeception() {
    }

    public EmptyExeception(String message) {
        super(message);
    }
}

2.链式队列

**
 * 用单链表来实现queue
 */
public class MyQueue {
    private LinkNode head = null;
    private LinkNode tail = null;
    private int length = 0;

    private class LinkNode{
        private int val;
        private LinkNode next;

        public LinkNode(int val) {
            this.val = val;
        }
    }


    public MyQueue() {}

    //入队
    public int offer(int data){
        LinkNode node = new LinkNode(data);
        if(empty()){
            head = node;
            tail = node;
            length++;
            return data;
        }
        //尾部插入
        tail.next = node;
        tail = node;
        length++;
        return data;
    }

    //出队
    public int poll(){
        if(empty()){
            System.out.println("队列已经空！");
            return -1;
        }
        int res = head.val;
        //只有一个节点
        if(head.next == null){
            head = null;
            tail = null;
            length--;
            return res;
        }
        head = head.next;
        length--;
        return res;
    }

    //获取队头元素
    public int peek(){
        if(empty()){
            System.out.println("队列是空的！");
        }
        return head.val;
    }

    public int getLength(){
        return length;
    }

    public boolean empty(){
        return length == 0;
    }
}