概念

栈是一种线性结构,相比数组,栈对应的操作是数组的子集,只能从一端添加元素,也只能从一端取出元素,这一端称为栈顶.
image.png

特点

栈是一种先进后出(后进先出)的数据结构.

image.png

数组栈实现

  1. public interface Stack<E> {
  2.     /**
  3.      * 获取栈中元素个数
  4.      *
  5.      * 时间复杂度 O(1)
  6.      * @return int
  7.      */
  8.     int getSize();
  10.     /**
  11.      * 判断栈是否为空
  12.      *
  13.      * 时间复杂度 O(1)
  14.      * @return boolean
  15.      */
  16.     boolean isEmpty();
  18.     /**
  19.      * 在栈中添加元素e(入栈)
  20.      *
  21.      * 时间复杂度 O(1)均摊
  22.      * @param e 元素
  23.      */
  24.     void push(E e);
  26.     /**
  27.      * 从栈中取出元素(出栈)
  28.      *
  29.      * 时间复杂度 O(1)均摊
  30.      * @return E
  31.      */
  32.     E pop();
  34.     /**
  35.      * 查看栈顶元素
  36.      *
  37.      * 时间复杂度 O(1)
  38.      * @return E
  39.      */
  40.     E peek();
  42. }

注意:这里的Array类是前面动态数组实现的Array类,点击动态数组跳转:

  1. public class ArrayStack<E> implements Stack<E> {
  3.     Array<E> array;
  5.     public ArrayStack(int capacity) {
  6.         array = new Array<>(capacity);
  7.     }
  9.     public ArrayStack() {
  10.         array = new Array<>();
  11.     }
  14.     @Override
  15.     public int getSize() {
  16.         return array.getSize();
  17.     }
  19.     @Override
  20.     public boolean isEmpty() {
  21.         return array.isEmpty();
  22.     }
  24.     public int getCapacity() {
  25.         return array.getCapacity();
  26.     }
  28.     @Override
  29.     public void push(E e) {
  30.         //在数组末尾添加元素
  31.         array.addLast(e);
  32.     }
  34.     @Override
  35.     public E pop() {
  36.         return array.removeLast();
  37.     }
  39.     @Override
  40.     public E peek() {
  41.         return array.getLast();
  42.     }
  44.     @Override
  45.     public String toString() {
  46.         StringBuilder builder = new StringBuilder();
  47.         builder.append("Stack: ");
  48.         builder.append("[");
  49.         for (int i = 0; i < array.getSize(); i++) {
  50.             builder.append(array.get(i));
  51.             if (i != array.getSize() - 1) {
  52.                 builder.append(",");
  53.             }
  54.         }
  55.         builder.append("] top");
  56.         return builder.toString();
  57.     }
  59.     public static void main(String[] args) {
  60.         ArrayStack<Integer> stack = new ArrayStack<>();
  61.         for (int i = 0; i < 5; i++) {
  62.             //入栈
  63.             stack.push(i);
  64.             System.out.println(stack);
  65.         }
  66.         //出栈
  67.         stack.pop();
  68.         System.out.println(stack);
  69.     }
  70. }

栈的应用

有效的括号(leetcode20题):

1. 要求:

  1.        给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。<br />有效字符串需满足：<br />左括号必须用相同类型的右括号闭合。<br />左括号必须以正确的顺序闭合。

2. 使用Java的Stack实现:

  1.  public static boolean isValid(String s) {
  2.         Stack<Character> stack = new Stack<>();
  3.         for (int i = 0; i < s.length(); i++) {
  4.             char c = s.charAt(i);
  5.             if (c == '(' || c == '[' || c == '{') {
  6.                 //将左括号全部放入栈中
  7.                 stack.push(c);
  8.             } else {
  9.                 if (stack.isEmpty()) {
  10.                     return false;
  11.                 }
  12.                 //删除栈顶元素并返回栈顶元素
  13.                 char topChar = stack.pop();
  14.                 if (c == ')' && topChar != '(') {
  15.                     return false;
  16.                 }
  17.                 if (c == ']' && topChar != '[') {
  18.                     return false;
  19.                 }
  20.                 if (c == '}' && topChar != '{') {
  21.                     return false;
  22.                 }
  24.             }
  25.         }
  26.         return stack.isEmpty();
  27.     }

3.使用Java的Stack结合Map实现:

  1. public static boolean isValid2(String s) {
  2.         int n = s.length();
  3.         //当括号成对时必然是偶数,若不为偶数可直接返回false
  4.         if (n % 2 == 1) {
  5.             return false;
  6.         }
  7.         Map<Character, Character> pairs = new HashMap<Character, Character>() {{
  8.             put(')', '(');
  9.             put(']', '[');
  10.             put('}', '{');
  11.         }};
  12.         Deque<Character> stack = new LinkedList<Character>();
  13.         for (int i = 0; i < n; i++) {
  14.             char ch = s.charAt(i);
  15.             //当元素是右括号时,删除栈顶元素使用返回的被删除的栈顶元素判断是否等于当前key元素的value值,不等直接返回false
  16.             if (pairs.containsKey(ch)) {
  17.                 if (stack.isEmpty() || !stack.pop().equals(pairs.get(ch))) {
  18.                     return false;
  19.                 }
  20.             } else {
  21.                 //当元素是左括号时存入栈中
  22.                 stack.push(ch);
  23.             }
  24.         }
  25.         //循环完毕,判断栈中是否还有元素,若没有元素则为ture
  26.         return stack.isEmpty();
  27.     }

4.使用go结合Map实现:

与Java版本Map实现方式思路一致

  1. func isValid(s string) bool {
  2.     n := len(s)
  3.     if n%2 == 1 {
  4.         return false
  5.     }
  6.     pairs := map[byte]byte{
  7.         ')': '(',
  8.         ']': '[',
  9.         '}': '{',
  10.     }
  11.     var stack []byte
  12.     for i := 0; i < n; i++ {
  13.         if pairs[s[i]] > 0 {
  14.             if len(stack) == 0 || stack[len(stack)-1] != pairs[s[i]] {
  15.                 return false
  16.             }
  17.             stack = stack[:len(stack)-1]
  18.         } else {
  19.             stack = append(stack, s[i])
  20.         }
  21.     }
  22.     return len(stack) == 0
  23. }

5.使用go不结合Map实现

与java版本的不结合map实现思路一致

  1. func isValid2(s string) bool {
  2.     var stack []byte
  3.     for i := 0; i < len(s); i++ {
  4.         c := s[i]
  5.         if c == '(' || c == '[' || c == '{' {
  6.             stack = append(stack, c)
  7.         } else {
  8.             if len(stack) == 0 {
  9.                 return false
  10.             }
  11.             topChar := stack[len(stack)-1]
  12.             if c == ')' && topChar != '(' {
  13.                 return false
  14.             }
  15.             if c == ']' && topChar != '[' {
  16.                 return false
  17.             }
  18.             if c == '}' && topChar != '{' {
  19.                 return false
  20.             }
  21.             stack = stack[:len(stack)-1]
  22.         }
  23.     }
  24.     return len(stack) == 0
  25. }

6.使用上面自己实现的ArrayStack数组栈实现:

  1. public static boolean isValid3(String s){
  2.         ArrayStack<Character> stack = new ArrayStack<>();
  3.         for (int i = 0; i < s.length(); i++) {
  4.             char c = s.charAt(i);
  5.             if (c == '(' || c == '[' || c == '{') {
  6.                 //将左括号全部放入栈中
  7.                 stack.push(c);
  8.             } else {
  9.                 if (stack.isEmpty()) {
  10.                     return false;
  11.                 }
  12.                 //删除栈顶元素并返回栈顶元素
  13.                 char topChar = stack.pop();
  14.                 if (c == ')' && topChar != '(') {
  15.                     return false;
  16.                 }
  17.                 if (c == ']' && topChar != '[') {
  18.                     return false;
  19.                 }
  20.                 if (c == '}' && topChar != '{') {
  21.                     return false;
  22.                 }
  24.             }
  25.         }
  26.         return stack.isEmpty();
  27.     }

项目demo