数据结构之栈

基本概念

　　栈(stack)又叫堆栈，是限制在表的一端进行插入和删除的线性表，按照后进先出(LIFO, Last In First Out)的原则操作数据，先进入的数据被压入栈底，最后的数据在栈顶。

　　栈中元素为零时则为空栈，插入数据称为进栈(push)，删除数据称为出栈(pop)。

　　Java中提供栈的实现java.util.Stack<E> extends Vector<E>

栈的模拟实现

 1 public class MyStack {
 2     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 3 
 4     private Object[] elementData;
 5     private int elementCount;
 6 
 7     public MyStack () {
 8         elementData = new Object[10];
 9     }
10 
11     public MyStack(int minCapacity) {
12         //带最小容量的初始化
13         elementData = new Object[minCapacity];
14     }
15 
16     //入栈元素
17     public void push(Object item) {
18         grow(elementCount + 1);
19         elementData[elementCount++] = item;
20     }
21 
22     //出栈元素
23     public Object pop() {
24         if (isEmpty()) throw new EmptyStackException();
25         Object item = elementData[--elementCount];
26         elementData[elementCount] = null;
27         return item;
28     }
29 
30     //容量是否需要扩容
31     private void grow(int minCapacity) {
32         if (minCapacity <= elementData.length) return;
33         int newCapacity = elementData.length << 1 > MAX_ARRAY_SIZE ? MAX_ARRAY_SIZE : elementData.length << 1;
34         System.out.println(String.format("grow:%s---->%s", elementData.length, newCapacity));
35         elementData = Arrays.copyOf(elementData, newCapacity);
36     }
37 
38     public boolean isEmpty() {
39         return elementCount == 0;
40     }
41 
42     public static void main(String[] args) {
43         MyStack stack = new MyStack(3);
44         //字段反转
45         String strs = "其实我很在乎你 难道你就不明白";
46         for (Character str : strs.toCharArray()) {
47             stack.push(str);
48         }
49         while (!stack.isEmpty()) {
50             System.out.print(stack.pop());
51         }
52         System.out.println("");
53         //判断标签是否匹配
54         strs = "<123(22[qd]5)>44>";
55         for (char str : strs.toCharArray()) {
56             if (str == '<' || str == '(' || str == '[') stack.push(str);
57             if (str == '>' || str == ')' || str == ']') {
58                 if (stack.isEmpty()) throw new RuntimeException("MyStack is Empty,But there has " + str);
59                 char pop = (char) stack.pop();
60                 if (str == '>' && pop != '<' || str == ')' && pop != '(' || str == ']' && pop != '[') throw new RuntimeException(String.format("%s not patch %s", pop, str));
61             }
62         }
63     }
64 }

总结

　　栈是一个概念上的工具具体实现什么功能由我们自己决定

　　栈通过提供限制性的访问方法push()和pop()使程序不易出错