一、堆是一个运行时数据区，通过new等指令创建，不需要程序代码显式释放
<1>优点：
可动态分配内存大小，生存周期不必事先告诉编译器，Java垃圾回收自动回收不需要的数据；
<2>缺点：
运行时需动态分配内存，数据存取速度较慢。
如：
String str = new String(“abc”);
String str2 = new String(“abc”);
二、栈(stack)又名堆栈，它是一种先进后出(FILO)的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
<1>优点：
存取速度比堆快，仅次于寄存器，栈数据可以共享；
<2>缺点：
存在栈中的数据大小与生存期必须是确定的，缺乏灵活性。
String str = “abc”;
String str2 = “abc”;
表的含义如下图所示：
下面介绍两种栈的实现方式：
1.采用链表中节点的方式实现：
public class MyStackNode<E> {
Node<E> top = null;
public boolean isEmpty() {
return top == null;
}
public void push(E data) {
Node<E> newNode = new Node<E>(data);
newNode.next = top;
top = newNode;
}
public E pop() {
if (this.isEmpty())
return null;
E data = top.data;
top = top.next;
return data;
}
public E peek() {
if (isEmpty()) {
return null;
}
return top.data;
}
}
2.采用数组的方式实现：
public class MyStackArry<E> {
private Object[] stack;
private int size;
public MyStackArry() {
stack = new Object[];
}
public boolean isEmpty() {
return size == ;
}
public E peek() {
if (isEmpty())
return null;
return (E) stack[size - ];// 如果有元素就返回最后一个
}
/**
* 移除栈顶部元素移除
*
* @return
*/
public E pop() {
E e = peek();// 保存最后一个元素的备份
stack[size - ] = null;// 给数组最后一个元素赋null
size--;
return e;
}
/**
* 把项压入栈顶部
*
* @param item
* @return
*/
public E push(E item) {
ensureCapacity(size + );
stack[size++] = item;
return item;
}
/**
* 检查容量是否足够，不够再原有的数组基础创建新的数组
*
* @param size
*/
public void ensureCapacity(int size) {
int len = stack.length;
if (size > len) {
// int newLen = 10;
// stack = Arrays.copyOf(stack, newLen);
// 如果栈满，则创建空间为当前栈空间两倍的栈
Object[] temp = stack;
stack = new Object[ * stack.length];
System.arraycopy(temp, , stack, , temp.length);
}
}
/**
* 返回对象在堆栈中的位置，以1 为基数
*
* @param o
* @return
*/
public int search(Object o) {
int index = lastIndexOf(o);
return index == - ? index : size - index;
}
/**
* 查找下标的方法
*
* @param o
* @return
*/
private int lastIndexOf(Object o) {
if (isEmpty()) {
throw new EmptyStackException(); // 如果数组为空，就抛出一个自定义异常
}
// 当传进来的元素为空时
if (o == null) {
for (int i = size - ; i >= ; i--) {
if (stack[i] == null) {
return i;
}
}
// 不为空时
} else {
for (int i = size - ; i >= ; i--) {
if (o.equals(stack[i])) {
return i;
}
}
}
return -; // 没有找到，返回-1
}
// 自定义异常
private static class EmptyStackException extends RuntimeException {
public EmptyStackException() {
super("堆栈为空");
}
}
三、队列 是一种先进先出的线性表。其限制仅在表的一端（尾端）进行插入，另一端（首端）进行删除的线性表，先进先出FIFO。
Quene类尚不在java集合框架中，因此它有很大的灵活性，为了能够进行代码重用，我们试着通过继承（is-a关系）或者合成（have-a关系）一些实现了List接口的类来定义Queue类。直观的选择是ArrayList和LinkedList。
1.第一种实现方式：LinkedList插入删除效率比较高，可以实现队列的尾部插入和头部删除只需常量次调用，我们首先选择LinkedList来实现Queue。
这里我们采用采用合成（have-a关系）的方法，通过包含一个LinkedList字段来定义一个Queue类。
实现方式如下：
public class MyQueueLink<E> {
private LinkedList<E> list;
public MyQueueLink() {
list = new LinkedList<E>();
}
//入队
public void put(E e) {
list.addLast(e);
}
//出队
public E pop() {
return list.removeFirst();
}
public boolean isEmpty() {
return list.isEmpty();
}
public int size() {
return list.size();
}
//获得队列的第一个元素
public E front() {
return list.getFirst();
}
}
2.第二种可选择的实现方式，用数组的方式实现
public class MyQueneArry {
protected Object[] data;
protected int size, head, tail;
public MyQueneArry() {
final int INTTIAN_LENGTH = ;
data = new Object[INTTIAN_LENGTH];
size = ;
head = ;
tail = -;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == ;
}
public Object front() {
if (size == )
throw new NoSuchElementException();
return data[head];
}
//入队
public void enquene(Object element) {
if (size == data.length) {
Object[] oldData = data;
data = new Object[data.length * ];
System.arraycopy(oldData, head, data, , oldData.length - head);
if (head > )
System.arraycopy(oldData, , data, head + , tail - );
head = ;
tail = oldData.length - ;
}
tail = (tail + ) % data.length;
size++;
data[tail] = element;
}
//出队
public Object dequene() {
if (size == )
throw new NoSuchElementException();
Object element = data[head];
head = (head + ) % data.length;
return element;
}
public static void main(String[] args) {
MyQueneArry q = new MyQueneArry();
for (int i = ; i < ; i++) {
q.enquene(i);
}
System.out.println("队列长度：" + q.size());
System.out.println("队列首元素：" + q.dequene());
System.out.println("队列首元素：" + q.dequene());
}
}