数据结构与算法-栈篇

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

简介:

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

解析:

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

总结:

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

目录
打赏
0
3
3
0
37
分享
相关文章
|
3月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
343 9
|
3月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
55 1
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
144 77
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
47 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
39 7
【算法】栈
栈相关算法题,供参考,附有链接地址及板书
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
100 5
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
116 21

热门文章

最新文章

  • 1
    局域网屏幕监控系统中的Python数据结构与算法实现
    133
  • 2
    2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
    49
  • 3
    2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    46
  • 4
    2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    50
  • 5
    2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    54
  • 6
    2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    40
  • 7
    2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    72
  • 8
    2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    39
  • 9
    2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    46
  • 10
    2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    44