队列数组实现-环形队列-创新互联

1.队列数组实现

队列：有序列表，可以用数组和链表实现，先进先出原则，

目前累计服务客户上千家，积累了丰富的产品开发及服务经验。以网站设计水平和技术实力，树立企业形象，为客户提供成都网站制作、成都做网站、外贸营销网站建设、网站策划、网页设计、网络营销、VI设计、网站改版、漏洞修补等服务。创新互联始终以务实、诚信为根本，不断创新和提高建站品质，通过对领先技术的掌握、对创意设计的研究、对客户形象的视觉传递、对应用系统的结合，为客户提供更好的一站式互联网解决方案，携手广大客户，共同发展进步。

尾部加数据（要判断队列是否满），队首取数据

1.front含义，指向队首数据的前一个位置;

front的初始值=-1

2.rear含义，指向队尾数据位置;

rear初始值=-1

3.队列满是rear == maxSize-1

4.队列空是front==rear

5.有效个数是rear-front

代码实现:

1.队列类

public class ArrayQueue {//        使用数组模拟队列
    private int maxSize;//数组的大容量
    private int front;//队列头
    private int rear;//队列尾
    private  int[] arr;//存放数据,模拟队列

    public ArrayQueue(int arrMaxSize) {this.maxSize=arrMaxSize;
        arr = new int[maxSize];
        front = -1;//指向队列头的前一个位置
        rear = -1;//指向队列尾的位置
    }

//    判断队列是否满
    public boolean isFull(){return rear==maxSize-1;
    }
//    判断队列是否为空
    public boolean isEmety(){return rear==front;
    }
//    添加数据到队列中
    public void addQueue(int ele){if (!isFull()){arr[++rear]=ele;
            return;
        }else {System.out.println("队列已满");
        }
    }
//    取出队列的数据
    public int getQueue(){if (isEmety()){throw new RuntimeException("没有数据，无法取出");
        }
        return arr[++front];
    }
//    获取队首数据，不取出
    public int headQueue(){if (isEmety()){throw new RuntimeException("没有数据，无法取出");
        }
        return arr[front+1];
    }
//     显示队列所有数据
    public void allQueue(){if (isEmety()){System.out.println("没有数据，无法取出");
            return;
        }
        for (int i = front+1; i< rear+1; i++) {System.out.println(arr[i]);
        }
    }
}

2.测试队列

public class ArrayQueueDemo {public static void main(String[] args) {ArrayQueue arrayQueue = new ArrayQueue(3);
        boolean flag = true;
        Scanner sc = new Scanner(System.in);
        while (flag){System.out.println("s(show):显示队列中的全部数据");
            System.out.println("h(head):获取队列中队首数据");
            System.out.println("a(add):向队列添加一个数据");
            System.out.println("g(get):取出队列中的一个元素");
            System.out.println("e(exit):退出程序");
            System.out.print("请输入操作:");
            char c = sc.next().charAt(0);
            switch (c){case 's':
                    arrayQueue.allQueue();
                    break;
                case 'h':
                    try {int i = arrayQueue.headQueue();
                        System.out.println("队首的数据是:"+i);
                    } catch (Exception e) {System.out.println(e.getMessage());
                    }
                    break;
                case 'a':
                    System.out.print("请输入要添加的数据:");
                    int add = sc.nextInt();
                    arrayQueue.addQueue(add);
                    break;
                case 'g':
                    try {int get = arrayQueue.getQueue();
                        System.out.println("取出的数据是:"+get);
                    } catch (Exception e) {System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    sc.close();
                    flag = false;
                    break;
                default:
                    System.out.println("输入错误");
                    break;
            }
        }
        System.out.println("程序退出！");
    }
}

3.问题分析:(环形队列可复用)

1.目前数组只能使用一次，没有达到复用的效果，将这个数组用一个算法，改进为环形队列(取模);

1.解决：使用数组模拟环形队列

1.front含义改变，由指向队首数据的前一个位置，变成队首数据位置

front的初始值=0

2.rear含义改变，由指向队尾数据位置，变成队尾数据的后一个位置

rear初始值=0

空出一个空间作为约定；

3.队列满是由rear == maxSize-1变成(rear+1)%maxSize==front;

4.队列空不改变，还是front==rear

5.有效个数是(rear+max-front)%max

public class CircleArrayQueue {private int[] arr;
    private int front;
    private int rear;
    private int maxSize;

    public CircleArrayQueue(int maxSize) {this.maxSize = maxSize;
        arr = new int[maxSize];
        front = 0;
        rear = 0;
    }
    public boolean isFull(){return (rear+1)%maxSize==front;
    }
    public boolean isEmepty(){return rear==front;
    }
    //队列添加元素
    public void addQueue(int ele){if (isFull()){System.out.println("队列满了，无法添加元素");
            return;
        }
        arr[rear]=ele;
        rear=(rear+1)%maxSize;
    }
    //取出队首元素
    public int getQueue(){if (isEmepty()){throw new RuntimeException("队列没有元素，无法取出数据");
        }
        int a =  arr[front];
        arr[front]=0;
        front = (front+1) % maxSize;
        return a;
    }

    //显示队首元素
    public int headQueue(){if (isEmepty()){throw new RuntimeException("队列没有元素，无法取出数据");
        }
        return arr[front];
    }

    //显示队列所有数据
    public void allQueue(){if (isEmepty()){System.out.println("没有数据");
            return;
        }

        int count = size();
        for (int i = front; i< front+count; i++) {System.out.println(arr[i%maxSize]);
        }
    }
    //有效数据个数
    public int size(){return (rear+maxSize-front)%maxSize;
    }
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享文章：队列数组实现-环形队列-创新互联
分享地址：http://shouzuofang.com/article/iieop.html