堆栈（stack）又称为栈或堆叠，是计算机科学中的一种抽象资料类型，只允许在有序的线性资料集合的一端（称为堆栈顶端，top）进行加入数据（push）和移除数据（pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作

特点

• 线性结构
• 先进后出(LIFO)
• 从栈顶进，栈顶出

入栈操作：

出栈操作：

IStack接口

public interface IStack<E> {//获取数据大小int getSize();//是否为空boolean isEmpty();//入栈void push(E e);//出栈E pop();//查看栈顶数据E peek();
}

MyArrayStack实现

/* 基于数组实现栈结构* 栈的特点：* 1、线性结构* 2、先进后出(LIFO)* 3、只能从栈顶进，栈顶出，所以不会添加数据的时候只会涉及到数据的扩容，不会造成数据的搬移/
public class MyArrayStack<E> implements IStack<E> {private static final int DEFAULT_CAPACITY = 10;private E[] data;private int size;public MyArrayStack(int capacity) {data = (E[]) new Object[capacity];size = 0;}public MyArrayStack() {this(DEFAULT_CAPACITY);}@Overridepublic int getSize() {return size;}@Overridepublic boolean isEmpty() {return size == 0;}//入栈@Overridepublic void push(E e) {//如果数据已满，则扩容为原来的2倍if (size == data.length) {resize(data.length * 2);}data[size] = e;size++;}//调整容量private void resize(int newCapacity) {E[] newData = (E[]) new Object[newCapacity];for (int i = 0; i < data.length; i++) {newData[i] = data[i];}data = newData;}//出栈@Overridepublic E pop() {E ret = data[size - 1];//如果数据的大小为容量的1/4，则缩容为目前容量的1/2if (size == data.length / 4 && data.length / 2 != 0) {resize(data.length / 2);}data[size - 1] = null;size--;return ret;}@Overridepublic E peek() {return data[size - 1];}public String toString(){StringBuilder stringBuilder=new StringBuilder();stringBuilder.append("[");for (int i = 0; i < size; i++) {stringBuilder.append(data[i]);}stringBuilder.append("]");return stringBuilder.toString();}
}

JDK源码实现分析

Stack类

public class Stack<E> extends Vector<E> {/* Creates an empty Stack.*/public Stack() {}//入栈public E push(E item) {addElement(item);return item;}//出栈public synchronized E pop() {E obj;int len = size();obj = peek();removeElementAt(len - 1);return obj;}//查看栈顶数据public synchronized E peek() {int len = size();if (len == 0)throw new EmptyStackException();return elementAt(len - 1);}//栈是否为空public boolean empty() {return size() == 0;}public synchronized int search(Object o) {int i = lastIndexOf(o);if (i >= 0) {return size() - i;}return -1;}/ use serialVersionUID from JDK 1.0.2 for interoperability */private static final long serialVersionUID = 1224463164541339165L;
}

1. Stack继承了Vector
2. 入栈和出栈都是调用父类的addElement和removeElementAt

Vector类

• 属性定义

    //数据存储的容器protected Object[] elementData;//数据大小protected int elementCount;//扩容增加值，如果大于0则增加capacityIncrement，否则翻倍protected int capacityIncrement;

1. 基于数组实现

• 构造方法

 public Vector(int initialCapacity, int capacityIncrement) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);this.elementData = new Object[initialCapacity];this.capacityIncrement = capacityIncrement;}public Vector(int initialCapacity) {this(initialCapacity, 0);}public Vector() {this(10);}public Vector(Collection<? extends E> c) {elementData = c.toArray();elementCount = elementData.length;// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, elementCount, Object[].class);}

1. 默认的数组容量为10
2. 默认的扩容增长为0，所以扩容的时候是当前容量的倍数扩容的

• 添加数据

 //添加数据public synchronized void addElement(E obj) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = obj;}//检查容量private void ensureCapacityHelper(int minCapacity) {// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}//数组的最大的扩容值private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//扩容private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;//默认的capacityIncrement为0，所以默认采用的扩容是翻倍的int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);}//获取最大的扩容值private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}

1. 默认的capacityIncrement为0，所以默认采用的扩容是翻倍的
2. 如果目前数据增加一个数据以后总大小大于Integer.MAX_VALUE - 8则最大的扩容量为Integer.MAX_VALUE ；如果小于Integer.MAX_VALUE - 8，则最大的扩容量为Integer.MAX_VALUE - 8
3. 扩容还是借助Arrays.copyOf

• 移除数据

public synchronized void removeElementAt(int index) {modCount++;if (index >= elementCount) {throw new ArrayIndexOutOfBoundsException(index + " >= " +elementCount);}else if (index < 0) {throw new ArrayIndexOutOfBoundsException(index);}int j = elementCount - index - 1;if (j > 0) {System.arraycopy(elementData, index + 1, elementData, index, j);}elementCount--;elementData[elementCount] = null; /* to let gc do its work */}

4. 直接调用System.arraycopy()进行数据的搬移

算法应用

20. Valid Parentheses

结题思路：
1、该题的符号局限于’()‘，‘[]’,’{}’
2、该类符号是成对出现的

解法1、

遍历字符串，如果是符号的左边部分，则放入栈中；如果不是左边部分，则从栈中取出栈顶的数据，查看是否匹配。

public static boolean solution(String parentheses) {Stack<Character> stack = new Stack<>();for (char c : parentheses.toCharArray()) {if (c == '(' || c == '[' || c == '{') {//符号的左边部分stack.push(c);} else {//符号的右边部分//如果此时栈里面没有数据，说明该字符串没有符号的左边部分，所以不合法if (stack.isEmpty()) return false;//取出栈顶数据，比较是否匹配Character left = stack.pop();if (left == '(' && c != ')') return false;if (left == '[' && c != ']') return false;if (left == '{' && c != '}') return false;}}return stack.isEmpty();}

解法2

1、核心还是把符号的左部分放入栈中。
2、利用HashMap把符号的左右做一次映射关系，更好的匹配

public static boolean solution(String parentheses) {Stack<Character> stack = new Stack<>();HashMap<Character, Character> map = new HashMap<>();map.put('(', ')');map.put('[', ']');map.put('{', '}');for (char c : parentheses.toCharArray()) {if (map.containsKey(c)) {stack.push(c);} else {if (stack.isEmpty() || map.get(stack.pop()) != c) {return false;}}}return stack.isEmpty();}

解法3

栈中不放入符号的左边部分，而是放入与左边部分相匹配的，最后直接比较栈中的数据是否和后面的右边部分相等。

 public static boolean solution(String parentheses) {Stack<Character> stack = new Stack<>();for (char c : parentheses.toCharArray()) {if (c == '(') {//放入与'('匹配的')'stack.push(')');} else if (c == '[') {//放入与'['匹配的']'stack.push(']');} else if (c == '{') {//放入与'{'匹配的'}'stack.push('}');} else if (stack.isEmpty() || c != stack.pop()) {//如果此时栈为空，或者不相等，则是不合法的return false;}}return stack.isEmpty();}