栈是一种后进先出的数据结构（Last In First Out, LIFO）,本文将以数组实现栈的数据结构。

1.栈的接口

1 /** 2  * @author 阿遠 3  * Date: 2019/1/14 4  * Time: 10:37 5  */ 6 public interface Stack
      
        { 7  8     int getSize(); // 查看栈的容量 9     boolean isEmpty(); // 判断栈非空10     void push(E e); // 入栈11     E pop(); // 出栈12     E peek(); // 查看栈顶元素13 }
      

2.栈的接口的数组实现

1 /**  2  * @author 阿遠  3  * Date: 2019/1/13  4  * Time: 19:29  5  */  6 // 数组操作接口的实现  7 public class Array
      
        {  8   9     private E[] data; 10     private  int size; // 数组中实际元素数量 11  12     // 构造函数，传入数组的容量capacity构造Array 13     public Array(int capacity) { 14         data = (E[]) new Object[capacity]; 15         size = 0; 16     } 17     // 默认构造函数，默认数组的容量capacity=10 18     public Array() { 19         this(10); 20     } 21     // 获取数组中的容量 22     public int getCapacity() { 23         return data.length; 24     } 25     //获取数组的元素个数 26     public int getSize() { 27         return size; 28     } 29     // 判断数组是否为空 30     public boolean isEmpty() { 31         return size == 0; 32     } 33     // 向所有元素后添加一个新元素 34     public void addLast(E e) { 35 //        if (size == data.length){ 36 //            throw new IllegalArgumentException("addLast failed!Array is full"); 37 //        } 38 //        data[size] = e; 39 //        size++; 40         // 复用add 41         add(size, e); 42     } 43     //在所有元素前添加新元素 44     public void addFirst(E e) { 45         add(0, e); 46     } 47     // 在index个位置插入一个新元素,扩容成动态数组，此处我们扩容成原来的2倍，在ArrayList中为1.5倍 48     public void add(int index, E e) { 49  50         if (index < 0 || index > size) { 51             throw new IllegalArgumentException("Add failed!Index required >=0 and 
       
        = index; i--){ 57             data[i+1] = data[i]; 58         } 59         data[index] = e; 60         size ++; 61     } 62     // 给数组扩容或者缩容 63     private void resize(int newCapacity) { 64         E[] newData = (E[]) new  Object[newCapacity]; 65         for (int i = 0; i < size; i++) { 66             newData[i] = data[i]; 67         } 68         data = newData; 69     } 70     // 获取index索引位置的元素 71     public E get(int index) { 72         if (index < 0 || index > size) { 73             throw new IllegalArgumentException("Get failed!Index is illegal."); 74         } 75         return data[index]; 76     } 77     // 获取数组第一个元素 78     public E getFirst() { 79         return get(0); 80     } 81     // 获取数组最后一个元素 82     public E getLast() { 83         return get(size-1); 84     } 85     //修改index元素索引位置的元素为e 86     public void  set(int index, E e) { 87         if (index < 0 || index > size) { 88             throw new IllegalArgumentException("Set failed!Index is illegal."); 89         } 90         data[index] = e; 91     } 92  93     @Override 94     public  String toString() { 95         StringBuilder res = new StringBuilder(); 96         res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length)); 97         res.append("["); 98         for (int i = 0; i < size; i++) { 99             res.append(data[i]);100             if (i != size-1)101                 res.append(", ");102         }103         res.append("]");104         return res.toString();105     }106 107     // 查找数组中是否存在元素e108     public boolean contains(E e) {109         for (int i= 0; i < size; i++) {110             if (data[i] == e)111                 return true;112         }113         return false;114     }115     // 查找数组中元素e所在的索引，如果不存在元素e,则返回-1116     public int find(E e) {117         for (int i = 0; i < size; i++) {118             if (data[i] == e)119                 return  i;120         }121         return -1;122     }123     // 从数组中删除元素,返回删除的元素124     public E remove(int index) {125         if (index < 0 || index >= size) {126             throw new IllegalArgumentException("Remove failed!Index is illegal.");127         }128         E ret = data[index];129         for (int i = index + 1; i < size; i++) {130             data[i-1] = data[i];131         }132         size --;133         data[size] = null; // loitering objects != memory leak134         if (size == data.length/4 && data.length/2 != 0) {135             resize(data.length/2);136         }137         return ret;138     }139     // 从数组中删除第一个元素140     public E removeFirst() {141         return remove(0);142     }143     // 从元素中删除最后一个元素144     public E removeLast() {145         return remove(size-1);146     }147     // 从数组中删除元素e148     public void removeElement(E e) {149         int index = find(e);150         if (index != -1) {151             remove(index);152         }153     }154 }
       
      

1 /** 2  * @author 阿遠 3  * Date: 2019/1/14 4  * Time: 10:39 5  */ 6 public class ArrayStack
      
        implements Stack
       
         { 7  8     // 基于动态数组实现的栈结构 9     Array
        
          array;10 11     public  ArrayStack(int capacity) {12         array = new Array
         
          (capacity);13     }14 15     public ArrayStack() {16         array = new Array
          
           ();17     }18 19     // 获取数组容量20     public int getCapacity() {21         return array.getCapacity();22     }23 24     // 获取数组元素个数25     @Override26     public int getSize() {27         return array.getSize();28     }29 30     // 非空判断31     @Override32     public boolean isEmpty() {33         return array.isEmpty();34     }35 36     // 入栈37     @Override38     public void push(E e) {39         array.addLast(e);40     }41 42     // 出栈43     @Override44     public E pop() {45         return array.removeLast();46     }47 48     // 取出栈顶元素49     @Override50     public E peek() {51         return array.getLast();52     }53 54     @Override55     public String toString() {56         StringBuilder res = new StringBuilder();57         res.append("Stack：");58         res.append("[");59          for (int i = 0; i < array.getSize(); i++){60              res.append(array.get(i));61              if (i != array.getSize()-1) {62                  res.append(", ");63              }64          }65         res.append("] top");66          return res.toString();67     }68 }
          
         
        
       
      

 2.1测试

1 public class Main { 2  3     public static void main(String[] args) { 4  5         ArrayStack
     
       stack = new ArrayStack
      
       (); 6  7         for (int i = 0; i < 5; i++) { 8             stack.push(i); 9         }10         System.out.println(stack);11         stack.pop();12         System.out.println("出栈：");13         System.out.println(stack);14     }15 }
      
     

 2.2测试结果：

Stack：[0, 1, 2, 3, 4] top出栈：Stack：[0, 1, 2, 3] top

3.栈的接口的链表实现

1 /**  2  * @author 阿遠  3  * Date: 2019/1/15  4  * Time: 11:08  5  */  6 public class LinkedList
      
        {  7   8   9     private Node dummyhead; // 链表头 10     private int size; // 链表容量 11     private class Node{ 12         public E e;  // 元素 13         public Node next;   // 结点 14  15         private Node(E e, Node next) { 16             this.e = e; 17             this.next = next; 18         } 19  20         public Node(E e) { 21             this(e, null); 22         } 23  24         public Node() { 25             this(null, null); 26         } 27  28         @Override 29         public String toString() { 30             return e.toString(); 31         } 32     } 33  34     public LinkedList() { 35         dummyhead = new Node(null, null); 36         size = 0; 37     } 38  39     // 获取列表中的元素个数 40     public int getSize() { 41         return size; 42     } 43  44     // 返回链表是否为空 45     public boolean isEmpty() { 46         return size == 0; 47     } 48  49     //在链表的index（0-based）位置添加新的元素e 50     public void add(int index, E e) { 51         if (index < 0 || index > size) { 52             throw new IllegalArgumentException("Add failed.Illegal index."); 53         } 54         Node pre = dummyhead; 55         for (int i = 0; i < index; i ++) { 56             pre = pre.next; 57         } 58 //            Node node = new Node(e); 59 //            node.next = pre.next; 60 //            pre.next = node; 61         pre.next = new Node(e, pre.next); 62         size ++; 63     } 64     //在链表头添加新的元素 65     public void addFirst(E e) { 66         add(0, e); 67     } 68     // 在链表的末尾添加新的元素 69     public void addLast(E e) { 70         add(size, e); 71     } 72  73     // 获得链表的第index个位置的元素 74     public E get(int index) { 75         if (index < 0 || index >= size) 76             throw new IllegalArgumentException("Get failed.Illegal index."); 77         Node cur = dummyhead.next; 78         for (int i = 0; i < index; i++) { 79             cur = cur.next; // 遍历找到index处的Node 80         } 81         return cur.e; 82     } 83     // 获得列表的第一个元素 84     public E getFirst() { 85         return get(0); 86     } 87     // 获得链表中最后一个元素 88     public E getLast() { 89         return get(size - 1); 90     } 91  92     // 修改列表中第index个位置的元素为e 93     public void set(int index, E e) { 94         if (index < 0 || index >= size) 95             throw new IllegalArgumentException("Update failed.Illegal index."); 96         Node cur = dummyhead.next; 97         for (int i = 0; i < index; i++) { 98             cur = cur.next; 99         }100         cur.e = e;101     }102 103     // 查找链表中是否有元素e104     public boolean contains(E e) {105         Node cur = dummyhead.next;106         while(cur != null) {107             if (cur.e.equals(e)) {108                 return true;109             }110             cur = cur.next;111         }112         return false;113     }114     // 从列表中删除index位置处的元素，返回删除的元素115     public E remove(int index) {116         if (index < 0 || index >= size)117             throw new IllegalArgumentException("Remove failed.Illegal index.");118         Node prev = dummyhead;119         for (int i = 0; i < index; i ++) {120             prev = prev.next;121         }122         Node retNode = prev.next;123         prev.next = retNode.next;124         retNode.next = null;125         size --;126 127         return retNode.e;128     }129     // 从链表中删除第一个元素，返回删除的元素130     public E removeFirst() {131         return remove(0);132     }133     // 从链表中删除最后一个元素134     public E removeLast() {135         return remove(size - 1);136     }137 138     @Override139     public String toString() {140         StringBuilder res = new StringBuilder();141 //        Node cur = dummyhead.next;142 //        while(cur != null) {143 //            res.append(cur + "->");144 //            cur = cur.next;145 //        }146         for (Node cur = dummyhead.next; cur != null; cur = cur.next)147             res.append(cur + "->");148         res.append("NULL");149         return res.toString();150     }151 }
      

 

1 /** 2  * @author 阿遠 3  * Date: 2019/1/17 4  * Time: 11:15 5  */ 6 public class LinkedListStack
      
        implements Stack
       
         { 7  8     private LinkedList
        
          list; 9 10     public LinkedListStack(){11         list = new LinkedList
         
          ();12     }13 14     @Override15     public int getSize() {16         return list.getSize();17     }18 19     @Override20     public boolean isEmpty() {21         return list.isEmpty();22     }23 24     @Override25     public void push(E e) {26         list.addFirst(e);27     }28 29     @Override30     public E pop() {31         return list.removeFirst();32     }33 34     @Override35     public E peek() {36         return list.getFirst();37     }38 39     @Override40     public String toString() {41         StringBuilder res = new StringBuilder();42         res.append("Stack: top ");43         res.append(list);44         return res.toString();45     }46 47 }
         
        
       
      

 

 3.1测试

1 public class Main { 2  3     public static void main(String[] args) { 4  5         LinkedListStack
     
       stack = new LinkedListStack
      
       (); 6  7         for (int i = 0; i < 5; i++) { 8             stack.push(i); 9         }10         System.out.println(stack);11         stack.pop();12         System.out.println("出栈：");13         System.out.println(stack);14     }15 }
      
     

 

 3.2测试结果

Stack: top 4->3->2->1->0->NULL出栈：（后进先出）Stack: top 3->2->1->0->NULL

 

4.应用实例

　　该应用实例是解决LeetCode上面的一道题——有效的括号。

题目：

　　给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

　　有效字符串需满足：

            1.左括号必须用相同类型的右括号闭合。

            2.左括号必须以正确的顺序闭合。

　　注意空字符串可被认为是有效字符串。

答案：

1 /** 2  * @author 阿遠 3  * Date: 2019/1/14 4  * Time: 16:19 5  */ 6  7 import java.util.Stack; 8  9 /**10  * 有效的括号，这里使用的java.util包下的Stack类实现11  */12 public class SolutionOne {13 14     public boolean isValid(String s) {15         Stack
     
       stack = new Stack
      
       ();16         for (int i = 0; i < s.length(); i++) {17             char c = s.charAt(i);18             // 如果括号为左括号则将其压入栈中19             if (c == '(' || c == '[' || c == '{'){20                 stack.push(c);21             } else {22                 // 如果栈为空说明不是以左括号开始，直接退出23                 if (stack.isEmpty()) {24                     return false;25                 }26                 // 取出栈顶元素匹配27                 char topChar = stack.pop();28                 if (c == ')' && topChar != '(')29                     return false;30                 if (c == ']' && topChar != '[')31                     return false;32                 if (c == '}' && topChar != '{')33                     return false;34             }35         }36         return stack.isEmpty();  // 只有当最后stack的字符串全部被匹配时才是成功的37     }38     public static void main(String[] args){39          System.out.println((new SolutionOne()).isValid("(){}[]"));40          System.out.println((new SolutionOne()).isValid("(}[]"));41     }42 }