章节
- 栈的特性 & 图示
- 栈的应用场景
- 构建一个栈
- 使用栈结构解决leetcode相关问题
1. 栈的特性 & 图示
栈是一种线性结构 相比数据，栈对应的操作是数组的子集 只能从一端add元素、get元素，这一端一般称之为栈顶 LIFO 后进先出
2. 栈的应用场景
2.1 undo 操作
比如撤销 "不法" 的输入操作
2.2 程序调用的系统栈
3. 构建一个栈
stack 基本操作包含以下5个操作api:
代码语言：javascript复制void push(obj) -> 入栈操作
obj pop() -> 弹出操作
obj peek() -> pick top 操作(获取栈顶元素)
int getSize() -> 获取栈元素num 操作
bool isEmpty() -> 判断栈是否为空操作
底层实现并不关心, 栈通过动态array(capacity 可以动态变化)实现即可，栈的操作是array的子集
example:
代码语言：javascript复制#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
# @Time : 2020/1/18 下午7:21
# @Author : bofengliu@tencent.com
# @Site :
# @File : Stack.py
# @Software: PyCharm
"""
from array.Array import Array
class Stack:
def __init__(self, capacity=None):
"""
:param capacity: 栈的容积
"""
if capacity is None:
self.array = Array()
else:
self.array = Array(capacity)
def push(self, val):
"""
向数组的末尾添加一个元素
:param val:
:return:
"""
self.array.add_last(val)
def pop(self):
"""
弹出栈顶的元素，其实是栈顶的元素, 并删除
:return:
"""
return self.array.remove_last()
def peek(self):
"""
获取栈顶的元素，其实是数组的末尾元素
:return:
"""
return self.array.get_last()
def get_size(self):
return self.array.get_size()
def is_empty(self):
return self.array.is_empty()
def get_capacity(self):
return self.array.get_capacity()
def to_string(self):
res_str_stack = []
res_str_stack.append('Stack: [')
for i in range(0, self.array.get_size()):
val = self.array.get(i)
if isinstance(val, int):
val = str(val)
res_str_stack.append(val)
if i != self.array.get_size() - 1:
res_str_stack.append(',')
res_str_stack.append('] top')
return "".join(res_str_stack)
if __name__ == '__main__':
# 1. 构建一个栈
stack = Stack(10)
for i in range(0, 5):
stack.push(i)
print(stack.to_string())
stack.pop()
print(stack.to_string())
4. 使用栈解决相关问题
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
# @Time : 2020/2/4 下午3:29
# @Author : bofengliu@tencent.com
# @Site :
# @File : Solution.py
# @Software: PyCharm
"""
from stack.Stack import Stack
class Solution:
def __init__(self):
pass
def is_valid(self, s):
array_stack = Stack()
str_list = list(s)
for index, char in enumerate(str_list):
if char == '(' or char == '{' or char == '[':
array_stack.push(char)
else:
if array_stack.is_empty():
return False
top_char = array_stack.pop()
if char == ')' and top_char != '(':
return False
if char == ']' and top_char != '[':
return False
if char == '}' and top_char != '{':
return False
return array_stack.is_empty()
if __name__ == '__main__':
solution = Solution()
valid_str = '}[['
print(solution.is_valid(valid_str))
valid_str = '{}'
print(solution.is_valid(valid_str))
valid_str = '{[]}'
print(solution.is_valid(valid_str))
