最新公告
  • 新注册用户请前往个人中心绑定邮箱以便接收相关凭证邮件!!!点击前往个人中心
  • 数据结构笔记总结(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)数组队列

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    参与讨论

    • 184会员总数(位)
    • 3737资源总数(个)
    • 0本周发布(个)
    • 0 今日发布(个)
    • 572稳定运行(天)

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

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级