• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

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

极客笔记 Geekerstar 12个月前 (05-09) 412次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

队列(Queue)

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

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

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

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

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

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

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

综上可得:

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

队列的实现

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

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

代码演示

首先创建一个叫Queue的接口

public interface Queue<E> {

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

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

public class ArrayQueue<E> implements Queue<E> {

    private Array<E> 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<Integer> 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,以此类推……

数组队列的复杂度分析

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(2.4)数组队列
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00