数据结构与算法-栈篇

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

简介:

栈是一种数据结构,它是一种先进后出(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 AAAAAAAAAAAAAAAAAAAAA

在上述代码中,我们实现了栈的创建。其中包括 入栈、出栈、判断栈空、访问栈顶  的函数方法,

通过这段代码,我们可以实现栈的创建和使用,下面我们就来简单介绍一下典型的括号匹配问题。

前言:

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

代码实现:

 
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)

解析:

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

总结:

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

相关文章
|
17天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
11天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
17天前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
|
2天前
|
算法 Java 开发者
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
6 0
|
2天前
|
存储 算法 Java
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
7 0
|
6天前
|
API
用栈翻转字符串
用栈翻转字符串
11 0
|
6天前
|
JavaScript
数据结构(用 JS 实现栈和队列【三种方式】)
数据结构(用 JS 实现栈和队列【三种方式】)
14 0
|
10天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
11天前
|
算法
数据结构与算法:栈与队列
数据结构与算法:栈与队列
|
14天前
|
存储 算法 调度
算法与数据结构-栈篇
算法与数据结构-栈篇
13 0