专栏首页T客来了打牢地基-栈篇

打牢地基-栈篇

章节

  • 栈的特性 & 图示
  • 栈的应用场景
  • 构建一个栈
  • 使用栈结构解决leetcode相关问题

1. 栈的特性 & 图示

栈是一种线性结构 相比数据,栈对应的操作是数组的子集 只能从一端add元素、get元素,这一端一般称之为栈顶 LIFO 后进先出

2. 栈的应用场景

2.1 undo 操作

比如撤销 "不法" 的输入操作

2.2 程序调用的系统栈

3. 构建一个栈

stack 基本操作包含以下5个操作api:

void  push(obj) -> 入栈操作
 
obj pop() -> 弹出操作
 
obj peek() -> pick top 操作(获取栈顶元素)
 
int getSize() -> 获取栈元素num 操作
 
bool isEmpty() -> 判断栈是否为空操作
 

底层实现并不关心, 栈通过动态array(capacity 可以动态变化)实现即可,栈的操作是array的子集

example:

#!/usr/bin/env python
 
# -*- coding: utf-8 -*-
 
"""
 
# @Time    : 2020/1/18 下午7:21
 
# @Author  : bofengliu@tencent.com
 
# @Site    :
 
# @File    : Stack.py
 
# @Software: PyCharm
 
"""
 
from array.Array import Array
 


 


 
class Stack:
 
 def __init__(self, capacity=None):
 
 """
 
        :param capacity: 栈的容积
 
        """
 
 if capacity is None:
 
            self.array = Array()
 
 else:
 
            self.array = Array(capacity)
 


 
 def push(self, val):
 
 """
 
        向数组的末尾添加一个元素
 
        :param val:
 
        :return:
 
        """
 
        self.array.add_last(val)
 


 
 def pop(self):
 
 """
 
        弹出栈顶的元素,其实是栈顶的元素, 并删除
 
        :return:
 
        """
 
 return self.array.remove_last()
 


 
 def peek(self):
 
 """
 
        获取栈顶的元素,其实是数组的末尾元素
 
        :return:
 
        """
 
 return self.array.get_last()
 


 
 def get_size(self):
 
 return self.array.get_size()
 


 
 def is_empty(self):
 
 return self.array.is_empty()
 


 
 def get_capacity(self):
 
 return self.array.get_capacity()
 


 
 def to_string(self):
 
        res_str_stack = []
 
        res_str_stack.append('Stack: [')
 
 for i in range(0, self.array.get_size()):
 
            val = self.array.get(i)
 
 if isinstance(val, int):
 
                val = str(val)
 
            res_str_stack.append(val)
 
 if i != self.array.get_size() - 1:
 
                res_str_stack.append(',')
 
        res_str_stack.append('] top')
 
 return "".join(res_str_stack)
 


 


 
if __name__ == '__main__':
 
 # 1. 构建一个栈
 
    stack = Stack(10)
 
 for i in range(0, 5):
 
        stack.push(i)
 
 print(stack.to_string())
 


 
    stack.pop()
 
 print(stack.to_string())
 

4. 使用栈解决相关问题

#!/usr/bin/env python
 
# -*- coding: utf-8 -*-
 
"""
 
# @Time    : 2020/2/4 下午3:29
 
# @Author  : bofengliu@tencent.com
 
# @Site    :
 
# @File    : Solution.py
 
# @Software: PyCharm
 
"""

 
from stack.Stack import Stack
 
class Solution:
 
 def __init__(self):
 
 pass

 
 def is_valid(self, s):
 
        array_stack = Stack()
 
        str_list = list(s)
 
 for index, char in enumerate(str_list):
 
 if char == '(' or char == '{' or char == '[':
 
                array_stack.push(char)
 
 else:
 
 if array_stack.is_empty():
 
 return False
 
                top_char = array_stack.pop()
 
 if char == ')' and top_char != '(':
 
 return False
 
 if char == ']' and top_char != '[':
 
 return False
 
 if char == '}' and top_char != '{':
 
 return False

  return array_stack.is_empty()
  
if __name__ == '__main__':
 
    solution = Solution()
 
    valid_str = '}[['
 
 print(solution.is_valid(valid_str))

 
    valid_str = '{}'
 
 print(solution.is_valid(valid_str))
 
 
    valid_str = '{[]}'
 
 print(solution.is_valid(valid_str))

本文分享自微信公众号 - T客来了(ltdo11),作者:bofeng

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打牢地基-链表

    注意: 关键点: 找到要插入节点的前一个节点 LinkedList - (head实现)

    用户1081422
  • 打牢地基-队列

    数组队列 dequeue 的时间复杂度是 o(n) ,因每次删除队首元素,后面的元素都得进行前移操作 使用循环队列可以将dequeue的时间复杂度降至o(1)

    用户1081422
  • 打牢地基-二叉树、BST

    二分搜索树-BTS 加速查询过程的原因,假如根节点val = 28, 现在在查找 30 这个元素,因为BTS的存储特性,只需要查找右子树部分就可以了,大大提高了...

    用户1081422
  • 打牢地基-拿下红黑树

    红黑树与2-3树的等价关系,理解2-3树和红黑树之间的关系 红黑树就很简单了 学习2-3树不仅对理解红黑树有帮助,对于理解B类树,也是有巨大帮助的:

    用户1081422
  • 打牢地基-映射的底层实现(LinkedListMap、BSTMap)

    注意:设置了 getnode 辅助函数, contains()、get()、set() 都会用的到

    用户1081422
  • 【编程基础】盖大楼地基要牢固

    水之积也不厚,则其负大舟也无力。——庄子 上一篇讲了几个编译编辑器,大家都可以用用,新手掌握几个是没有坏处的。 学编程要从基础学起,就像盖大楼,先把地基打好,...

    程序员互动联盟
  • 握草,你竟然在代码里下毒!

    除了有点味道以外,这回是不记住了,我们编程写代码的过程和我们日常生活的例子,往往都是这样可以对应上,有了真实可以触及的实物,再去了解编程就会更加容易,也很难忘记...

    小傅哥
  • 打牢算法基础,从动手出发!

    大家好,我是光城。算法在计算机领域的重要性,就不用我多说了,每个人都想要学算法,打牢算法基础,可是不知道如何做,今天我来推荐一波学习思路。

    公众号guangcity
  • 2019 我的 Github 开源之路!

    转眼间2019即将过去,回想这一年,学习了很多也输出了很多。如果要说我最大的成果的话,我的Github可以概括下。这一年之中累计收获了3w+Star,总计开源维...

    macrozheng
  • 【连载】两百行Rust代码解析绿色线程原理(三)栈

    这一点很重要。计算机只有内存,它没有特殊的“栈”内存和“堆”内存,它们都是同一个内存的某一部分。

    MikeLoveRust
  • Python打牢基础,从12个语法开始!

    Python简单易学,但又博大精深。许多人号称精通Python,却不会写Pythonic的代码,对很多常用包的使用也并不熟悉。学海无涯,我们先来了解一些Pyth...

    小小詹同学
  • 握草,你竟然在代码里下毒!

    除了有点味道以外,这回是不记住了,我们编程写代码的过程和我们日常生活的例子,往往都是这样可以对应上,有了真实可以触及的实物,再去了解编程就会更加容易,也很难忘记...

    小傅哥
  • 【小家java】final修饰的变量真的不可变吗?

    这可能是大家的一个共识:如果我们希望这个变量不可变,我们可以用final进行修饰。但本篇将带你深入了解不变的含义,我相信可以让你更深的了解final的原理,也能...

    YourBatman
  • scrapy遇上ajax,抓取QQ音乐周杰伦专辑与歌词

    zone同学最近在上线小程序好久没写文章了,他说早就手痒痒了,所以挤出时间写了这篇,这是下面这五篇文章的连载文章:

    小小詹同学
  • 大牛带你打牢Python基础,看看这10语法

    都说Python简单,易懂,但是有时候却又很深奥,许多人都觉的自己学会了,却老是写不出项目来,对很多常用包的使用也并不熟悉。学海无涯,我们先来了解一些Pytho...

    一墨编程学习
  • 梦凡&粉丝---问题交流第一期

    因为「函数调用传递实参」,「函数体内通过形参拷贝实参数据」,并且形参只在函数体内存在,出了函数就被释放掉了

    DeROy
  • 给大家推荐一个PHP学习路线

    俗话说PHP是世界上最好的语言,哈哈,给大家开个玩笑。PHP作为一门编程语言,学会的话并不难。如果只去了解基础使用的话1、2天,想更深入的学习的话就需要更多的时...

    学长冷月
  • 美军网络安全 | 第3篇:JIE联合区域安全栈JRSS

    “美军网络安全”系列第一篇(美军网络安全 | 开篇:JIE(联合信息环境)概述)介绍了美军JIE(联合信息环境)的总体情况。其主要目标是实现“三个任意”的愿景—...

    网络安全观
  • Google 鼓励的 13 条代码审查标准,建议收藏!

    在本文中,我们将简要介绍13条代码审查标准,希望能够通过这些标准极大地帮助改善软件的质量,同时让开发人员保持心情愉悦。

    Java技术栈

扫码关注云+社区

领取腾讯云代金券