在现有循环队列实例下,如何使断言tail<front成立?

来源:3-7 循环队列的实现

慕前端8962423

2019-10-17

波波老师好,我这边按照课程上的思路,实现了循环队列的逻辑,传送门:LoopQueue

我的问题是,我们实现循环队列的前提是充分利用数组空间,也就是说,只有在循环队列里出现过tail<front的情况,循环队列才有它自己的意义,但是在测试过程当中发现,出于保证数组安全节约空间的考虑,会根据情况进行resize操作并随之重排tailfront,进而导致tail>=front,那么,在什么情况下才能出现tail<front使逻辑自洽呢?

单元测试代码表述如下:

    @Test
    public void test_tail_lt_front() throws NoSuchFieldException, IllegalAccessException {
        LoopQueue<Integer> queue = null;
        //TODO  begin
        // queue = new LoopQueue<>(?);
        // ...
        // ...
        // end
        Field tailField = LoopQueue.class.getDeclaredField("tail");
        tailField.setAccessible(true);
        int tail = (Integer) tailField.get(queue);
        Field frontField = LoopQueue.class.getDeclaredField("front");
        frontField.setAccessible(true);
        int front = (Integer) frontField.get(queue);
        Assert.assertTrue(tail < front);
    }
写回答

1回答

liuyubobobo

2019-10-17

我不确定我是不是正确理解了你的问题。我理解你的问题是,在什么情况下,循环队列中会出现 tai < front?


1)先将队列中填满元素

2)从队首取出任意多元素。

3)再向队列添加元素,因为之前队列满了,所以索引大的数组空间已经没有位置了,只能从索引 0 开始继续添加,此时,tail 就小于 front 了。


继续加油!:)

0
1
慕前端8962423
明白了,我的实现中,出队时是先resize的,所以出现不了。您是先出队并调整指针后resize的。
2019-10-17
共1条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

查看课程