数据结构与算法(一)数组模拟环形队列

一、队列的基本认识

队列就是一个只允许在一端进行插入,在另一端进行删除操作的线性表。
队列是一种常用的数据结构之一,队列是“先进先出”。队列有队头(front)和队尾(rear),数据从队尾进入队列,从队头出队列,队头(front)指向队列的第一个数据,队尾(rear)指向队列中的最后一个数据。

二、我们简单实现下环形队列

package cn.fengpt.queue;


/**
 *数组模拟环形队列
 */
public class ArrayQueue {

    /**
     * 队头
     */
    private int front;
    /**
     * 最后一个元素的后一个位置
     */
    private int real;

    /**
     * 队的最大容量
     */

    private int maxSize;
    /**
     * 数据
     */
    private int []values=null;

    public ArrayQueue(int maxSize){
        this.maxSize=maxSize;
        this.values=new int[maxSize];
    }
    /**
     * 判断是否满了
     * @return
     */
    public boolean isFull(){
        return (real+1)%maxSize==front;
    }

    /**
     * 判断是否为空
     * @return
     */
    public boolean isEmpty(){
        return real==front;
    }

    /**
     * 入队
     * @param val
     */
    public void add(int val){
        if(isFull()){
            throw new RuntimeException(" 队列已满。。。。");
        }
        values[real]=val;
        real=(real+1)%maxSize;
    }

    /**
     * 出队
     * @return
     */
    public int getQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列为空....");
        }
        int val=values[front];
        front=(front+1)%maxSize;
        return val;
    }

    /**
     * 显示队头数据,不是取出数据
     * @return
     */
    public int headQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列为空。。。");
        }
        return values[front];
    }


    /**
     * 得到队列的有效个数
     * @return
     */
    public int size(){
        return (real + maxSize -front)%maxSize;
    }

    /**
     * 显示队列信息
     */
    public void show(){
        if (isEmpty()){
            throw new RuntimeException("队列为空....");
        }
        for (int i=front;i<front+size();i++){
            System.out.printf("values[%d]=%d \n",i%maxSize,values[i%maxSize]);
        }
    }

    public static void main(String[] args) {
        ArrayQueue queue=new ArrayQueue(3);
        queue.add(1);
        queue.add(2);
        queue.show();
        queue.getQueue();
        queue.add(3);
        queue.show();


    }

}

以上就是简单的实现环形队列。

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://www.fengpt.cn/archives/数据结构与算法一数组模拟环形队列