线性表，栈，队列。

Java中，线性表分为数组构造的ArrayList和双向链表构造的LinkedList。

两者区别，对于取值ArrayList较快，插入删除LinkedList较快。这是因为ArrayList取值直接通过下标就可以取到，而LinkedList需要判断下标靠近前段还是后段，然后决定从前段扫还是后段扫。插入删除对于ArrayListl来说，如果是在本身已经在数组中的元素的话，需要移动它前后的元素。如果是不在数组中的元素，还需要判断它是否越界，是否重新开括一个更大的数组。而对于LinkedList来说，只需要扫到它要插入删除的位置进行操作就可以了，不需要担心大小问题。

源码如下:public class MyArrayList<T> implements Iterable<T>{

   private T []mNums;

   private int mSize;

   private static final int DEFAULT_CAPACITY =10;

   public boolean isEmpty() {

return mSize==0 ;

}

   public void clear() {

mSize = 0;

ensureCapacity(DEFAULT_CAPACITY);

}

   public void trimToSize() {

ensureCapacity(size());

}

   public int size() {

return mSize;

}

   public T get(int idx) {

  try{

if(idx>=size()||idx<0)

throw new ArrayIndexOutOfBoundsException();

  }

  catch (ArrayIndexOutOfBoundsException e) {

  e.printStackTrace();

}

  return mNums[idx];

}

   public void set(T element,int idx) {

  try{

if(idx>=size()||idx<0)

throw new ArrayIndexOutOfBoundsException();

  }

  catch (ArrayIndexOutOfBoundsException e) {

  e.printStackTrace();

}

  mNums[idx]=element;

}

   public void add(T element) {

add(size(),element);

}

   public void add(int idx,T element) {

  try{

if(idx>size()||idx<0)

throw new ArrayIndexOutOfBoundsException();

  }

  catch (ArrayIndexOutOfBoundsException e) {

  e.printStackTrace();

}

  if(mNums.length==size())

  {

  ensureCapacity(size()*2+1);

  }

  for(int i=mSize;i>idx;i--)

  {

  mNums[i]=mNums[i-1];

  }

  mSize++;

}

   

   public MyArrayList() {

}

   public T remove(int idx) {

  try{

  if(idx>size()||idx<0)

throw new ArrayIndexOutOfBoundsException();

  }

  catch (ArrayIndexOutOfBoundsException e) {

  e.printStackTrace();

}

T removeItem = mNums[idx];

for(int i=idx;i<size();i++)

{

mNums[i]=mNums[i+1];

}

mSize--;

return removeItem;

}

public void ensureCapacity(int newCapacity) {

if(newCapacity<mSize)

return;

T[] old = mNums;

mNums = (T[]) new Object[newCapacity];

for(int i=0;i<old.length;i++)

{

mNums[i]=old[i];

}

}

@Override

public Iterator<T> iterator() {

// TODO Auto-generated method stub

return null;

}

 private class ArrayListIterator implements Iterator<T>{

   private int current=0;

@Override

public boolean hasNext() {

return current<mSize;

}

@Override

public T next() {

if(!hasNext())

throw new NoSuchElementException();

return mNums[current++];

}

public void remove() {

MyArrayList.this.remove(--current);

}

}

public class MyLinkedList<T> implements Iterable<T>{

private Node<T>begainMarker;

private Node<T>endMarker;

private int mSize=0;

private int modCount=0;

public MyLinkedList() {

     clear();

}

 public void clear() {

   begainMarker = new Node<T>(null,null,null);

   endMarker = new Node<T>(null,null,null);

   begainMarker.next = endMarker;

   mSize = 0;

   modCount ++;

}

 public int  size() {

return mSize;

}

 public boolean isEmpty()

 {

return size()==0;

 }

 public void add(T t) {

add(size(),t);

}

 public void  add(int idx, T t) {

Node node = getNode( idx);

Node<T>newNode = new Node<T>(t,node.prev,node);

node.prev.next= newNode;

node.prev = newNode;

}

 public T get(int index) {

return (T) getNode(index).data;

}

 public T set(int idx,T t)

 {

Node<T>pNode=getNode(idx);

T old = pNode.data;

pNode.data = t;

return old;

 }

public Node getNode(int idx) {

Node<T>pNode;

if(idx<0||idx>size())

{

throw new IndexOutOfBoundsException();

}

if(idx<size()/2)

{

pNode = begainMarker.next;

for(int i=0;i<idx;i++)

{

pNode = pNode.next;

}

}

else{

pNode = endMarker.prev;

for(int i=size();i>idx;i--)

{

pNode = pNode.prev;

}

}

return pNode;

}

public void remove(Node<T> pNode) {

pNode.next.prev=pNode.prev;

pNode.prev.next=pNode.next;

mSize--;

modCount++;

}

private static class Node<T> {

public Node(T t,Node<T> p,Node<T> n) {

data = t;

prev = p;

next = n;

}

public T data;

public Node<T> prev;

public Node<T> next;

}

@Override

public Iterator<T> iterator() {

return new LinkedListIterator();

}

private class LinkedListIterator implements Iterator<T> {

       private Node<T> current = begainMarker.next;

       private int expectedModCount = modCount;

       private boolean okToRemove = false;

@Override

public boolean hasNext() {

return current!=endMarker;

}

@Override

public T next() {

if(modCount!=expectedModCount)

throw new ConcurrentModificationException();

if(!hasNext())

throw new NoSuchElementException();

T t = current.data;

current =current.next;

okToRemove = true;

return t;

}

public void  remove() {

if(modCount != expectedModCount)

throw new ConcurrentModificationException();

if(!okToRemove)

throw new IllegalStateException();

MyLinkedList.this.remove(current.prev);

okToRemove = false;

expectedModCount++;

}

}

}

栈是先进后出，递归函数就是栈形式调用函数。它的应用具体有四则运算，把中缀表达式转换成后缀表达式，再用后缀表达式计算四则运算。中缀转后缀是为了优先级高的运算放在前面。

栈实现方式，数组实现，一个栈顶索引。

中缀转后缀流程:

遍历表达式

遇到操作符号，看栈顶元素是否是优先级比他低或相同的符号，如果是，就把操作符号添加到输出数组中。不是(或者栈顶元素没有)就入栈。遇到操作数直接放入输出数组。遇到左括号压入栈中，遇到右括号再把左括号上的都添加到输出数组。当表达式遍历完成，再把栈内元素添加到输出数组。这样中缀就转成了后缀。

后缀计算四则表达式流程

遇到操作数，就入栈，遇到操作符号就计算两个操作数，结果再入栈。一直重复上述过程，直至遍历后缀表达式完成。

队列是先进先出。两个前后索引，表明数组中队列所占的大小。队列大小可以通过前后索引之差隐式算出。也可以通过一个值保存。