• 推荐!搬瓦工官方代理,自动更换被封IPJust My Socks

ad

数据结构中的表、栈和队列

本文介绍数据结构中常用的表、栈和队列。以及Java中ArraryList与LinkedList的区别与选择,栈与队列的概念以及栈的应用以及队列的应用。

 

数据结构中的表

Java中增强的for循环

List<? extends Integer> l = ...
for (float i : l) {
    ...
}
same as:(编译器使用迭代器进行改写)
for (Iterator<Integer> i = l.iterator(); i.hasNext();) {
    float i0 = (Integer)i.next();
}

这段代码对于任何实现了Iterable接口的对象都可以起作用。

而对于数组:

T[] a = Expression;
L1: L2: ... Lm:
for (int i = 0; i < a.length; i++) {
    {VariableModifier} TargetType Identifier = a[i];
    Statement
}

参考:http://docs.oracle.com/javase/specs/jls/se8/html/jls-14.html#jls-14.14.2

 

关于ArrayList和LinkedList的选择

ArrayList底层是用数组实现的,LinkedList则是用双向列表。ArrayList的查找和修改修很快(get和set),都是常数时间(直接修改数组对应索引的值即可),但是都说LinkedList的插入和删除很快,的确,如果是知道结点的位置,插入和删除确实很快,常数时间就可以。但是,在插入前,如果需要先遍历找到结点,这是一个跟N有关的操作。源码中是node(inde index)方法,它是首先判断index的与中间位置的关系,在前半段就通过头结点来进行查找,在后半段就通过尾结点进行查找,确实比ArrayList移动数据快,但也不是常数时间的操作。具体可以查看stackoverflow上的问题:when-to-use-linkedlist-over-arraylist

总结如下:

对于LinkedList:

  1. get(int index) is O(n/4) average
  2. add(E element) is O(1)
  3. add(int index, E element) is O(n/4) average, but O(1) when index = 0 <— main benefit of LinkedList
  4. remove(int index) is O(n/4) average
  5. Iterator.remove() is O(1) <— main benefit of LinkedList
  6. ListIterator.add(E element) is O(1) <— main benefit of LinkedList

Note: O(n/4) is average, O(1) best case (e.g. index = 0), O(n/2) worst case (middle of list)

对于ArraryList:

  1. get(int index) is O(1) <— main benefit of ArrayList
  2. add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
  3. add(int index, E element) is O(n/2) average
  4. remove(int index) is O(n/2) average
  5. Iterator.remove() is O(n/2) average
  6. ListIterator.add(E element) is O(n/2) average

Note: O(n/2) is average, O(1) best case (end of list), O(n) worst case (start of list)

 

关于ArrayList和LinkedList,修改list立马抛出异常

AbstactList中有一个int值modCount,对它的注释是:

* The number of times this list has been <i>structurally modified</i>.
* Structural modifications are those that change the size of the
* list, or otherwise perturb it in such a fashion that iterations in
* progress may yield incorrect results.

可以看到这个值的作用就是记录那些对list的尺寸(大小)有了改动或者对list内部进行了改动导致iterations不能正确执行的修改次数,而在ArrayList和LinkedList的clear()、add()、remove()、sort()等对这个值都进行了modCount++,在Iterator中的next()方法中,会首先执行checkForComodification()方法:

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

所以只要修改了list,立马就会抛出异常。

 

Java中的ArrayList

transient Object[] elementData; // non-private to simplify nested class access
private int size;

一个是放数据的数组,一个是代表当前数据数量的整型。

再贴几个常用的方法的具体实现:

//因此是常数级(添加在末端)
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        /* 
        * Copies an array from the specified source array, beginning at the
        * specified position, to the specified position of the destination array.
        * @param      src      the source array.
        * @param      srcPos   starting position in the source array.
        * @param      dest     the destination array.
        * @param      destPos  starting position in the destination data.
        * @param      length   the number of array elements to be copied.
        public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);
        */
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);//一个native方法
        elementData[index] = element;
        size++;
    }
    
    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
    
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }
    
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
    
    //可以看到是remove掉第一个符合条件的数据
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

 

Java中的LinkedList

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

用到的数据结构,可以看到其实是一个双向链表。

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

分别代表头指针和尾指针。

贴一下常用方法的实现:

/**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

    /**
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
    /**
     * Returns the (non-null) Node at the specified element index.
     */
    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    /**
     * Unlinks non-null node x.
     */
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }
    
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }
    
    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

LinkedList还提供了快速获取头尾结点,或者是remove头尾结点的方法。removeFirst、removeLast、getFirst、getLast、addFirst、addLast。。。等等,源码不难,理解了这几点,都可以看懂。

 

数据结构中的

所谓栈,就是一种LIFO(last-in-first-out)表,在Java中是通过继承Vector实现的,主要添加了几个操作让它成为一个栈:

/**
     * Pushes an item onto the top of this stack. This has exactly
     * the same effect as:
     * <blockquote><pre>
     * addElement(item)</pre></blockquote>
     *
     * @param   item   the item to be pushed onto this stack.
     * @return  the <code>item</code> argument.
     * @see     java.util.Vector#addElement
     */
    public E push(E item) {
        addElement(item);

        return item;
    }
    
    /**
     * Removes the object at the top of this stack and returns that
     * object as the value of this function.
     *
     * @return  The object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }
    
    /**
     * Looks at the object at the top of this stack without removing it
     * from the stack.
     *
     * @return  the object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

可以看到所有方法都是同步的(addElement()是同步的),方法的实现也都是用的Vector里的方法(好像Vector是是JDK1.0的遗留产物了,是不是不推荐用了?而且继承Vector,那不是很多跟栈不相关的方法也都可以访问到?)。

 

栈的应用

1.平衡符号
就是判断左右括号是否可以闭合:

做一个空栈。读入字符直到文件结尾。如果字符是一个开放符号(左边),则将其推入栈中。如果字符是一个封闭符号,则当栈空是报错。否则,将栈元素弹出。如果弹出的符号不是对应的开放符号,则报错。在文件结尾,如果栈非空则报错。

2.后缀表达式
即逆波兰表示法,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

解算方法:
即逆波兰表示法,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

3.中缀到后缀的转换
所谓中缀,就是我们正常时候的表达式,转换方式也可以借助栈来实现:

从左到右遍历中缀表达式的每个操作数和操作符。当读到操作数时,立即把它输出,即成为后缀表达式的一部分;若读到操作符,判断该符号与栈顶符号的优先级,若该符号优先级高于栈顶元素,则将该操作符入栈,否则把栈中运算符弹出并加到后缀表达式尾端,直到遇到优先级低于该操作符的栈元素,然后把该操作符压入栈中。如果遇到”(”,直接压入栈中,除非正在处理“)”否则“(”不会从栈中弹出,如果遇到一个”)”,那么就将直到“(”的所有栈元素弹出并加到后缀表达式尾端,但左右括号并不输出。最后,如果读到中缀表达式的尾端,将栈元素依次完全弹出并加到后缀表达式尾端。

例如a+b*c+(d*e+f)*g 可以转成 abc*+de*f+g*+; 1 + (( 2 + 3)* 4 ) – 5可以转成123+4*+5-

4.方法调用

递归就是不停的将方法压到方法栈中,到达结束条件再一个个弹出来。

 

数据结构中的队列

所谓队列就是FIFO(first-in-first-out)的表,Java中的LinkedList实现了Queue,可以用Queue接口来窄化LinkedList的方法,Queue queue = new LinkedList(),这样就只能访问Queue中的方法。主要有以下几个方法:

public interface Queue<E> extends Collection<E> {
    /**
     * Inserts the specified element into this queue if it is possible to do so
     * immediately without violating capacity restrictions, returning
     * {@code true} upon success and throwing an {@code IllegalStateException}
     * if no space is currently available.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws IllegalStateException if the element cannot be added at this
     *         time due to capacity restrictions
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this queue
     * @throws NullPointerException if the specified element is null and
     *         this queue does not permit null elements
     * @throws IllegalArgumentException if some property of this element
     *         prevents it from being added to this queue
     */
    boolean add(E e);

    /**
     * Inserts the specified element into this queue if it is possible to do
     * so immediately without violating capacity restrictions.
     * When using a capacity-restricted queue, this method is generally
     * preferable to {@link #add}, which can fail to insert an element only
     * by throwing an exception.
     *
     * @param e the element to add
     * @return {@code true} if the element was added to this queue, else
     *         {@code false}
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this queue
     * @throws NullPointerException if the specified element is null and
     *         this queue does not permit null elements
     * @throws IllegalArgumentException if some property of this element
     *         prevents it from being added to this queue
     */
    boolean offer(E e);

    /**
     * Retrieves and removes the head of this queue.  This method differs
     * from {@link #poll poll} only in that it throws an exception if this
     * queue is empty.
     *
     * @return the head of this queue
     * @throws NoSuchElementException if this queue is empty
     */
    E remove();

    /**
     * Retrieves and removes the head of this queue,
     * or returns {@code null} if this queue is empty.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E poll();

    /**
     * Retrieves, but does not remove, the head of this queue.  This method
     * differs from {@link #peek peek} only in that it throws an exception
     * if this queue is empty.
     *
     * @return the head of this queue
     * @throws NoSuchElementException if this queue is empty
     */
    E element();

    /**
     * Retrieves, but does not remove, the head of this queue,
     * or returns {@code null} if this queue is empty.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E peek();
}

 

队列的应用

1.操作系统的各种数据缓冲区的先进先出管理,应用系统中的各种事件排队管理等等。

2.判断回文。所谓回文就是一个字符序列以中间字符基准两边字符完全相同。解决方法可以将字符逐个分别放入队列和栈中,依次弹出,看是否相等,如果全部相等则是回文。

点赞

相关文章