数据结构之栈详解

以你之姓@ 2022-03-06 02:48 220阅读 0赞

### 文章目录 ###

*  栈
 *   *  栈的应用
     *  栈的实现
     *  栈的时间复杂度
     *  栈的应用
     *  使用栈解决有效的括号问题（LeetCode第二十号问题）

# 栈 #

*  栈也是一种数据结构
 *  相比数组，栈对应的操作是数组的子集
 *  只能从一端添加元素，也只能从一端取出元素
 *  这一端称为栈顶
 *  栈是一种后进先出的数据结构
 *  Last In First Out(LIFO)
 *  在计算机的世界里，栈拥有着不可思议的作用

## 栈的应用 ##

*  无处不在的Undo操作（撤销）
 *  程序调用的系统栈

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]  
如图，当我们执行程序A到第二行时，要跳转去执行B而暂停A，这时系统就会将A2放入系统栈中，说明说明A暂停在了第二行中断了，在执行B时到第二行时会中断跳转到C中，将状态B2压入系统栈中，在执行完C后系统会在系统栈中依次取出之前中断的B2，A2继续执行。

## 栈的实现 ##

Stack

*  void push(E)：入栈
 *  E pop()：出栈
 *  E peek()：查看栈顶元素（不出）
 *  int getSize()：返回栈元素个数
 *  boolean isEmpty()：栈是否为空

这里我们使用基于动态数组的实现方式

/**
     * Created by binzhang on 2019/3/16.
     */
    public interface Stack<E> { 
        int getSize();
        boolean isEmpty();
        void push(E e);
        E pop();
        E peak();
    }
    
    /**
     * Created by binzhang on 2019/3/16.
     */
    public class ArrayStack<E> implements Stack<E> { 
    
    	// 这里用的是我们自己定义的泛型数组，在数组篇中有写
        Array<E> array;
    
        public ArrayStack(int capacity){ 
            array = new Array<>(capacity);
        }
    
        public ArrayStack(){ 
            array = new Array<>();
        }
    
        @Override
        public int getSize() { 
            return array.getSize();
        }
    
        @Override
        public boolean isEmpty() { 
            return array.isEmpty();
        }
    
        public int getCapacity(){ 
            return array.getCapacity();
        }
    
        @Override
        public void push(E e) { 
            array.addLast(e);
        }
    
        @Override
        public E pop() { 
            return array.removeLast();
        }
    
        @Override
        public E peak() { 
            return array.getLast();
        }
    
        @Override
        public String toString() { 
            StringBuilder res = new StringBuilder();
            res.append("Stack: ");
            res.append("[");
            for (int i = 0 ; i < array.getSize() ; i ++){ 
                res.append(array.get(i));
                if(i != array.getSize() - 1)
                    res.append(", ");
            }
            res.append("] top");
            return res.toString();
        }
    }

测试类编写：

public class Main { 
    
        public static void main(String[] args) { 
    
            ArrayStack<Integer> stack = new ArrayStack<>();
    
            for (int i = 0 ; i < 5 ; i ++){ 
                stack.push(i);
                System.out.println(stack);
            }
    
            stack.pop();
            System.out.println(stack);
        }
    }

输出：

Stack: [0] top
    Stack: [0, 1] top
    Stack: [0, 1, 2] top
    Stack: [0, 1, 2, 3] top
    Stack: [0, 1, 2, 3, 4] top
    Stack: [0, 1, 2, 3] top

## 栈的时间复杂度 ##

ArrayStack

*  void push(e) O(1) 均摊
 *  E pop() O(1) 均摊
 *  E peek() O(1)
 *  int getSize() O(1)
 *  boolean isEmpty() O(1)

## 栈的应用 ##

*  undo操作-编辑器
 *  系统调用栈-操作系统
 *  括号匹配-编译器

## 使用栈解决有效的括号问题（LeetCode第二十号问题） ##

*  **题目描述**
    
    给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串，判断字符串是否有效。  
    有效字符串需满足：  
    左括号必须用相同类型的右括号闭合。  
    左括号必须以正确的顺序闭合。  
    注意空字符串可被认为是有效字符串。
 *  **示例**
    
        示例 1:
        输入: "()"
        输出: true
        
        示例 2:
        输入: "()[]{}"
        输出: true
        
        示例 3:
        输入: "(]"
        输出: false
        
        示例 4:
        输入: "([)]"
        输出: false
        
        示例 5:
        输入: "{[]}"
        输出: true
    
    > 栈顶元素反应了在嵌套的层次关系中，最近的需要匹配的元素
 *  解答代码
    
        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;
                        char topChar = stack.pop();
                        if (c == ')' && topChar != '(')
                            return false;
                        if (c == ']' && topChar != '[')
                            return false;
                        if (c == '}' && topChar != '{')
                            return false;
                    }
                }
                return stack.isEmpty();
            }
        
            public static void main(String[] args) { 
                System.out.println((new Solution()).isValid("{}[]()")); // true
                System.out.println((new Solution()).isValid("([)]"));   // false
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]: /images/20220306/23cb1945879f483ead033276e91a2b19.png