Java实现顺序队列

什么是队列具体实现

核心代码

IQueue.classSqQueue.class 测试

测试代码测试结果

我们之前说的栈是一种先进后出的数据结构，而队列呢是先进先出数据结构。
也就是说，先放进去的元素，先拿出来。而放进去元素的操作叫做入队，拿出的元素操作我们称之为出队。
日常生活中最简单的栗子就是–排队做核酸。做核酸应该是先来排队的先做对不对，不可能你后来的先做吧。
PS：排队有风险，插队需谨慎。

队列接口

public interface IQueue {
    //置空
    public void clear();
    //判空
    public boolean isEmpty();
    //队列长度
    public int length();
    //取队首元素
    public Object peek() throws Exception;
    //入队
    public void offer(Object o) throws Exception;
    //出队
    public Object poll();
}

具体实现

public class SqQueue implements IQueue {
    private Object[] queueElem;
    private int front;//指向队首 有元素
    private int rear; //指向队尾 没有元素

    //初始化
    public SqQueue(int maxSize) {
        queueElem = new Object[maxSize];
        front = rear =0;
    }

    @Override
    public void clear() {
        front = rear = 0;
    }

    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    @Override
    public int length() {
        //要考虑rear < front 这种情况
        return (rear - front + queueElem.length)%queueElem.length;
    }

    //取出元素前需要判空
    @Override
    public Object peek() throws Exception {
        if(rear == front)
            return null;
        else
            return queueElem[front];
    }

    //入队
    @Override
    public void offer(Object o) throws Exception {
        if((rear + 1) % queueElem.length == front)
            System.out.println("队列已满。");
        else {
            //存入元素
            queueElem[rear] = o;
            //rear指向下一个存储位置
            rear = (rear + 1) % queueElem.length;
        }
    }

    //出队
    @Override
    public Object poll() {
        if(rear == front)
            return null;
        else {
            //取出元素
            Object o = queueElem[front];
            //front前移
            front = (front + 1) % queueElem.length;
            return o;
        }
    }

    //遍历输出所有元素
    public void display() {
        if(!isEmpty()) {
            //取余到队尾
            for(int i = front; i != rear; i = (i + 1) % queueElem.length) {
                System.out.print(queueElem[i].toString() + " ");
            }
        }else {
            System.out.println("队列为空。");
        }
    }

}

public class QueueTest {
    public static void main(String[] args) throws Exception {
        SqQueue sqQueue = new SqQueue(5);
        sqQueue.offer("零");
        sqQueue.offer("一");
        sqQueue.offer("二");
        sqQueue.offer("三");
        sqQueue.offer("四");//rear为保留位置 不能存放元素
        sqQueue.display();
        System.out.println();
        System.out.println("队首元素为：" + sqQueue.peek());
        System.out.println("出队元素为：" + sqQueue.poll());
        System.out.println("出队操作后的队列元素为：");
        sqQueue.display();
        System.out.println();
        System.out.println("队列长度为：" + sqQueue.length());
        sqQueue.offer("四");//由于出队了一个元素 此时front = 1 rear 可以指向0 故而可以存入元素
        sqQueue.display();
        System.out.println();
        System.out.println("队列长度为：" + sqQueue.length());
    }
}

队列已满。
零 一 二 三 
队首元素为：零
出队元素为：零
出队操作后的队列元素为：
一 二 三 
队列长度为：3
一 二 三 四 
队列长度为：4