MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » 数据结构与算法-行列

数据结构与算法-行列

www.MyException.Cn  网友分享于:2013-09-28  浏览:0次
数据结构与算法--队列

数据结构与算法--队列

队列如其名,就是一列元素。举个我们熟知的场景,火车站窗口购票,排队买票的人们就组成一个队列。先去的人排在前头,后去的站在队伍后面。买票的顺序也是队伍头的人买了离开后,才轮到下一个。什么?你为了先买票想在队伍前头插入,对不起不允许的,请排队。新来的只能站在队列末端,只是最后一个才离开。队列是一种只允许在一端插入,在另一端删除的数据结构。能进行数据插入的那端是队尾,进行数据删除的那端是队列头。显然队列是先进先出的(First In First Out),就是平常说的FIFO

队列也是一种线性表,可以用顺序存储或链式存储。先看使用数组实现的顺序存储。

队列的数组实现

撇开数组容量限制不谈,光是出列(删除队列头元素)就很费劲——删除a[0]处元素后将引起其后所有元素的移动,时间复杂度为O(n)。有没有办法降低到O(1)呢?

可能会想到:那我出列就出列,你后面的元素不要动嘛!这样会造成什么后果?前面的人走了留下了大片可用的空间,后面的元素占据着接近数组末尾的位置。如果数组最后一个位置被占用了,后面的元素不能插入进来了。这不合理嘛,明明前面还有那么多空!这就好比你上课迟到了,跑到教室门口发现教室后排都坐满了,但是教室第一二排还空着没人坐。你总不能和老师说:”老师,没位置了。“老师肯定会把你安排到前排去坐的。

我们可由此受到启发:出列后留下的空,由新来的去补上。这样就有可能a[0]处站的是队列的最后一个元素。这就意味着一旦到达末尾我们就又回到开头,这不就是循环结构嘛。所以这样的队列称为循环队列。队列尾可以存在于数组中的任何位置,所以我们需要使用一个标志物记住队列尾的所在位置,用last表示;同样,队列头也可以在数组中的任何位置,使用一个标志物记住队列头的所在位置,用first表示。

first和last的具体含义是什么呢?假如first是队列第一个元素的下标,last是队列最后一个元素的下标。那么当第一个元素入列后,first和last应该相同都为0,表示只有一个元素时,first和last指向同一个元素。所以刚开始还没元素入列时(空列),因为入列只涉及last的自增,last应初始化为-1,而first被初始化为0。

再看,队列满时满足什么条件?很明显当first和last所在位置相邻时,相邻什么意思?由于是循环队列,相当于把这个数组首尾相连,当last的下一位置刚好是first的时候(想象成循环结构,数组的最后一个位置的下一个位置就是数组的第一个位置),last与first之间已无空余空间,所以不能再插入元素,队列满了。看下图,这是last与first相邻的两种情况。

有可能last在first的前面,则last + 1 = first,而因为last + 1 < a.lebgth故有(last + 1) % length = last + 1;也有可能last在first的后面,last比first大了一圈,由于last + 1== a.length,则(last + 1) % a.length刚好等于0,与first值一样。两种情况可以用一个式子统一起来,只用判断以下条件即可:

(last + 1) % a.length == first

回到first和last的含义以及其初始值。first = 0, last = -1,由于在入列时肯定会先判断是否已满后才进行后续操作,就像下面一样:

if ((last + 1) % a.length == first) {
    throw new RuntimeException("已达到最大容量,不可再入列!");
    // 其他操作
}

这时要入列第一个元素时,我们发现last和first的值代入刚好满足这个条件。这就意味着,当last和first表达的是上述意思时,一个元素都不能入列!

所以换个理解方式咯。如果last表示的不是最后一个元素所在位置,而是最后一个元素位置的下一个位置。因为当第一个元素入列后,first指向数组下标0位置,last应该指向下标1的位置,所以空列时last初始化为0,first应该初始化为0。而当队列满时,条件也变成了last == first,表示两个指针相遇。这又回到了上面说的困境,在第一个元素想入列时,经判断满足条件,被告知不能入列!

有没有什么办法可以解决上面的困境呢?假设我们保持first表示第一个元素所在的位置,last表示最后一个元素位置的下一个位置。则空列时first = last = 0。而将判断满的条件改一下,改成(last + 1) % a.length == first,则可以在入列第一个元素时完美避开这个条件。相应地,付出的代价就是数组的空间没有使用完。即使队列满时,也还有一个空余空间,last就指向它。 任何时候last所在的位置都是空的,没有任何元素填充。

好了搞清楚last和first是啥了,也清楚了队列满时的条件,是时候放代码了。

package Chap4;

import java.util.Iterator;

public class ArrayQueue<Item> implements Iterable<Item> {

    private Item[] a;
    // 指向队列的第一个元素
    private int first; // 默认值0
    // 指向最后一个元素的下一位置
    private int last; // 默认值0

    public ArrayQueue(int maxsize) {
        if (maxsize <= 0) {
            maxsize = 512;
        }
        a = (Item[]) new Object[maxsize];
    }

    public ArrayQueue() {
        this(512);
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public int size() {
        /* 1. last > first时:长度应该是last -first
              而(last - first + a.length) % a.length
              即(last - first) % a.length + 0 = last -first

           2. last < first时:长度应该是last - first + a.length
              而(last - first + a.length) % a.length
              即last - first + a.length

           综上,统一使用下面的表达式
         */
        return (last - first + a.length) % a.length;
    }

    public void enqueue(Item item) {
        // 先判断是否已满,无论何时,即使满时,last所在都是空
        if ((last + 1) % a.length == first) {
            throw new RuntimeException("已达到最大容量,不可再入列!");
        }
        a[last] = item;
        // 当新元素入列成占据数组最后一个位置时,last应该变成0(循环结构,数组最后一个位置的下一个位置就是数组的第一个位置);其余情况保持自增
        last = (last + 1) % a.length;
    }

    public Item dequeue() {
        Item item = a[first];
        // 既然弹出,此处应变成null
        a[first] = null;
        // first的更新和last一样的
        first = (first + 1) % a.length;
        return item;
    }
    // 获得队头元素
    public Item getHead() {
        return a[first];
    }

    // 清空相当于初始化到原来的样子
    public void clear() {
        for (int i = 0; i < a.length; i++) {
            a[i] = null;
        }
        first = 0;
        last = 0;
    }

    @Override
    public Iterator<Item> iterator() {
        return new Iterator<Item>() {
            private int current = first;

            @Override
            public boolean hasNext() {
                // 1. 空队列时(first = last = 0)
                // 2. first在last前一个位置,刚好访问了最后一个元素。之后和last相等时结束遍历
                return current != last;
            }

            @Override
            public Item next() {
                Item item = a[current];
                current = (current + 1) % a.length;
                return item;
            }
        };
    }

    @Override
    public String toString() {
        Iterator<Item> it = iterator();
        if (!it.hasNext()) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder();
        sb.append("[");

        while (true) {
            Item item = it.next();
            sb.append(item);
            if (!it.hasNext()) {
                return sb.append("]").toString();
            }
            sb.append(", ");
        }
    }

    public static void main(String[] args) {
        ArrayQueue<String> a = new ArrayQueue<>();
        a.enqueue("a");
        a.enqueue("b");
        a.enqueue("c");
        a.enqueue("d");
        System.out.println(a);
        a.dequeue(); // a
        a.dequeue(); // b
        for (String each: a) {
            System.out.print(each+" "); // c d
        }
        a.clear();
        System.out.println("\n"+a.isEmpty()); // true
        a.enqueue("tiger");
        a.enqueue("lion");
        System.out.println("head: "+a.getHead()); // tiger
    }
}

相信经过上面的讲解,enqueuedequeue方法理解起来都不太难了,需要注意的是last和first的更新方式,注释里说明了当新元素入列成占据数组最后一个位置时,last应该变成0(循环结构,数组最后一个位置的下一个位置就是数组的第一个位置);其余情况保持自增。用一句last = (last + 1) % a.length统一的这两种情况。同理在dequeue方法中first的更新方式和last一样。

然后是iteratorhasNext方法的判断,从first开始遍历,不断自增,只要first还不等于last,说明还没遍历完,当first在last前一个位置,刚好访问到了最后一个元素,之后和last相等,结束遍历。

最后看看如何队列的长度,由于使用了两个指针,本着节约内存的考虑,就不再新增一个变量专门保存队列的长度了。画画图可以轻松看出。

情况1长度就一段即last - first ;情况2长度有两段,一段长度为last,另一段长度是a.length - first,相加即是队列的长度。为了统一这两种情况,使用(last - first + a.length) % a.length就行了。至于为什么可以使用这个式子代替,图中给了解释,注意看。

队列的链表实现

用链表实现栈和队列都十分方便。代码都不用改的,把方法名从add改成enqueue,pop改成dequeue就行了。

package Chap4;

import java.util.Iterator;

public class MyQueue<Item> implements Iterable<Item> {

    private class Node {
        Item data;
        Node next;
    }

    // 指向第一个节点
    private Node first;
    // 指向最后一个节点
    private Node last;
    private int N;

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }



    // 入列,表尾加入元素
    public void enqueue(Item item) {
        Node oldlast = last;
        last = new Node();
        last.data = item;
        // last应该指向null,但是新的结点next默认就是null
        // 如果是第一个元素,则last和first指向同一个,即第一个
        if (isEmpty()) {
            first = last;
        } else {
            oldlast.next = last;
        }
        N++;
    }

    // 出列,即删除表头元素
    public Item dequeue() {
        Item item = first.data;
        Node next = first.next;
        // 这两行有助于垃圾回收
        first.data = null;
        first.next = null;
        first = next;
        N--;
        // 最后一个元素被删除,first自然为空了,但是last需要置空。
        // 注意是先减再判断是否为空
        if (isEmpty()) {
            last = null;
        }
        return item;
    }
    public Item getHead() {
        return first.data;
    }

    public void clear() {
        while (first != null) {
            Node next = first.next;
            // 下面两行帮助垃圾回收
            first.next = null;
            first.data = null;
            first = next;
        }
        // 所有元素都空时,last也没有有所指了。记得last置空
        last = null;
        N = 0;
    }

    @Override
    public Iterator<Item> iterator() {
        return new Iterator<Item>() {
            private Node current = first;

            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public Item next() {
                Item item = current.data;
                current = current.next;
                return item;
            }
        };
    }

    @Override
    public String toString() {
        Iterator<Item> it = iterator();

        if (!it.hasNext()) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while (true) {
            Item item = it.next();
            sb.append(item);
            if (!it.hasNext()) {
                return sb.append("]").toString();
            }

            sb.append(", ");
        }
    }

    public static void main(String[] args) {
        MyQueue<Integer> a = new MyQueue<>();
        a.enqueue(1);
        a.enqueue(2);
        a.enqueue(3);
        a.enqueue(4);
        System.out.println(a);
        a.dequeue();
        a.dequeue();
        System.out.println(a); // [3, 4]
        a.clear();
        System.out.println(a.size()); // 0
        a.enqueue(999);
        a.enqueue(777);
        System.out.println(a.getHead()); // 999
    }
}

代码比较简单,而且在实现单链表的时候已经说得比较详细了,这里就不再赘述。

比较循环队列和链表实现的队列,入列出列的时间复杂度都是O(1),不过循环队列有长度的限制,适合实现知道数据量的情况。链表实现的队列虽然有指针域Node会产生一些内存开销,不过总的来说可以接受,而且没有队列长度的限制。


by @sunhaiyu

2017.8.18

文章评论

如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
代码女神横空出世
代码女神横空出世
程序员和编码员之间的区别
程序员和编码员之间的区别
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
总结2014中国互联网十大段子
总结2014中国互联网十大段子
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
Java程序员必看电影
Java程序员必看电影
漫画:程序员的工作
漫画:程序员的工作
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
一个程序员的时间管理
一个程序员的时间管理
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员的鄙视链
程序员的鄙视链
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
程序员必看的十大电影
程序员必看的十大电影
我的丈夫是个程序员
我的丈夫是个程序员
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
那些争议最大的编程观点
那些争议最大的编程观点
如何成为一名黑客
如何成为一名黑客
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
中美印日四国程序员比较
中美印日四国程序员比较
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
每天工作4小时的程序员
每天工作4小时的程序员
老程序员的下场
老程序员的下场
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
程序员都该阅读的书
程序员都该阅读的书
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
我是如何打败拖延症的
我是如何打败拖延症的
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
鲜为人知的编程真相
鲜为人知的编程真相
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
 程序员的样子
程序员的样子
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
编程语言是女人
编程语言是女人
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有