算法与数据结构-栈篇

简介: 算法与数据结构-栈篇

简介:

栈是一种数据结构,它是一种先进后出(FILO)的有序集合。栈可以理解为一个容器,只能在一端进行插入和删除操作,栈可以看作是一种特殊的线性表,只能在表的一端进行插入和删除操作,这一端被称为栈顶。栈的基本操作包括压栈(push)和出栈(pop),压栈是向栈顶插入元素,出栈是从栈顶删除元素。除此之外,栈还有其他操作,如获取栈顶元素(top)、判断栈是否为空(isEmpty)等。

用途:

栈常用于解决递归问题、表达式求值、括号匹配等场景。在计算机科学中,栈的应用非常广泛,比如函数调用栈用于存储函数的局部变量和返回地址,操作系统的进程调度也会使用栈来保存进程的上下文信息等。因此,了解和掌握栈的基本概念和操作是非常重要的。下面给出栈的代码实现:

class Stack:
    class _Node:
        def __init__(self, data, addr=None):
            self.data=data
            self.next=addr
 
    def __init__(self):
        self._head=self._Node(0) # 有效元素为0,所以头为0
    
    def __len__(self):
        return self._head.data
    
    def is_empty(self):
        return self._head.data==0
    
    def push(self, value): #头部 是栈顶
        # if self.is_empty(self):
        #     self._head.next=value
        #     return self
        node = self._Node(value,self._head.next)
        self._head.next=node
        self._head.data+=1
    
    def pop(self):
        if self.is_empty(): raise ValueError('值不存在!')
        l=self._head.next.data
        self._head.next=self._head.next.next
        self._head.data-=1
        return l
    
    def peek(self):  # 返回 第一个值
        if self.is_empty(self): raise ValueError('值不存在!')
        return self._head.next.data 

通过以上代码我们成功创建了栈,其中包括 入栈、出栈、判断栈空、访问栈顶元素 等方法。接下来,我们通过栈这一数据结构来解决一下典型的括号匹配问题。

描述:

栈常用于解决括号匹配问题。在括号匹配问题中,我们需要判断一个字符串中的括号是否匹配,即每个左括号都有相应的右括号与之匹配,并且括号的嵌套关系也必须正确。例如,字符串 "({[]})" 是一个合法的括号序列,而字符串 "({[})" 则是一个不合法的括号序列。

下面附上解题代码:

def init():
    line = input("输入表达式(每个符号以空格间隔)")
    chs = line.split(" ")  # 返回一个字符串 列表
    return chs
 
def calc_once(op_stack, opr_stack):
    # 对应求解过程的第三步
    op=op_stack.pop() # 拿操作符
    op_stack.pop() # 扔掉左括号
    a=opr_stack.pop() #拿元素
    b=opr_stack.pop() # 另一个元素
    res = eval(f"{b}{op}{a}")  # 字符串 用eval函数计算出来
    opr_stack.push(res)
    
def calc(chs):
    ls = ["+", "-", "*", "/", "("]
    op_stack = Stack()  # 符号栈
    opr_stack = Stack()  # 数字栈
    for item in chs:
        if item in ls:
            op_stack.push(item)
        elif item == ")":
            calc_once(op_stack,opr_stack) 
        else:
            opr_stack.push(item)
    return opr_stack.pop()
 
if __name__ == "__main__":
    while True:
        chs = init()
        if chs == ["exit"]: break
        result = calc(chs)
        print(result)
 

解析:

解决括号匹配问题的一种常见方法是使用栈。我们可以遍历字符串,当遇到左括号时,将其压入栈中;当遇到右括号时,判断栈顶元素是否与其匹配的左括号,如果匹配则将栈顶元素出栈,否则说明括号不匹配。最终,如果栈为空且所有括号都匹配,则说明括号序列是合法的。

总结:

通过使用栈来解决括号匹配问题,我们可以有效地检查括号序列的合法性,避免手动逐个匹配括号带来的复杂性。这种方法在编程中经常被使用,可以帮助我们快速准确地判断括号序列的正确性。

目录
相关文章
|
2月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
66 1
|
2月前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
155 4
|
8天前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
124 75
|
8天前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
33 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
8天前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
33 9
|
8天前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
26 7
|
8天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
30 2
|
24天前
|
存储 运维 监控
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
56 20
|
22天前
|
算法
【算法】栈
栈相关算法题,供参考,附有链接地址及板书
|
2月前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等