一、栈的实现

栈的实现，有两个方法：一个是用java本身的集合类型Stack类型；另一个是借用LinkedList来间接实现Stack。

1.Stack实现

有关Stack的具体知识可以参考：http://www.cnblogs.com/skywang12345/p/3308852.html  

直接用Stack来实现非常方便，常用的api函数如下：

 

       boolean             isEmpty() // 判断当前栈是否为空
synchronized E             peek() //获得当前栈顶元素
synchronized E             pop() //获得当前栈顶元素并删除
             E             push(E object) //将元素加入栈顶
synchronized int           search(Object o)  //查找元素在栈中的位置，由栈低向栈顶方向数

2.LinkedList实现

LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。

LinkedList 实现 List 接口，能对它进行队列操作。

LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。

当LinkedList被当做栈来使用时，常用api及对应关系如下：

 

栈方法        等效方法
push(e)      addFirst(e)
pop()        removeFirst()
peek()       peekFirst()

	     isEmpty()  //判断是否为空

 

 

二、队列的实现

java中虽然有Queue接口，单java并没有给出具体的队列实现类，而Java中让LinkedList类实现了Queue接口，所以使用队列的时候，一般采用LinkedList。因为LinkedList是双向链表，可以很方便的实现队列的所有功能。

Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。 如果要使用前端而不移出该元素，使用

element()或者peek()方法。

 

java中定义队列 一般这样定义： Queue<E> queue = new LinkedList<E>();

当采用LinkedList来实现时，api的使用和对用关系如下：

 

队列方法       等效方法
offer(e)      offer(e)/offerLast(e)  //进队列，将元素加入队列末尾
poll()        poll()/pollFirst()  //获取队列头的元素并移除
peek()        peek()/peekFirst()  //获取队列头的元素

	      isEmpty() //判断是否为空

什么是线程栈
继续纠缠 Java 9 的新特性，仍然是一个边角料，即 Java 9 增加了对线程栈遍历的 API。那么什么是线程栈，JVM 在创建每一个线程的同时都会创建一个私有的虚拟机栈，每一桢代表着一个方法调用，每次方法的调用与退出意味着压栈与出栈。每一桢上有局部变量，操作数常量引用等信息，这也是为什么局部变量是能最快被销毁的对象。过深的栈(比如过多的递归调用) 会出现我们程序员赖以生存的 StackOverflow。
浅显些说，线程栈就是通常我们捕获到异常后，用 e.printStackTrace() 看到自 main 方法追溯到当前方法的调用。例如：
java.lang.RuntimeException: stack
    at cc.unmi.TestStackWalking.m2(TestStackWalking.java:15)
    at cc.unmi.TestStackWalking.m1(TestStackWalking.java:10)
    at cc.unmi.TestStackWalking.main(TestStackWalking.java:6)
调用层次是 main() 调用 m1(), m1() 调用 m2(), m2() 中的代码如下
try {
    throw new RuntimeException("stack");
} catch (Exception ex) {
    ex.printStackTrace();
}
上面输出的每一行就是一个栈桢，输出了当前类名，方法名，代码行号。 阅读全文 >>

欢迎转载，转载请注明出处：https://blog.csdn.net/u013547284/article/details/71158100

一、JAVA常用API

java.lang.Math

提供sin, cos, tan, exp, log, log10 等类方法，PI和E等类字段

java.lang.String（StringBuilder线程不安全，StringBuffer线程安全）

char charAt(int index)
			
返回给定位置的代码单元
		
boolean equals(Object other)

			boolean equalsIngoreCase(String other)
			
如果字符串与other相等，返回true

			忽略大小写
		
int length()
			
返回字符串的长度
		
String substring(int beginIndex)

			String substring(int beginIndex, int endIndex)
			
返回一个新字符串，包含原始字符串从beginIndex到串尾或到endIndex-1的所有代码单元
		
String toLowerCase()

			String toUpperCase()
			
返回小写字符串

			返回大写字符串
		
int indexOf(String str[, int fromIndex])

			int lastIndexOF(String str[, int fromIndex])
			
返回第一个/最后一个子串的位置,从起始位置或者fromIndex开始
		
java.util.Scanner

Scanner(InputStream in)

			Scanner(File f)

			Scanner(String data)
			
用给定的输入流创建一个Scanner对象

			例子：Scanner in = new Scanner(System.in)
		
String nextLine()
			
读取输入的下一行内容
		
String next()
			
读取输入的下一个单词（以空格作为间隔）
		
int nextInt()

			double nextDouble()
			
读取并转换下一个表示整数或浮点数的字符序列
		
for each循环

for(variable : collection) statement

collection这一集合表达式必须是一个数组或者是一个实现了Iterable接口的类对象

java.util.Arrays

static String toString(type[] a)
			
返回包含a中数据元素的字符串
		
static void sort(type[] a)
			
采用优化的快速排序算法对数组进行排序
		
static void binarySearch(type[] a, type v)
			
使用二分搜索算法查找值v
		
static Boolean equals(type[] a, type[] b)
			
如果两个数字相同，返回true
		
数组名.length

数组长度

java.util.Radom

Random()
			
构建一个新的随机数生成器
		
int nextInt(int n)
			
返回一个 0 ~ n-1之间的随机数
		
java.lang.Object

String toString()
			
返回描述该对象值的字符串。在自定义类中应覆盖这个方法
		
boolean equals(Object otherObject)
			
比较两个对象是否相等。在自定义类中应覆盖这个方法
		
Class getClass()

			int hashCode()
			
返回包含对象信息的类对象

			返回对象的散列码
		
static wait()

			static notify()

			static notifyAll()
			
 
		

java.lang.Class

String getName()
			
返回这个类的名字
		
static Class forName(String className)
			
返回描述类名为className的Class对象
		
Object newInstance()
			
返回这个类的一个新实例
		
Field[] getFields()

			Field[] getDeclareFields()
			
getFields()返回一个包含Field对象的数组，这些对象记录了这个类或其超类的公有域

			getDeclareFields()返回的Field对象记录了这个类的全部域
		
Method[] getMethods()

			Method[] getDeclareMethods()
			
getMethods()返回一个包含Method对象的数组，这些对象记录了这个类或其超类的公用方法

			getDeclareMethods()返回的Field对象记录了这个类的全部方法
		
Constructor[] getConstructors()

			Constructor[] getDeclareConstructors()
			
getConstructors()返回一个包含Constructor对象的数组，这些对象记录了这个类的公有构造器

			getDeclareConstructors()返回的Constructor对象记录了这个类的全部构造器
		
断言

assert 条件;

assert 条件:表达式;

二、JAVA集合框架

Java集合类库将接口和实现分离。当程序使用集合时，一旦构建了集合就不需要知道究竟使用了哪种实现。因此，只有在构建集合对象时，使用具体的类才有意义。可以使用接口类型存放集合的引用。利用这种方法，一旦改变想法，可以轻松使用另外一种不同的实现，只需在对象创建处修改即可。



java.util.Collection<E>

Iterator<E> iterator()
			
返回一个用于访问集合中每个元素的迭代器
		
int size()
			
返回当前存储在集合中的元素个数
		
boolean isEmpty()
			
如果集合中没有元素，返回true
		
boolean contains(Object obj)

			boolean containAll(Collection<? extend E> other)
			
如果集合中包含相等对象，返回true
		
boolean add(Object element)

			boolean addAll(Collection<? extend E> other)
			
将一个元素添加到集合中，集合改变返回true
		
boolean remove(Object element)

			boolean removeAll(Collection<?> other)
			
删除相等元素，成功删除返回true
		

java.util.Iterator<E>

boolean hasNext()
			
如果存在可访问的元素，返回true
		
E next()
			
返回将要访问的下一个对象
		
void remove()
			
删除上次访问的元素
		

Java库中具体集合

ArrayList
			
一种可以动态增长和缩减的索引序列
		
LinkedList
			
一种可以在任何位置进行高效插入和删除操作的有序序列
		
ArrayDeque
			
一种用循环数组实现的双端队列
		
HashSet
			
一种没有重复元素的无序集合
		
TreeSet
			
一种有序集
		
EnumSet
			
一种包含枚举类型值的集合
		
LinkedHashSet
			
一种可以记住元素插入次序的集
		
PriorityQueue
			
一种允许高效删除最小元素的集合
		
HashMap
			
一种存储键/值关联的数据结构
		
TreeMap
			
一种键值有序排列的映射表
		
EnumMap
			
一种键值属于枚举类型的映射表
		
LinkedHashMap
			
一种可以记住键/值项添加次序的映射表
		
WeakHashMap
			
一种其值无用武之地后可以被垃圾回收期回收的映射表
		
IdentityHashMap
			
一种用==而不是用equals比较键值的映射表
		
1、List

List接口扩展自Collection，它可以定义一个允许重复的有序集合，从List接口中的方法来看，List接口主要是增加了面向位置的操作，允许在指定位置上操作元素，同时增加了一个能够双向遍历线性表的新列表迭代器ListIterator。List接口有动态数组（ArrayList类）和双端链表（LinkedList类）两种实现方式。

java.util.List<E>

ListIterator<E> listIterator()

			ListIterator<E> listIterator(int index)
			
返回一个列表迭代器

			迭代器第一次调用next返回给定位置元素
		
void add(int i, E element)

			void addAll(int i, Colletion<? extend E> elements)
			
向集合指定位置添加元素
		
E remove(int i)
			
删除给定位置元素并返回
		
E get(int i)
			
获得给定位置元素并返回
		
E set(int i, E element)
			
设置给定位置元素并返回原来的元素
		
int indexOf(Object element)

			int lastIndexOf(Object element)
			
返回与指定元素相等元素在列表中第一次出现的位置

			返回与指定元素相等元素在列表中最后一次出现的位置
		
java.util.ListIterator<E>

void add(E Element)
			
在当前位置添加一个元素
		
void set(E Element)
			
用新元素代替next或previous上次访问的元素
		
boolean havaPrevious()
			
反向迭代列表时是否还有可供访问的值
		
E previous()
			
返回前一个对象
		
int nextIndex()
			
返回下一次调用next时返回的元素索引
		
int previousIndex()
			
返回下一次调用previous时返回的元素索引
		
java.util.ArrayList<E>

ArrayList<E>()
			
构造一个空数组列表
		
boolean add(E obj)
			
在数组列表尾端添加一个元素，永远返回true
		
int size()
			
返回存储在数组中的当前元素数量
		
void set(int index, E obj)
			
设置数组列表指定位置的值
		
E get(int index)
			
获的指定位置的元素值
		
void add(int index, E obj)
			
向后移动元素，插入元素
		
E remove(int index)
			
删除一个元素，并将后面元素前移
		
java.util.LinkedList<E>

LinkedList()

			LinkedList(Colletion<? extend E> elements)
			
构造一个链表
		
void addFirst(E element)

			void addLast(E element)
			
添加元素到表头或表尾
		
E getFirst()

			E getLast()
			
返回表头或表尾的元素
		
E removeFirst()

			E removeLast()
			
删除表头或表尾的元素并返回
		
2、Set

Set接口扩展自Collection，它与List的不同之处在于，规定Set的实例不包含重复的元素。在一个规则集内，一定不存在两个相等的元素。AbstractSet是一个实现Set接口的抽象类，Set接口有三个具体实现类，分别是散列集HashSet、链式散列集LinkedHashSet和树形集TreeSet。

java.util.HashSet<E>

HashSet()

			HashSet(Colletion<? extend E> elements)

			HashSet(int initialCapacity)
			
构造散列表
		
java.util.LinkedHashSet<E>

LinkedHashSet是用一个链表实现来扩展HashSet类，它支持对规则集内的元素排序。HashSet中的元素是没有被排序的，而LinkedHashSet中的元素可以按照它们插入规则集的顺序提取。

java.util.TreeSet<E>

TreeSet扩展自AbstractSet，并实现了NavigableSet，AbstractSet扩展自AbstractCollection，树形集是一个有序的Set，其底层是一颗树,用红黑树实现，这样就能从Set里面提取一个有序序列了。在实例化TreeSet时，我们可以给TreeSet指定一个比较器Comparator来指定树形集中的元素顺序。树形集中提供了很多便捷的方法。

3、队列

java.util.Queue<E>(接口)

boolean add(E element)

			boolean offer(E element)
			
如果队列没有满，将元素添加到队列尾部
		
E remove()

			E poll()
			
如果队列不为空，删除并返回这个队列头部元素
		
E element()

			E peek()
			
如果队列不为空，返回这个队列头部元素
		
java.util.Deque<E>

接口Deque，是一个扩展自Queue的双端队列，它支持在两端插入和删除元素，Deque接口由ArrayDeque和LinkedList这两个类实现，所以通常我们可以使用LinkedList来创建一个队列。PriorityQueue类实现了一个优先队列，优先队列中元素被赋予优先级，拥有高优先级的先被删除。

java.util.ProrityQueue<E>

优先级队列中的元素可以按任意顺序插入，却总是按照排序的顺序进行检索。优先级队列由堆实现。堆是一个可以自我调整的二叉树，对树执行添加和删除操作，可以让最小元素移动到根（最小堆），而不必花费时间对元素进行排序

4、Map接口

Map，图，是一种存储键值对映射的容器类，在Map中键可以是任意类型的对象，但不能有重复的键，每个键都对应一个值，真正存储在图中的是键值构成的条目。

java.util.Map<K,V>

V get(Object key)
			
获得与键对应的值
		
V put(K key, V value)

			V putAll(Map<? extends K, ? extends V> entries)
			
将键与对应的值关系插入到映射中
		
boolean containKey(Object key)

			boolean containValue(Object value)
			
查询
		
java.util.HashMap<K,V>HashMap是基于哈希表的Map接口的非同步实现，继承自AbstractMap，AbstractMap是部分实现Map接口的抽象类。在之前的版本中，HashMap采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当链表中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

java.util.LinkedHashMap<K,V>

LinkedHashMap继承自HashMap，它主要是用链表实现来扩展HashMap类，HashMap中条目是没有顺序的，但是在LinkedHashMap中元素既可以按照它们插入图的顺序排序，也可以按它们最后一次被访问的顺序排序。

java.util.TreeHashMap<K,V>

TreeMap基于红黑树数据结构的实现，键值可以使用Comparable或Comparator接口来排序。TreeMap继承自AbstractMap，同时实现了接口NavigableMap，而接口NavigableMap则继承自SortedMap。SortedMap是Map的子接口，使用它可以确保图中的条目是排好序的。在实际使用中，如果更新图时不需要保持图中元素的顺序，就使用HashMap，如果需要保持图中元素的插入顺序或者访问顺序，就使用LinkedHashMap，如果需要使图按照键值排序，就使用TreeMap。

5、其他集合类

下面主要介绍一下其它几个特殊的集合类，Vector、Stack、HashTable、ConcurrentHashMap以及CopyOnWriteArrayList。

java.util.Vector<E>

用法上，Vector与ArrayList基本一致，不同之处在于Vector使用了关键字synchronized将访问和修改向量的方法都变成同步的了，所以对于不需要同步的应用程序来说，类ArrayList比类Vector更高效。

java.util.Stack<E>

Stack，栈类，是Java2之前引入的，继承自类Vector。

java.util.HashTable

HashTable和前面介绍的HashMap很类似，它也是一个散列表，存储的内容是键值对映射，不同之处在于，HashTable是继承自Dictionary的，HashTable中的函数都是同步的，这意味着它也是线程安全的，另外，HashTable中key和value都不可以为null。

java.util.ConcurrentHashMap

ConcurrentHashMap是HashMap的线程安全版。同HashMap相比，ConcurrentHashMap不仅保证了访问的线程安全性，而且在效率上与HashTable相比，也有较大的提高。

java.util.CopyOnWriteArrayList

CopyOnWriteArrayList，是一个线程安全的List接口的实现，它使用了ReentrantLock锁来保证在并发情况下提供高性能的并发读取。

java.util.CopyOnWriteArraySet

CopyOnWriteArraySet，是一个线程安全的set接口的实现，它使用了ReentrantLock锁来保证在并发情况下提供高性能的并发读取。

ConcurrentLinkedQuerue是一个先进先出的队列。它是非阻塞队列。

ConcurrentSkipListMap可以在高效并发中替代SoredMap（例如用Collections.synchronzedMap包装的TreeMap）。

ConcurrentSkipListSet可以在高效并发中替代SoredSet（例如用Collections.synchronzedSet包装的TreeMap）。

6、泛型集合算法

6.1  排序

static <T extends Comparable<? super T>> void java.util.Collections.sort(List<T> elements,[new Comparator<T>(){ public int compare(T o1, T o2){return ...}   } ])
			
对列表元素排序
		
6.2  查找

static <T extends Comparable<? super T>> int java.util.Collections.binarySearch(List<T> elements, T key)
			
二分查找key，返回对象索引
		
6.3  其他

static <T> java.util.Collections.min(Collection<T> elements, Comparator<? super T> c)

			static <T> java.util.Collections.max(Collection<T> elements, Comparator<? super T> c)
			
查找最小值/最大值
		
三、并发部分API

java.lang.Runnable

void run()
			
必须覆盖这个方法
		
java.lang.Thread

Thread()

			Thread(Runnable target)
			
构造器
		
void start()
			
启动线程
		
void run()
			
如果没有重写，调用关联Runnable的run方法
		
void interupt()
			
中断线程（中止阻塞状态，对运行线程无作用）
		
void setPriority(int newPriority)
			
设置优先级（1-10，默认5）
		
static void yield()

			static void sleep(long millis)
			
使当前线程处于让步状态（让步于同优先级或高优先级线程）

			休眠
		
void setDaemon()
			
设置为守护线程
		
Thread.State getState()
			
获得线程当前状态
		
锁对象

ReentrantLock myLock = new ReentrantLock();
mylock.lock();
try{
     critical section
}finally{
     mylock.unlock();
}

条件对象

private ReetranLock mylock = new ReetranLock();
private Condition sufficientFunds = mylock.newCondition()
public void transfer(int from, int amount)
{
    mylock.lock();
    try{
         while(account[from] < amount){
              sufficientFunds.await();
          }
          ...
          sufficientFunds.singalAll();
      }finally{
          mylock.unlock();
      }
}

synchronized关键字（内置锁）

格式1：synchronized 方法

格式2：synchronized（obj）{}

使用synchronized如何设置条件变量

void notifyAll()
			
解除在对象上调用wait方法的线程的阻塞状态
		
void wait()
			
导致线程进入等待状态
		

volatile域

volatile只提供可见性（在线程工作内存中被修改后立即写入到主存中），不提供原子性。

使用final变量可以保证可见性：构造函数完成时即不变，未完成构造期间对其他线程不可见。
java.lang.ThreadLocal<T>

作用：将内存共享变量变为线程拷贝变量
Executor类执行器

1）调用Executors类（工厂类）中静态工厂方法newCacherThreadPool

2）调用submit提交Runnable或Callable对象

3）当不再提交任何任务时，调用shutdown


 

在java中要实现栈和队列，需要用到java集合的相关知识，特别是Stack、LinkedList等相关集合类型。
一、栈的实现
栈的实现，有两个方法：一个是用java本身的集合类型Stack类型；另一个是借用LinkedList来间接实现Stack。
1.Stack实现
有关Stack的具体知识可以参考：http://www.cnblogs.com/skywang12345/p/3308852.html  
直接用Stack来实现非常方便，常用的api函数如下：

       boolean             isEmpty() // 判断当前栈是否为空
synchronized E             peek() //获得当前栈顶元素
synchronized E             pop() //获得当前栈顶元素并删除
             E             push(E object) //将元素加入栈顶
synchronized int           search(Object o)  //查找元素在栈中的位置，由栈低向栈顶方向数
2.LinkedList实现
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。

当LinkedList被当做栈来使用时，常用api及对应关系如下：

栈方法        等效方法
push(e)      addFirst(e)
pop()        removeFirst()
peek()       peekFirst()
	     isEmpty()  //判断是否为空


二、队列的实现
java中虽然有Queue接口，单java并没有给出具体的队列实现类，而Java中让LinkedList类实现了Queue接口，所以使用队列的时候，一般采用LinkedList。因为LinkedList是双向链表，可以很方便的实现队列的所有功能。
Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。 如果要使用前端而不移出该元素，使用

element()或者peek()方法。


java中定义队列 一般这样定义： Queue<E> queue = new LinkedList<E>();
当采用LinkedList来实现时，api的使用和对用关系如下：

队列方法       等效方法
offer(e)      offer(e)/offerLast(e)  //进队列，将元素加入队列末尾
poll()        poll()/pollFirst()  //获取队列头的元素并移除
peek()        peek()/peekFirst()  //获取队列头的元素
	      isEmpty() //判断是否为空