栈的定义

栈是一种遵循后进先出（Last In First Out，LIFO）原则的抽象数据类型。想象一下餐厅里一摞盘子，你最后放上去的盘子会被最先拿走，这就是栈的工作方式。在编程中，栈常用于存储和管理数据，它提供了一种有序的方式来处理数据项。

栈的基本操作

1. Stack()：创建一个空栈，不包含任何数据项。这就像是准备一个空的盘子架子，等待着盘子被放上去。
2. push(item)：将 item 加入栈顶，无返回值。当你把一个盘子放在一摞盘子的最上面时，就类似于在栈中执行 push 操作。
3. pop()：将栈顶数据项移除，并返回，栈被修改。这就如同从盘子堆中拿走最上面的那个盘子，同时盘子堆的状态也发生了改变。
4. peek()：“窥视” 栈顶数据项，返回栈顶的数据项但不移除，栈不被修改。就像你看一眼最上面的盘子是什么，但不拿走它。
5. isEmpty()：返回栈是否为空栈。判断盘子架子上有没有盘子，就是这个操作的现实类比。
6. size()：返回栈中有多少个数据项。就像数一数盘子堆里一共有多少个盘子。

栈的应用场景

1. 表达式求值：在计算数学表达式时，栈可以用来处理运算符的优先级。例如，对于表达式 3 + 4 * 2，栈可以帮助我们正确地先计算乘法再计算加法。
2. 函数调用：当一个函数被调用时，它的参数、局部变量等信息都会被压入栈中。当函数执行完毕，这些信息会从栈中弹出，这保证了程序的正确执行顺序。
3. 深度优先搜索（DFS）：在图论和树的遍历算法中，栈可以用于实现深度优先搜索。它帮助我们沿着一条路径尽可能深地探索，直到无法继续，然后回溯。

栈操作	栈内元素	返回值
s = Stack()	[]	栈对象
s.isEmpty()	[]	True
s.push(5)	[5]	无
s.push('cat')	[5, 'cat']	无
s.peek()	[5, 'cat']	'cat'
s.push(10.5)	[5, 'cat', 10.5]	无
s.size()	[5, 'cat', 10.5]	3
s.isEmpty()	[5, 'cat', 10.5]	False
s.push('book')	[5, 'cat', 10.5, 'book']	无
s.pop()	[5, 'cat', 10.5]	'book'
s.pop()	[5, 'cat']	10.5
s.size()	[5, 'cat']	2

Python实现ADT Stack

class Stack:
    def __init__(self):
        """
        初始化一个空栈，使用列表来存储栈内元素
        """
        self.items = []

    def push(self, item):
        """
        将元素item压入栈顶
        :param item: 要压入栈的元素
        """
        self.items.append(item)

    def pop(self):
        """
        弹出栈顶元素并返回该元素
        如果栈为空，返回None
        """
        if self.isEmpty():
            return None
        return self.items.pop()

    def peek(self):
        """
        查看栈顶元素，但不弹出
        如果栈为空，返回None
        """
        if self.isEmpty():
            return None
        return self.items[-1]

    def isEmpty(self):
        """
        判断栈是否为空
        :return: 栈为空时返回True，否则返回False
        """
        return len(self.items) == 0

    def size(self):
        """
        返回栈中元素的数量
        """
        return len(self.items)

# 创建一个栈对象
stack = Stack()
# 测试push方法
stack.push(10)
stack.push(20)
# 测试peek方法
print(stack.peek())  # 输出: 20
# 测试pop方法
print(stack.pop())  # 输出: 20
# 测试isEmpty方法
print(stack.isEmpty())  # 输出: False
# 测试size方法
print(stack.size())  # 输出: 1

压栈（push）、弹栈（pop）、查看栈顶元素（peek）、判断栈是否为空（isEmpty）和获取栈的大小（size）

Python-十进制转换为二进制

进制即进位计数制，是人为定义的带进位的计数方法。

定义与原理

对于 X 进制，运算时每一位置上的数逢 X 进一位。比如，十进制是逢十进一，二进制是逢二进一，十六进制是逢十六进一。

常见进制及其特点、应用

• 十进制：是最通用的进制。有人认为其普遍使用源于人类有 10 根手指。分为无位值概念（如古希腊、古埃及和古印度的佉卢十进制和婆罗米十进制）和有位值概念（如中国古代算筹数、印度 - 阿拉伯数字及现代广泛使用的阿拉伯数字，最早使用有位值概念十进制的是中国）两类。不仅用于计数，在公制度量衡中也很重要，国际单位制采用的是十进制度量系统。
• 十二进制：来源有多种说法，如和一年十二次日月相会或人类一只手除去拇指外有十二指骨节点有关。12 是高合成数，因子多，在有些计算上比十进制方便。应用场景包括十二小时制、中国十二地支、黄道十二宫、英制度量衡（1 英尺 = 12 英寸 ）等。
• 二十进制：古玛雅文明和因纽特人采用，可能来源是十个手指加十个脚趾。曾应用于欧洲旧时货币换算，如法国 1 里弗尔 = 20 苏等。
• 六十进制：古巴比伦人使用，来源可能是 60 是 10 和 12 的最小公倍数，也是高合成数。至今应用于时间（1 小时 = 60 分钟，1 分钟 = 60 秒 ）、角度和地理坐标的记录与运算。
• 二进制：现代二进制思想由莱布尼兹在 1703 年提出，随着电子计算机诞生和发展而重要起来。因为计算机内部电子元件多以两种状态表示（如电路的通和断），所以二进制适合计算机数据存储和处理。
• 八进制与十六进制：为节约二进制书写空间而衍生。三位二进制数字可转换为一位八进制数字，四位二进制数字可转换为一位十六进制数字。常用于计算机领域，如表示内存地址、颜色编码等。

其他进制

各种度量衡中存在多种进制混用情况。如中国古代《汉书・律历志》记载的度量衡中，有十二进制、二十四进制、十六进制等；英国度量衡体系中也有多种进制。此外，互联网信息传输时会采用三十六进制（26 个英文字母 + 10 个数字构成 ）、六十二进制（大小写英文字母 + 10 个数字构成 ）、base64 编码（62 个符号加上 +、/ 构成 ）等大基数进制，可降低信息传输成本且具有可打印性，在生成短链、资源传输等方面有实用价值。

Python 实现不同进制之间的转换

十进制转其他进制

1. 手动实现转换函数

def decimal_to_base(decimal_num, base):
    # 用于存储转换后的结果
    result = ""
    digits = "0123456789ABCDEF"
    while decimal_num > 0:
        # 取余数
        remainder = decimal_num % base
        # 将余数对应的字符添加到结果字符串的前面
        result = digits[remainder] + result
        # 整除，更新商
        decimal_num = decimal_num // base
    if result == "":
        result = "0"
    return result

# 示例
decimal_num = 255
binary = decimal_to_base(decimal_num, 2)
octal = decimal_to_base(decimal_num, 8)
hexadecimal = decimal_to_base(decimal_num, 16)

print(f"十进制 {decimal_num} 转换为二进制是: {binary}")
print(f"十进制 {decimal_num} 转换为八进制是: {octal}")
print(f"十进制 {decimal_num} 转换为十六进制是: {hexadecimal}")

2. 使用 Python 内置函数

decimal_num = 255
# bin() 函数将十进制转换为二进制，会以 '0b' 开头
binary = bin(decimal_num)[2:]
# oct() 函数将十进制转换为八进制，会以 '0o' 开头
octal = oct(decimal_num)[2:]
# hex() 函数将十进制转换为十六进制，会以 '0x' 开头
hexadecimal = hex(decimal_num)[2:]

print(f"十进制 {decimal_num} 转换为二进制是: {binary}")
print(f"十进制 {decimal_num} 转换为八进制是: {octal}")
print(f"十进制 {decimal_num} 转换为十六进制是: {hexadecimal}")

其他进制转十进制

# 二进制转十进制
binary_num = "11111111"
decimal_from_binary = int(binary_num, 2)

# 八进制转十进制
octal_num = "377"
decimal_from_octal = int(octal_num, 8)

# 十六进制转十进制
hexadecimal_num = "FF"
decimal_from_hex = int(hexadecimal_num, 16)

print(f"二进制 {binary_num} 转换为十进制是: {decimal_from_binary}")
print(f"八进制 {octal_num} 转换为十进制是: {decimal_from_octal}")
print(f"十六进制 {hexadecimal_num} 转换为十进制是: {decimal_from_hex}")

任意进制之间的转换

如果要实现任意进制之间的转换，可以先将其转换为十进制，再从十进制转换为目标进制。

def convert_base(num_str, from_base, to_base):
    # 先将输入的数从 from_base 进制转换为十进制
    decimal_num = int(num_str, from_base)
    # 再将十进制数转换为 to_base 进制
    return decimal_to_base(decimal_num, to_base)

# 示例：将二进制数 1111 转换为八进制
binary_num = "1111"
octal_result = convert_base(binary_num, 2, 8)
print(f"二进制 {binary_num} 转换为八进制是: {octal_result}")