数据结构与算法——队列

OldPanda 发布于2019-08-16 15:51 / 624人阅读

摘要：概述前面说完了栈，接下来再看看另一种很基础的数据结构，队列。很明显，队列的操作也是受限的，插入元素入队只能在队尾，删除元素出队只能在队头。这时候我们需要进行数据搬移，性能会受到影响，而循环队列解决了这个问题。

1. 概述

前面说完了栈，接下来再看看另一种很基础的数据结构，队列。顾名思义，队列跟我们现实生活中的排队很相似：例如我们在食堂排队打饭，先来的先打到，后来的只能一次排在后面，不允许插队。很明显，队列的操作也是受限的，插入元素（入队）只能在队尾，删除元素（出队）只能在队头。结合下面的图就很容易理解了：

2. 队列实现

和栈一样，队列也有两种实现方式，使用数组实现的队列叫做顺序队列，使用链表实现的队列叫做链式队列。这里我实现了链式队列，你也可以根据其思想使用数组来实现。

public class LinkedListQueue {
    
    private Node head;//队头节点指针
    private Node tail;//队尾节点指针
    private int size;//队列中元素个数

    public LinkedListQueue() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    //入队
    public boolean enqueue(String value) {
        Node node = new Node(value);
        if(tail == null) {
            head = tail = node;
            this.size ++;
            return true;
        }
        
        tail.next = node;
        tail = node;
        
        this.size ++;
        return true;
    }
    
    //出队列
    public String dequeue() {
        if(head == null) return null;//队列为空
        
        String result = head.getData();
        
        head = head.next;
        this.size --;
        return result;
    }
    
    //定义链表节点
    public static class Node{
        private String data;
        private Node next;

        public Node(String data) {
            this.data = data;
            this.next = null;
        }

        public String getData() {
            return data;
        }
    }
}

3. 循环队列

在使用数组实现队列的时候，会出现一个问题，就是随着队头和队尾指针的后移，就算数组中还有空间，也不能进行入队操作了。这时候我们需要进行数据搬移，性能会受到影响，而循环队列解决了这个问题。

循环队列就是将数组首尾相连，形成了一个环形：

如上图，当指针 tail 到达数组末尾的时候，并不进行数据搬移，而是直接将指针向前移，到达了 0 这个位置。在进行一次入队，就变成了下面的样子：

可以看到，循环队列判断空的条件是 head == tail，而怎么判断队列满呢？答案是（tail + 1）== head 的时候，队列就满了，不能看出循环队列实际上浪费了一个存储空间。下面我给出了循环队列的代码实现：

public class CircularQueue {

    private String[] items;
    private int size;
    private int head;
    private int tail;
    
    public CircularQueue(int capacity) {
        this.items = new String[capacity];
        this.size = 0;
        this.head = 0;
        this.tail = 0;
    }
    
    public CircularQueue() {
        this(16);
    }
    
    //入队列
    public boolean enqueue(String value) {
        if((tail + 1) % items.length == head) return false;//队列已满
        
        items[tail] = value;
        //head 和 tail 指针的移动不是简单的加减1了
        tail = (tail + 1) % items.length;
        this.size ++;
        
        return true;
    }

    //出队列
    public String dequeue() {
        if(head ==  tail) return null;//队列为空
        
        String result = items[head];
        head = (head + 1) % items.length;
        this.size --;
        
        return result;
    }
    
    //队列中元素个数
    public int size() {
        return size;
    }

    //打印队列中数据
    public void print() {
        int h = head;
        int t = tail;
        
        while(h != t) {
            System.out.print(items[h] + "  ");
            h = (h + 1) % items.length;
        }
        System.out.println();
    }
}

GPU云服务器云服务器算法与数据结构数据结构与算法数据结构与算法教程数据结构与算法答案

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73733.html

你与解决“缓存污染”只差这篇文章的距离

摘要：如果处理不得当，就会造成缓存污染问题。解决缓存污染的算法算法，英文名，字面意思就是最不经常使用的淘汰掉算法，是通过数据被访问的频率来判断一个数据的热点情况。分析降低了缓存污染带来的问题，命中率比要高。微信公众号：IT一刻钟大型现实非严肃主义现场一刻钟与你分享优质技术架构与见闻，做一个有剧情的程序员关注可第一时间了解更多精彩内容，定期有福利相送哟。 showImg(https://s...

shadowbook 2019-08-06 13:41 评论0 收藏0
学习数据结构与算法之栈与队列

摘要：于是翻出了机房里的这本学习数据结构与算法开始学习程序员的基础知识。这本书用了我最熟悉的来实现各种数据结构和算法，而且书很薄，可以说是一本不错的入门教程。队列在头部删除元素，尾部添加元素。本系列所有文章：第一篇文章：学习数据结构与算法之栈与队列第二篇文章：学习数据结构与算法之链表第三篇文章：学习数据结构与算法之集合第四篇文章：学习数据结构与算法之字典和散列表第五篇文章：学习数据结构与算...

pingan8787 2019-08-20 18:37 评论0 收藏0
学习JavaScript数据结构与算法（一）：栈与队列

摘要：之数组操作接下来就是数据结构的第一部分，栈。以字符串显示栈中所有内容方法的实现说明需要往栈中添加新元素，元素位置在队列的末尾。的前端乐园原文链接寒假前端学习学习数据结构与算法，栈与队列本系列的第一篇文章: 学习JavaScript数据结构与算法（一），栈与队列第二篇文章：学习JavaScript数据结构与算法（二）：链表第三篇文章：学习JavaScript数据结构与算法（三）：集合第...

Flink_China 2019-08-19 17:23 评论0 收藏0
每周一练之 数据结构与算法（Queue）

摘要：与堆栈区别队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。移除队列的第一项，并返回被移除的元素。三使用队列计算斐波那契数列的第项。前两项固定为，后面的项为前两项之和，依次向后。 showImg(https://segmentfault.com/img/remote/1460000019005270); 这是第二周的练习题，这里补充下咯，五一节马上就要到了，自己的...

anquan 2019-08-23 17:10 评论0 收藏0
Java数据结构与算法[原创]——队列

摘要：前言数据结构与算法专题会不定时更新，欢迎各位读者监督。队列和栈类似，也是一个遵循特殊规则约束的数据结构。将没有元素的队列称之为空队，往队列中插入元素的过程称之为入队，从队列中移除元素的过程称之为出队。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本文介绍数据结构中的队列（queue）的概念、存储结构、队列的特点...

韩冰 2019-08-19 10:43 评论0 收藏0
[ JavaScript ] 数据结构与算法 —— 队列

摘要：而且目前大部分编程语言的高级应用都会用到数据结构与算法以及设计模式。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。前言 JavaScript是当下最流行的编程语言之一，它可以做很多事情：数据可视化（D3.js，Three.js，Chart.js）; 移动端应用(React Native,Weex,AppCan,Flutter,Hybrid App,小程...

Yi_Zhi_Yu 2019-08-23 15:05 评论0 收藏0