本文介绍数据结构中常用的表、栈和队列。以及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：
- get(int index) is O(n/4) average
- add(E element) is O(1)
- add(int index, E element) is O(n/4) average, but O(1) when index = 0 <— main benefit of LinkedList
- remove(int index) is O(n/4) average
- Iterator.remove() is O(1) <— main benefit of LinkedList
- 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：
- get(int index) is O(1) <— main benefit of ArrayList
- add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
- add(int index, E element) is O(n/2) average
- remove(int index) is O(n/2) average
- Iterator.remove() is O(n/2) average
- 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.判断回文。所谓回文就是一个字符序列以中间字符基准两边字符完全相同。解决方法可以将字符逐个分别放入队列和栈中，依次弹出，看是否相等，如果全部相等则是回文。
相关文章