(3)栈-Stack

应用很广的一种数据结构 栈和队列也是线性表 ，可以说是一种操作被限制的线性表。 所以它也有 顺序存储和 链式存储 栈 ：{      特点：后进先出  LIFO 每次只能访问栈顶的第一个peek() Java的栈：         Stack:                        1-->public Stack()创建一个空堆栈                           2-->public boolean empty()测试堆栈是否为空;                           3-->public  E  pop()移除堆栈顶部的对象，并作为此函数的值返回该对象。 Stact< E>    出                           4-->public E  push(E item)把项压入堆栈顶部    进                           5-->public E peek()查看堆栈顶部的对象，但不从堆栈中移除它。                            6-->public boolean empty()测试堆栈是否为空         栈的应用一般运用在 1.输入  之后逆向输出 2.语法检查：括号匹配 3.迷宫求解，表达式求值 4.行编辑器  就像现在输出字的情况。 考点：输出状态 设一个栈的序列为ABCD  则借助一个栈的输出序列不可能的是（） a ABCD   b.DCBA  c.ACDB    d.DABC 解答: D先出则  CBA还在栈里    输出的序列一定是DCBA 已知一个栈的进栈序列是1,2,3,…,n,其输出序列 是 p 1 ,p 2 ,…, p n , 若 p 1 =n, 则 p i 的值是   。 p1 = n p2 = n-1 p3 = n-2 ... pi = n-(i-1) = n-i+1 .... pn = 1; 自定义的栈： 顺序存储： 使用数组进行存储数据 java { public interface MyStack<T> {       /**       * 判断栈是否为空       */       boolean isEmpty();       /**       * 清空栈       */       void clear();       /**       * 栈的长度       */       int length();       /**       * 数据入栈       */       boolean push(T data);       /**       * 数据出栈       */       T pop();   }   //数组存储 public class MyArrayStack<T> implements MyStack<T> {       private Object[] objs = new Object[16];       private int size = 0;          @Override       public boolean isEmpty() {           return size == 0;       }          @Override       public void clear() {           // 将数组中的数据置为null, 方便GC进行回收           for (int i = 0; i < size; i++) {               objs[size] = null;           }           size = 0;       }          @Override       public int length() {           return size;       }          @Override       public boolean push(T data) {           // 判断是否需要进行数组扩容           if (size >= objs.length) {               resize();           }           objs[size++] = data;           return true;       }          /**       * 数组扩容       */       private void resize() {           Object[] temp = new Object[objs.length * 3 / 2 + 1];           for (int i = 0; i < size; i++) {               temp[i] = objs[i];               objs[i] = null;           }           objs = temp;       }          @SuppressWarnings("unchecked")       @Override       public T pop() {           if (size == 0) {               return null;           }           return (T) objs[--size];       }          @Override       public String toString() {           StringBuilder sb = new StringBuilder();           sb.append("MyArrayStack: [");           for (int i = 0; i < size; i++) {               sb.append(objs[i].toString());               if (i != size - 1) {                   sb.append(", ");               }           }           sb.append("]");           return sb.toString();       }   }     // 链式存储  就采用结点来存储而已  其他没啥特点了   就是插入删除速度快点，而存储查询比较慢 public class MyLinkedStack<T> implements MyStack<T> {       /**       * 将数据封装成结点       */       private final class Node {           private Node pre;           private T data;       }    /**       * 栈顶指针       */       private Node top;       /**       * 栈的长度       */       private int size;              public MyLinkedStack() {           top = null;           size = 0;       }              @Override       public boolean isEmpty() {           return size == 0;       }              @Override       public void clear() {           top = null;           size = 0;       }              @Override       public int length() {           return size;       }              @Override       public boolean push(T data) {           Node node = new Node();           node.data = data;           node.pre = top;           // 改变栈顶指针           top = node;           size++;           return true;       }              @Override       public T pop() {           if (top != null) {               Node node = top;               // 改变栈顶指针               top = top.pre;               size--;               return node.data;           }           return null;       }   } } }