欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构_2:栈

程序员文章站 2024-03-18 11:51:28
...

栈 Stack

写在开头

  • 线性结构,栈操作是数组操作的子集
  • 先进后出的数据结构(LIFO),只能从一端添加元素,也只能从一端取出元素,这一端称为栈顶

栈的实现:复用动态数组,采用接口的方式进行构造ArrayStack<E>

  • Stack接口:

      public interface Stack<E> {
      
          /**
           * 获取栈内元素容量
           * @return
           */
          int getSize();
      
          /**
           * 栈空判断
           * @return
           */
          boolean isEmpty();
      
          /**
           * 入栈
           * @param e
           */
          void push(E e);
      
          /**
           * 出栈
           * @return
           */
          E pop();
      
          /**
           * 获取栈顶元素
           * @return
           */
          E peek();
      }
    
  • 接口实现类:ArrayStack<E>

      public class ArrayStack<E> implements Stack<E> {
    
          private Array<E> array;
      
          public ArrayStack(int capacity) {
              array = new Array<>(capacity);
          }
      
          public ArrayStack() {
              array = new Array<>();
          }
      
          public int getCapacity() {
              return array.getCapacity();
          }
      
          @Override
          public int getSize() {
              return array.getSize();
          }
      
          @Override
          public boolean isEmpty() {
              return array.isEmpty();
          }
      
          @Override
          public void push(E e) {
              array.addLast(e);
          }
      
          @Override
          public E pop() {
      		// 等同于:array.remove(size - 1);
              return array.removeLast();
          }
      
          @Override
          public E peek() {
      		// 等同于:array.get(size - 1);
              return array.getLast();
          }
      
          @Override
          public String toString() {
              return "stack.ArrayStack{" +
                      "array=" + array +
                      '}';
          }
      }
    

应用

  • 编辑器 - Undo(撤销)操作:Undo操作永远撤销的是当前一步操作的上一步操作,从操作栈中依次执行出栈操作。
  • 操作系统 - 系统调用栈:记录程序嵌套指令执行中断点,将中断点记录压入栈内(类比子函数执行点,重复子函数执行点入栈操作,直到调用至最底层子函数为止),出栈操作便是对底层中断点结果进行依次返回的操作。
  • 编辑器 - 括号匹配,以力扣-T20题目为例:
    • 题面:

        给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
        有效字符串需满足:
        	左括号必须用相同类型的右括号闭合。
        	左括号必须以正确的顺序闭合。
        注意空字符串可被认为是有效字符串。
      
    • 题解:利用栈的特性,扫描给定字符串字符元素,对左括号类别字符( ([{ ),执行入栈操作,对于非左括号类别字符:取栈顶元素进行配对逻辑判断,配对成功并且遍历结束后栈为空作为匹配成功。

        import java.util.Stack;
        class Solution {
            public boolean isValid(String s) {
                Stack<Character> stack = new Stack<>();
                for (int i = 0; i < s.length(); i ++) {
                    char c = s.charAt(i);
                    if (c == '(' || c =='[' || c == '{') {
                        stack.push(c);
                    } else {
                        if (stack.isEmpty()) {
                            return false;
                        }
                        if (c == ')' && stack.pop() != '(') {
                            return false;
                        }
                        if (c == ']' && stack.pop() != '[') {
                            return false;
                        }
                        if (c == '}' && stack.pop() != '{') {
                            return false;
                        }
                    }
                }
                return stack.isEmpty();
            }
        }