常用数据结构之Stack(栈)

╰半夏微凉° 2022-12-10 07:28 173阅读 0赞

# 1.理论介绍 #

上一篇中我们介绍了[数据结构中的堆][Link 1]，常言道堆栈不分家，我们继续来聊聊栈这种数据结构吧。栈从本质上来讲是一种有着特殊要求的线性表，感兴趣的可以了解一下之前讲的[数据结构中的线性表][Link 2]。既然是线性表那么其就有两种形式，一种是线性存储(像数组一样是一块连续的内存空间)，另外一种是链式存储(像链表一样是一段非连续的空间)；

栈的特殊要求就是LIFO(Last In First Out)，对，后进先出。只有栈顶的元素允许访问。还记得上一篇讲的堆吗？从本质上来讲堆也是只有顶部的元素是经常使用的。但是堆是一种基于值大小的顶部弹出，而栈是一种基于时间顺序的顶部弹出(所谓的顶部就是最后时刻元素)；一般来说内存中的栈，也使用栈的思想来实现。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70][]

# 2.代码实现 #

本文中我们使用python中的列表来实现一个栈，基本思路就是没插入一个元素的时候直接append到列表尾部，弹出元素的时候直接使用pop方法返回并删除尾部元素。所以其插入的时间复杂度为O(1),弹出的时间复杂度为O(n).

#-*- coding:utf-8 -*-
    class Stack(object):
        def __init__(self):
            self.array = []
        #弹出栈顶的元素
        def pop(self):
            #pop方法默认弹出最后一个元素
            return  self.array.pop()
        #查看栈顶的元素
        def peek(self):
            return self.array[-1]
        #入栈,插入到最后一位
        def push(self,v):
            self.array.append(v)
        #查看栈的大小
        def get_size(self):
            return len(self.array)
        #判断栈是否 为空
        def is_empty(self):
            return self.array == []

# 3.判断括号是否匹配 #

栈结构常用的场景之一就是判断左括号和右括号是否匹配，我们的实现思路如下：如果是左括号就入栈，如果是右括号就将栈顶的左括号弹出；最后如果栈为空的话，那么说明左括号和右括号的数量是匹配的；如果先出现右括号那么栈中此时为空，判断为不匹配。

当然除了括号匹配之外，我们还可以做很多的匹配工作，本篇以此为例！

def balance(str):
        stack = Stack()
        for i,v in enumerate(str):
            if v == '(':
                stack.push(v)
            elif v == ')':
                if stack.is_empty():
                    return False
                else:
                    stack.pop()
        return stack.is_empty()
    str = '()))'
    print(balance(str))

# 4.总结 #

本篇讲述了常用数据结构中的栈，数据结构就是一种思想，为了特定的任务而设计的一种结构。栈的思想就是后进先出，其入栈时间复杂度为O(1),出栈的时间复杂度为O(n),因为弹出栈顶的元素，其它元素的位置都需要进行改变。

# 5.好诗推荐 #

不向长安路上行。却教山寺厌逢迎。味无味处求吾乐，材不材间过此生。  
宁作我，岂其卿。人间走遍却归耕。一松一竹真朋友，山鸟山花好弟兄。

《鹧鸪天·博山寺作》辛弃疾

快来！一起跳支舞吧！

[Link 1]: https://blog.csdn.net/gaobing1993/article/details/108768791
[Link 2]: https://blog.csdn.net/gaobing1993/article/details/108666410
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70]: /images/20221123/f4310b99510b49b9bba5efd113238556.png