数据结构笔记总结(2.4)数组队列

队列(Queue)

  • 队列也是一种线性结构
  • 相比数组,队列对应的操作是数组的子集
  • 只能从一端(队尾)添加元素,只能从另一端(队首)取出元素

接下来看一个演示,假设上图是一个队列,定义下面是队首,上面是队尾。

类比于我们去银行办事情,相应的就有一个柜台,排队到柜台办业务。

一旦来了个新的人,类比于数据结构中也就是来了一个新的元素。

新的元素就应该从队尾的位置进入队列,依次类推……

如果要出队,比如服务员已经办完了一个人的业务了,有空闲去办另一个人的业务。

这就需要从队列中取出一个元素,取出的这个元素就应该是队首的元素,也就是1。

综上可得:

  • 队列是一种先进先出的数据结构(先到先得)
  • Fist In First Out(FIFO)

队列的实现

类比于之前栈的实现,队列中主要实现这些方法,其实这些方法和栈是对应的,只不过换了一下数据结构名字叫法而已。

同理,我们实现队列也不用关心底层实现的,我们实现一个接口Queue,和之前的栈一样,复用array动态数组类来实现一个属于我们自己的arrayQueue。

代码演示

首先创建一个叫Queue的接口

public interface Queue {

    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();
}

再创建一个arrayQueue来实现Queue接口

public class ArrayQueue implements Queue {

    private Array array;

    public ArrayQueue(int capacity){
        array = new Array<>(capacity);
    }

    public ArrayQueue(){
        array = new Array<>();
    }

    @Override
    public int getSize(){
        return array.getSize();
    }

    @Override
    public boolean isEmpty(){
        return array.isEmpty();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public void enqueue(E e){
        array.addLast(e);
    }

    @Override
    public E dequeue(){
        return array.removeFirst();
    }

    @Override
    public E getFront(){
        return array.getFirst();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue: ");
        res.append("front [");
        for(int i = 0 ; i < array.getSize() ; i ++){
            res.append(array.get(i));
            if(i != array.getSize() - 1)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args) {

        ArrayQueue queue = new ArrayQueue<>();
        for(int i = 0 ; i < 10 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);
            if(i % 3 == 2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

运行程序,分析结果:

运行一下程序可以看到这样的结果,在开始的时候我们向队列中添加0,1,2三个元素。

队首是0,队尾是2,之后我们取出一个元素,取出0,队列只剩下1,2。

然后再添加三个元素3,4,5,队列变成1,2,3,4,5。

又取出一个元素,把1取出变成2,3,4,5,以此类推……

数组队列的复杂度分析

源码下载

[dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

导航目录

[dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(2.4)数组队列

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多