数据结构与算法(四)栈

老沙

发布于 2019-10-09 19:04:21

4280

发布于 2019-10-09 19:04:21

文章被收录于专栏：老沙课堂

概念

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

由于栈的特性为先进后出所以称之为First In Last Out 简称FILO

栈pop和push

有效括号（leetCode 20题）

题目

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/valid-parentheses

解题思路

我们吧( [ {定义为统称为左括号

我们吧) ] }定义为统称为右括号

•给定字符串"({[]]})"; 如果发现是左面括号就入栈。一直到发现是右括号•当为右括号就把栈顶元素pop出来，如果和右括号匹配就继续，否则返回false•如果遍历字符串到最后栈为空，就返回true 否则就为false

有效括号

private static HashMap<Character, Character> map = new HashMap<Character, Character>();static {  map.put('(', ')');  map.put('[', ']');  map.put('{', '}');}
public boolean isValid(String s) {  int length = s.length();  Stack<Character> stack = new Stack<>();  for (int i = 0; i < length; i++) {    Character character = s.charAt(i);
    if (map.containsKey(character)) {      stack.push(character);    } else {      if (stack.isEmpty()) {        return false;      }      if (character != map.get(stack.pop())) {        return false;      }    }  }  if (stack.isEmpty()) {    return true;  }  return false;}

时间复杂度

因为需要遍历字符串长度为n 所以时间复杂度为O(n);

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-09-30，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自老沙说点事微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度