数据结构与算法-Python实现(二)栈
程序员文章站
2022-03-29 08:20:12
...
一、线性结构(Linear Structure)
概念:线性结构是一种有序数据项的集合,除了第一个元素没有前驱,最后一个没有后继新都数据项加入到数据集中时,只会加入到原有某个数据项之前或者之后,具有这种性质到数据集,就称为线性结构;常见的线性结构有:线性表,栈,队列,双队列,数组等,不同线性结构的关键区别在于数据项增减的方式。
二、栈 (Stack)
- 什么是栈?栈是一种有次序的数据项集合,在栈中,数据项的加入和移除都仅发生在同一端,这一端叫 “顶 top”,另一端叫 “底 base”,距离栈底越近都数据项,留在栈中都时间越长,既:新加入都数据会最先被移除,这种次序通常称为:后进先出(Last in First out)
- 使用 Python 自己实现一个 “栈”
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
"""
判断“栈”是否为空
"""
return self.items == []
def size(self):
"""
返回”栈“的大小
"""
return len(self.items)
def push(self, item):
"""
向栈里添加数据
"""
self.items.append(item)
def peek(self):
"""
返回“栈”最顶端数据,不做修改或删除
"""
return self.items[len(self.items) - 1]
def pop(self):
"""
从栈顶取出一个数据
"""
return self.items.pop()
使用Python面向对象编程配合列表可以很容易实现 “栈” 的数据结构
- 使用栈做案例:识别括号,有许多编程语言都来依据括号来判断作用域的,我们现在要做的案例就是基于栈准确识别括号的程序,例如:(()()())✔️ ((())❌ Stack() 调用的是上面实现栈的代码,案例如下:
def par_check(par_string):
"""
识别括号格式是否正确
:param par_string:
:return:
"""
S, balanced, index = Stack(), True, 0
while index < len(par_string) and balanced:
symbol = par_string[index]
if symbol == "(":
S.push(symbol)
else:
if S.isEmpty():
balanced = False
else:
S.pop()
index += 1
if balanced and S.isEmpty():
return True
else:
return False
print(par_check("((()))"))
print(par_check("(()))"))
- 使用栈来做十进制转换:
- 二进制概述:我们日常生活中使用的是十进制,而计算机中全部采用的是二进制只有:0、1两个数,逢二进一
- 将十进制转换为二进制,下面的例子数将12转换为二进制,整除二取余数:12 / 2 = 6 余数为 0、6 / 2 = 3 余数为0、3 / 2 = 1 余数为1、1 / 2 = 1 余数为1;12的二进制结果为:1100 我们发现先计算出来的数,最后取出,刚好符合栈的结构,下面我们使用栈来实现一个二进制转换函数
- 十进制转换二进制代码实现(结合刚才实现的Stack):
def divide_by2(dec_num):
S = Stack()
while dec_num > 0:
S.push(dec_num % 2)
dec_num = dec_num // 2
return int("".join([str(S.pop()) for i in range(S.size())]))
print(divide_by2(12))
- 十进制转换十六进制以下任意进制代码(原理都一样接着来尝试吧):
def base_converter(dec_num, base):
digits = "0123456789ABCDEF"
stack = Stack()
while dec_num > 0:
stack.push(dec_num % base)
dec_num = dec_num // base
return "".join([str(digits[stack.pop()]) for i in range(stack.size())])
print(base_converter(233, 16))
上一篇: 森林合成表大全(森林全物品合成表一览)