小码哥《恋上数据结构与算法》笔记（五）：栈

我就是我 2023-07-24 08:07 32阅读 0赞

> 具体代码在 [Stack][] , 欢迎 `star`

## 目录 ##

*  一、栈（Stack）
 *  二、栈接口设计
 *  三、栈的实现
 *  四、实现细节
 *  五、双向链表和动态数组比较
    
     *  1、有效的括号
     *  [2、括号的分数][2]
     *  [3、基本计算器][3]
     *  [4、逆波兰表达式求值][4]

--------------------

# 一、栈 #

跳转到目录

*  栈是一种特殊的`线性表`, 只能在`一端`进行操作。
 *  往栈中`添加`元素的操作，一般叫做`push`，入栈。
 *  从栈中`移除`元素的操作，一般叫做`pop`，出栈(只能`移除栈顶`的元素)。
 *  栈的内部实现可以使用`动态数组`或`链表`实现。
 *  栈的主要操作是在`栈顶`添加或删除元素。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]

# 二、栈的接口设计 #

跳转到目录

public class Stack<E> { 
        // 使用动态数组实现栈
        private List<E> list = new ArrayList<>();
        // 元素的数量
        public int size();
        // 是否为空
        public boolean isEmpty();
        // 入栈
        public void push(E element);
        // 出栈
        public E pop();
        // 获取栈顶元素
        public E top();
    }

> 栈的内部实现可以使用`动态数组`或`链表`。

# 三、栈的实现 #

跳转到目录

*  使用`动态数组`实现栈(组合关系)。

public class Stack<E> { 
        // 使用 动态数组存储数组
        private ArrayList<E> list;
        
        public Stack() { 
            // 初始化方法中创建列表
        	this.list = new ArrayList<>();
        }
        
        public int size() { 
        	// 栈中元素数量, 就是列表中存储的元素数量
        	return list.size();
        }
        
        public void clear() { 
        	// 清空栈, 就是清空列表
        	list.clear();
        }
        
        public boolean isEmpty() { 
        	// 栈是否空, 就是列表是否空
        	return list.isEmpty();
        }
        
        public void push(E element) { 
        	// 入栈, 将元素添加到列表的最后面
        	list.add(element);
        }
        
        public E pop() { 
        	// 出栈, 将列表中最后一个元素删除并返回
        	return list.remove(list.size() - 1);
        }
        
        public E top() { 
        	// 查看栈顶元素, 就是查看列表中的最后一个元素
        	return list.get(list.size() - 1);
        }
    }

# 四、实现细节 #

跳转到目录

*  1、因为栈是`线性结构`,许多特点和动态数组和链表是`相同`的, 这里可以`继承`ArrayList来实现栈。
 *  2、因为使用了继承ArrayList, 所以栈就拥有了动态数组的所有方法,这样明显是不合理的~(官方的栈是继承`Vector`(安全的ArrayList)); 可以使用和ArrayList变为`组合`关系。

# 五、leetcode算法题 #

跳转到目录

##### 1、[有效的括号][Link 1] #####

跳转到目录  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]

public class _20_有效的括号 { 
        // {[()]}
    
    	
        public boolean isValid3(String s) { 
            Stack<Character> stack = new Stack<>();
            for (char c : s.toCharArray()) { 
                if (c == '(')
                    stack.push(')');
                else if (c == '[')
                    stack.push(']');
                else if (c == '{')
                    stack.push('}');
                else if (stack.isEmpty() || c != stack.pop())
                    return false;
            }
            return stack.isEmpty();
        }
    
        // --------------------------------------------
        
        // 因为下面的操作是在做,左右对应的关系(一对一),可以采用map方式来将左右括号对应起来
        private static Map<Character, Character> map = new HashMap<>();
    
    	/* 静态代码块: 随着类的加载而执行,该代码块中如果要使用map, 该map对象必须静态修饰的,这也是一种初始化的方式 */
        static { 
            map.put('{', '}');
            map.put('[', ']');
            map.put('(', ')');
        }
    
        // 优化方法1
        public static boolean isValid(String s) { 
            Stack<Character> stack = new Stack<>();
            int len = s.length();
            for (int i = 0; i < len; i++) { 
                char c = s.charAt(i);
                if (map.containsKey(c)) {    // 左括号
                    stack.push(c);
                } else {     // 右括号
                    if (stack.isEmpty()) return false;
                    char left = stack.pop();
                    if (map.get(left) != c) return false;
                }
            }
            return stack.isEmpty();
        }
    
        // --------------------------------------------
    
        public static boolean isValid1(String s) { 
            // 方法1
            Stack<Character> stack = new Stack<>();
            int len = s.length();
            // 遍历给定的字符串的字符
            for (int i = 0; i < len; i++) { 
                char c = s.charAt(i); // 拿出字符串的字符
                // 遍历左字符(左括号)
                if (c == '{' || c == '[' || c == '(') { 
                    // 将左字符入栈
                    stack.push(c);
                } else { 
                    // 右括号
                    if (stack.isEmpty()) return false; // 说明没有左括号入栈,直接false
                    // 如果出现右括号,则弹出栈顶字符,和右括号作匹配
                    char left = stack.pop();
                    if (left == '{' && c != '}') return false;
                    if (left == '[' && c != ']') return false;
                    if (left == '(' && c != ')') return false;
                }
            }
            // 判断完之后,看栈是否为空,若为空则说明是有效括号
            return stack.isEmpty();
        }
    
        // --------------------------------------------
    
        // 方法2
        public static boolean isValid2(String s) { 
            while (s.contains("{}") || s.contains("[]") || s.contains("()")) { 
                s = s.replace("{}", "");
                s = s.replace("[]", "");
                s = s.replace("()", "");
            }
            return s.isEmpty();
        }
    
        public static void main(String[] args) { 
            System.out.println(isValid1("{[()]}"));
        }
    }

[Stack]: https://github.com/coderZYGui/stack_structure
[2]: https://leetcode-cn.com/problems/score-of-parentheses/comments/
[3]: https://leetcode-cn.com/problems/basic-calculator/
[4]: https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]: /images/20230528/d09d208096cb4ccd8bb05f4b4bdbcde4.png
[Link 1]: https://leetcode-cn.com/problems/valid-parentheses/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]: /images/20230528/556330c6519f4f529c339cc732f73c26.png