Python[数据结构及算法 --- 栈]

一.栈的概念

在 Python 中，栈（Stack）是一种 “  后进先出（LIFO）”的数据结构，仅允许在栈顶进行插入（push）和删除（pop）操作。

二.栈的抽象数据类型 

1.抽象数据类型 “栈” 定义：

<1>.Stack ()：创建一个空栈，不包含任何数据项
<2>.push (item)：将 item 加入栈顶，无返回值
<3>.pop ()：将栈顶数据项移除，并返回，栈被修改
<4>.peek ()：“窥视” 栈顶数据项，返回栈顶的数据项但不移除，栈不被修改
<5>.isEmpty ()：返回栈是否为空栈
<6>.size ()：返回栈中有多少个数据项 

2.简单操作样例：

Stack Operation	Stack Contents	Return Value
s = Stack()	[]	Stack object
s.isEmpty()	[]	True
s.push(4)	[4]
s.push('dog')	[4, 'dog']
s.peek()	[4, 'dog']	'dog'
s.push(True)	[4, 'dog', True]
s.size()	[4, 'dog', True]	3
s.isEmpty()	[4, 'dog', True]	False
s.push(8.4)	[4, 'dog', True, 8.4]
s.pop()	[4, 'dog', True]	8.4
s.pop()	[4, 'dog']	True
s.size()	[4, 'dog']	2

3.操作实例代码实现：

class Stack:def __init__(self):self.items = []def isEmpty(self):return self.items == []def push(self,item):self.items.append(item)def pop(self):return self.items.pop()def peek(self):return self.items[len(self.items) - 1]def size(self):return len(self.items)# 操作样例
s = Stack()
print("s.isEmpty():", s.isEmpty())  # Trues.push(4)
s.push('dog')
print("s.peek():", s.peek())  # 'dog's.push(True)
print("s.size():", s.size())  # 3
print("s.isEmpty():", s.isEmpty())  # Falses.push(8.4)
print("s.pop():", s.pop())  # 8.4
print("s.pop():", s.pop())  # True
print("s.size():", s.size())  # 2    

三.栈的应用

1.简单括号匹配：

class Stack:def __init__(self):self.items = []def isEmpty(self):return self.items == []def push(self,item):self.items.append(item)def pop(self):return self.items.pop()def peek(self):return self.items[len(self.items) - 1]def size(self):return len(self.items)def parChecker(symbolString):s = Stack()balanced = Trueindex = 0while index < len(symbolString) and balanced:symbol = symbolString[index]if symbol == "(":s.push(symbol)else:if s.isEmpty():balanced = Falseelse:s.pop()index = index + 1if balanced and s.isEmpty():return Trueelse:return False# 测试示例
print(parChecker("((()))"))      # True
print(parChecker("(()"))        # Error: unmatched left parentheses
print(parChecker("(]"))         # Error at position 1: mismatched ']'
print(parChecker("{[()]}"))     # True
print(parChecker("{[(])}"))     # Error at position 3: mismatched ')'

代码分析：

1.提供的代码是一个使用栈（Stack）检查括号平衡性的函数 parChecker。这个函数可以判断一个字符串中的括号是否匹配（即每个左括号 ( 都有对应的右括号 )）。

2.实现过程：

<1>.初始化栈：创建一个空栈 s 用于存储左括号 (。

<2>.遍历字符串：从左到右扫描每个字符：

       遇到左括号 ( 时，将其压入栈。

       遇到右括号 ) 时：

如果栈为空，说明没有匹配的左括号，返回 False。

如果栈不为空，弹出栈顶元素（即匹配一个左括号）。

<3>.最终判断：遍历结束后，如果栈为空且所有括号都匹配，则返回 True，否则返回 False。

3.复杂度分析：

<1>.时间复杂度：O (n)，其中 n 是字符串长度。

<2>.空间复杂度：O (n)，最坏情况下栈存储所有左括号（如 "((((("）。

2.将十进制数转换成二进制数：

def divideBy2(decnumber):remstack = Stack()while decnumber > 0:rem = decnumber % 2remstack.push(rem)decnumber = decnumber // 2binstring = ""while not remstack.isEmpty():binstring = binstring + str(remstack.pop())return binstringprint(divideBy2(100))
print(divideBy2(200))
print(divideBy2(300))
print(divideBy2(400))
print(divideBy2(500))

代码分析：

1.提供的代码是一个使用栈（Stack）将十进制数转换为二进制数的函数 divideBy2。这个函数通过不断除以 2 并记录余数，最后反向拼接余数得到二进制表示。

2.实现过程：

<1>.初始化栈：创建一个空栈 remstack 用于存储每次除法的余数。

<2>.循环取余：当十进制数 decnumber 大于 0 时，不断进行以下操作：

                         1.计算 decnumber % 2 得到余数（0 或 1）。

                         2.将余数压入栈 remstack。

                         3.更新 decnumber 为其整数除法结果（decnumber // 2）。

<3>.拼接二进制字符串：从栈中弹出所有元素并拼接成字符串，得到二进制表示。

3.复杂度分析：

<1>.时间复杂度：O(log n)

每次循环将输入数减半，循环次数为 log₂(n)，每次操作（取余、压栈）时间为 O (1)。

<2>.空间复杂度：O(log n)

栈中存储的余数数量为 log₂(n)，拼接字符串的空间也为 log₂(n)。

优化改进：

将上述代码改进成可以任意进制转换，适配性更强：

class Stack:def __init__(self):self.items = []def isEmpty(self):return self.items == []def push(self,item):self.items.append(item)def pop(self):return self.items.pop()def peek(self):return self.items[len(self.items) - 1]def size(self):return len(self.items)def baseConverter(decnumber,base):digits = "0123456789ABCDEF"remstack = Stack()while decnumber > 0:rem = decnumber % baseremstack.push(rem)decnumber = decnumber // basenewstring = ""while not remstack.isEmpty():newstring = newstring + digits[remstack.pop()]return newstringprint(baseConverter(100,2))
print(baseConverter(100,4))
print(baseConverter(100,6))
print(baseConverter(100,8))
print(baseConverter(100,10))
print(baseConverter(100,16))

以上就是一些比较经典的栈的应用。