数据结构小记【Python/C++版】——栈篇

一,基础概念

栈是一种存放数据的线性结构容器,栈中的数据元素只能在同一端进行添加和删除等操作。
栈中被用来进行数据读写的一端被称作栈顶,无法进行任何操作的另一端被称为栈底。
元素在栈中的移动顺序依照后进先出(LIFO)原则,较早入栈的元素,更接近栈底,更晚被弹出。
栈结构在生活中的抽象模型有:酒店堆起来的盘子,书架上堆起来的书等,都是从最顶部开始取走和放回的。

二,栈的图示结构

图片

三,栈的常见操作

push: 入栈操作,将数据从栈顶压入。

pop: 出栈操作,从栈顶弹出数据。

peek: 返回栈顶的数据而不删除它。

size: 返回栈中数据的数量。

isEmpty: 检查栈是否为空。

isFull: 检查栈是否已满。

四,栈的代码实现

1.Python语言实现

方式1.使用Python内置数据类型实现:

list, collections.deque, queue.LifoQueue

方式2.封装Stack类来实现

Demo.01:  基于list实现

stack = []

Demo.02:  基于deque实现

from collections import deque
stack = deque()

Demo.03:  基于LifoQueue实现

from queue import LifoQueue

stack = LifoQueue(maxsize=3)
print(stack.qsize())

Demo.04:  封装Stack类来实现

class Stack:
    

运行结果:

Inserting 1 into the stack…
Inserting 2 into the stack…
Removing 2 from the stack
Removing 1 from the stack
Inserting 3 into the stack…
Inserting 4 into the stack…
Top element is 4
The stack size is 2
Removing 4 from the stack
The stack is not empty

2.C++语言实现


方式1.基于STL标准库自带的std::stack进行实现
方式2.封装一个Stack类来实现


Demo.01:  基于std::stack实现

}


Demo.02:  封装Stack类来实现


运行结果:

The Stack Push
2
4
6
The Stack Pop :
6
4
2

五,栈的应用场景

1.表达式解析,对表达式的前缀/后缀进行出栈/入栈操作来解析表达式的内容。
2.程序运行记录跟踪,比如在Web浏览器中,每访问一个新页面时,URL被添加到栈中,当点击后退按钮时,栈中弹出以前的URL。
3.实现其他更复杂的数据结构,比如树和图。


简单应用案例
1.场景:
编写一个算法,从左到右读取字符串中所有的括号字符,判断其中的括号是否都能互相匹配。

2.实现步骤:
 
step.1:
新建一个空的栈。
step.2:
从左往右依次读取括号字符,如果遇到左括号,调用push将字符压入堆栈,如果遇到右括号,调用pop弹出栈顶的字符。
step.3:
如果存在左括号与右括号不匹配,结束时,栈中数据不为空。如果所有的左括号与右括号匹配,结束时,栈中的数据是空的。


3.Python代码实现:
class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.insert(0, item)

    def pop(self):
        return self.items.pop(0)

    def peek(self):
        return self.items[0]

    def size(self):
        return len(self.items)

def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol == “(“:
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()
        index = index + 1

    if balanced and s.isEmpty():
        return True
    else:
        return False

if __name__ == ‘__main__’:
    test_st1 = “((()))”
    print(“The check result is :”, parChecker(test_st1))
    test_st2 = “((())”
    print(“The check result is :”, parChecker(test_st2))


运行结果:

The check result is : True
The check result is : False

六,参考阅读

https://www.geeksforgeeks.org/stack-in-python

https://www.techiedelight.com/zh/stack-implementation-python

声明:文中观点不代表本站立场。本文传送门:https://eyangzhen.com/206817.html

(0)
联系我们
联系我们
分享本页
返回顶部