目录

目标

特点

代码实现

---

目标

• 熟悉队列的特点，能实现单项队列的核心部分。

---

特点

• 线性表，可以用数组或者链表实现；
• 数据先进先出。

---

代码实现

package com.ctx.data;

import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.NoSuchElementException;

/**
 * @describe 单向队列
 */
public class MyQueue<T> {
    //队列容量
    private int capacity;
    //数据
    private Object[] queue;
    //头部下标
    private int head;
    //尾部下标
    private int tail;
    //元素个数
    public int size;

    public MyQueue(int capacity, Class clazz) {
        this.capacity = capacity;
        queue = (T[]) Array.newInstance(clazz, capacity);
        head = 0;
        tail = 0;
        size = 0;
    }

    public boolean isEmpty() {
        if (queue == null || queue.length == 0 || size == 0) {
            return true;
        }
        return false;
    }

    private void resize(int newcapacity) {
        int a = -1;
        Object[] newQueue = new Object[newcapacity];
        for (int i = 0; i < queue.length; i++) {
            if (queue[i] != null) {
                newQueue[++a] = queue[i];
            }
        }
        tail = size == 0 ? 0 : size - 1;
        head = 0;
        queue = newQueue;
        capacity = newcapacity;
    }

    public T pop() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        int h = head;
        T result = (T) queue[h];
        queue[h] = null;
        head = h + 1;
        size = size - 1;
        return result;
    }

    public void push(T t) {
        //队列如果满了就扩容
        if (queue.length == tail + 1) {
            resize(queue.length * 2);
        }
        if (size == 0) {
            tail = 0;
            queue[0] = t;
        } else {
            queue[tail + 1] = t;
            tail = tail + 1;
        }
        size = size + 1;
    }

    public static void main(String[] args) {
        //参考队列：java.util.ArrayDeque
        MyQueue<String> myQueue = new MyQueue<>(3, java.lang.String.class);
        java.util.ArrayDeque q=new ArrayDeque(1);

        System.out.println("元素数量：" + myQueue.size);

        System.out.println("队列容量：" + myQueue.queue.length);

        myQueue.push("a");
        myQueue.push("b");
        myQueue.push("c");
        myQueue.push("d");
        myQueue.push("e");
        myQueue.push("f");

        System.out.println("队列容量：" + myQueue.queue.length);

        for (int i = 0; i < myQueue.size; i++) {
            System.out.println("==========拥有元素：" + myQueue.queue[i]);
        }
        System.out.println("出栈元素：" + myQueue.pop());
        System.out.println("出栈元素：" + myQueue.pop());
        System.out.println("出栈元素：" + myQueue.pop());

        myQueue.push("g");
        myQueue.push("h");
        myQueue.push("i");
        myQueue.push("j");
        myQueue.push("k");
        myQueue.push("l");
        System.out.println("元素数量：" + myQueue.size);

        for (int i = 0; i < myQueue.queue.length; i++) {
            System.out.println("==========拥有元素：" + myQueue.queue[i]);
        }

    }
}