数据结构小记【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.techiedelight.com/zh/stack-implementation-python