您当前的位置: 首页 >  Java

Kevin-Dev

暂无认证

  • 0浏览

    0关注

    544博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

【Java -- 数据结构】什么是队列(Queue)?

Kevin-Dev 发布时间:2021-03-13 15:54:15 ,浏览量:0

前言

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。先进先出,简单暴力的理解就是吃进去拉出来

优点:

  • 提供了先进先出的存取方式

缺点:

  • 存取其他项很慢

在这里插入图片描述 队列有两个最基本的操作,入队enqueue(),放一个数据到队列的尾部;出队dequeue(),从队列头部取出一个元素。

顺序队列和链式队列

队列可以使用数组来实现也可以使用链表来实现,用数组实队列的栈叫做顺序队列,用链表实现的队列叫做链式队列。

使用数组来实现一个队列:
public class ArrayQueue {
    private String[] items;
    private int n = 0;//总大小
    private int head = 0;
    private int tail = 0;

    //申请一个大小为n的数组
    public ArrayQueue(int n) {
        this.items = new String[n];
        this.n = n;
    }

    //入队
    public boolean enqueue(String item){
        //如果队列满了返回false
        if(tail == n) return false;
        items[tail] = item;
        ++tail;
        return true;
    }

    //出队
    public String dequeue(){
        //head == tail 表示队列为空
        if(head == tail) return  null;
        String res = items[head];
        ++head;
        return res;
    }

}

队列需要两个指针,一个指向队头,一个指向队尾。

在这里插入图片描述 当a、b、c、d一次进入队列之后,队列中的head指针指向下标为0的位置,tail下标为4的位置 当我们调用两次出队操作的之后,队列中的head指针指向下标为2的位置,tail指针位置不变。

随着不停的入队和出队操作,head和tail指针会不断的往后移动移动到最右边,即使数组中还有空闲的空间也不能往队列中添加数据了,那怎么办呢?

我们可以使用数据搬移,当然出队的时候不会出现空间不够的情况也就不用搬移,我们只需要在入队的时候集中触发一次数据搬移即可。根据这个思想,上面的出队操作不用变,入队操作可以改成下面的:

    public boolean enqueue(String item){
        //tail==n 说明队列满了
        if(tail == n){
            //tail==n&&head==0说明整个队列都是满的
            if(head == 0) return  false;
            //搬移数据
            for (int i = head; i             
关注
打赏
1658837700
查看更多评论
0.1120s