数据结构:循环队列及其基本操作的实现

niushao 2020-01-10

/**
 * 循环队列 * 队列设置first指针直接指向队列头部元素,tail尾指针指向队列最后一个元素的后一个,即队列中总是预留一个空位
 */
class CircleQueue implements Queue<Integer>{

    private Integer[] queueArray = null;

    private int first;
    
    private int tail;

    private int maxSize;

    public CircleQueue(int max){
        this.maxSize=max+1;
        this.queueArray = new Integer[maxSize];
    }
    
    
    @Override
    public int size() {
        return (tail-first+maxSize)%maxSize;
    }

    @Override
    public boolean isEmpty() {
        return tail==first;
    }

    @Override
    public boolean contains(Object o) {
        Integer integer = (Integer)o;
        for (int i = first; i!=tail; i++) {
            if (i==queueArray.length){
                i=0;
            }
            if (integer.equals(queueArray[i])){
                return true;
            }
        }
        return false;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int temFirst = first;
            @Override
            public boolean hasNext() {
                return tail!=temFirst;
            }

            @Override
            public Integer next() {
                int num = queueArray[temFirst];
                temFirst = (temFirst+1)%maxSize;
                return num;
            }
        };
    }


    @Override
    public boolean add(Integer integer) {
        if ((tail+1)%maxSize==first){
            System.out.println("队列已满,无法添加");
            return false;
        }
        queueArray[tail]=integer;
        tail = (tail+1)%maxSize;
        return true;
    }


    @Override
    public Integer poll() {
        if(isEmpty()){
            throw new RuntimeException("队列为空");
        }
        int result = queueArray[first];
        first  = (first+1)%maxSize;
        return first;
    }

    @Override
    public Integer peek() {
        return queueArray[first];
    }
}

    public static void main(String[] args) {
        CircleQueue circleQueue = new CircleQueue(5);

        Scanner scanner = new Scanner(System.in);

        while (true){
            System.out.println("1:添加元素");
            System.out.println("2:取出元素");
            System.out.println("3:查看头元素");
            System.out.println("4:遍历队列");
            System.out.println("5:查看元素数量");
            System.out.println("6:是否为空");
            int commend = scanner.nextInt();
            switch (commend){
                case 1:{
                    System.out.println("请输出一个元素");
                    int num = scanner.nextInt();
                    circleQueue.add(num);
                    break;
                }
                case 2:{
                    System.out.println(circleQueue.poll());
                    break;
                }
                case 3:{
                    System.out.println(circleQueue.peek());break;

                }
                case 4:{
                    for (Integer integer : circleQueue) {
                        System.out.printf("%d\t",integer);
                    }
                    System.out.println();
                    break;
                }
                case 5:{
                    System.out.println(circleQueue.size());break;

                }
                case 6:{
                    System.out.println(circleQueue.isEmpty());
                    break;
                }
            }
        }

    }
 
 

相关推荐