LeetCode讲解算法2-数据结构[栈和队列]（Python版）

文章目录

一、栈
- 1.1 栈的定义
- 1.2 栈的实现分析步骤
- 1.3 栈的应用
- - 匹配圆括号
  - 匹配符号
  - 模2除法（十进制转二进制）
  - 进制转换
二、队列
- 2.1 单向队列
- 2.2 双端队列
- 2.3 队列的应用
- - 验证回文串
  - 滑动窗口最大值

一、栈

1.1 栈的定义

栈是一种线性数据结构，栈是元素的有序集合，其元素的顺序取决于添加顺序或移除顺序，它有两端，称作顶端和底端，即对应栈的栈顶和栈底，栈中元素的添加称为入栈，而元素的移除称为出栈，栈中元素的添加操作和移除操作都发生在其顶端。
栈中最后添加的元素将最先被移除，栈的排序原则被称作LIFO，即后进先出，最先添加的元素在栈底，它最后最移出。简单来说，可比喻为几本书或砖头叠在一起，需要依次从上至下一本一本地拿出书，最下面的那本书最后被拿出。

1.2 栈的实现分析步骤

1、创建一个空栈，通过构造方法创建一个空列表；

class Stack:def __init__(self):self.items = []  # 创建一个空栈，它不需要参数，且会返回一个空栈

2、向栈（栈顶）中添加元素，通过列表的append()或insert()实现添加新的元素至栈中。（若将列表的尾部作为栈的顶端，则通过append()实现；而若将列表的头部作为栈的顶端，则通过insert()实现，insert()第一个参数表示索引位置，第二个参数即要添加的元素，由于是向栈顶添加元素，则第一个参数为0（列表的下标从0开始））；

def push(self, item):self.items.append(item)  # 将一个元素添加到栈的顶端，它需要一个参数item，且无返回值【self.items.insert(0,item)】

3、删除栈顶元素，通过列表的pop()实现删除栈顶的元素。（若将列表的尾部作为栈的顶端，pop()内无参数，即此时删除列表的末尾元素，也就是栈的顶端元素；而若将列表的头部作为栈的顶端，则pop(0)表示移除列表中下标为0的元素）；

def pop(self):return self.items.pop()  # 将栈顶的元素移除，它不需要参数，但会返回顶端的元素，且修改栈的内容【return self.items.pop(0)】

4、返回栈顶元素，若将列表的尾部作为栈的顶端，则通过len()先取得列表的长度，由于下标是从0开始，所以要减1；而若将列表的头部作为栈的顶端，则直接通过索引列表下标为0的元素）；

def peek(self):return self.items[len(self.items) - 1]  # 返回栈顶端的元素，它不需要参数，不会修改栈的内容【return self.items[0]】

5、检查栈是否为空，通过比较运算符“==”比较栈是否为空，若为空，则返回布尔值False，若不为空，则返回True；

 def isEmpty(self):return self.items == []  # 检查栈是否为空，它不需要参数，且会返回一个布尔值

6、返回栈中元素数目，通过len()取列表的长度，即返回栈中元素的数目。

def size(self):return len(self.items)  # 返回栈中元素的数目，它不需要参数，且会返回一个整数

代码实现

# 通过列表实现栈的操作（以列表尾部作为栈的顶端）
class Stack:def __init__(self):self.items = []  # 创建一个空栈，它不需要参数，且会返回一个空栈def isEmpty(self):return self.items == []  # 检查栈是否为空，它不需要参数，且会返回一个布尔值def push(self, item):self.items.append(item)  # 将一个元素添加到栈的顶端，它需要一个参数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)  # 返回栈中元素的数目，它不需要参数，且会返回一个整数

1.3 栈的应用

匹配圆括号

我们知道圆括号由左括号“(”和右括号“)”进行匹配的，通过创建一个空栈来保存括号，从左至右依次处理括号，若匹配到左括号则通过push()方法将其添加至栈中，而若匹配到右括号则通过pop()方法删除栈顶元素，最后若所有括号都匹配则栈为空，程序会返回一个布尔值来表示括号是否匹配。
程序完整代码及解析如下：

# 通过列表实现栈的操作（以列表尾部作为栈的顶端）
class Stack:def __init__(self):self.items = []  # 创建一个空栈，它不需要参数，且会返回一个空栈def isEmpty(self):return self.items == []  # 检查栈是否为空，它不需要参数，且会返回一个布尔值def push(self, item):self.items.append(item)  # 将一个元素添加到栈的顶端，它需要一个参数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)  # 返回栈中元素的数目，它不需要参数，且会返回一个整数# 定义一个有参函数Par_Checker()，其参数parenthesis是输入的括号
def Par_Checker(parenthesis):s = Stack()  # s是一个新创建的空栈，创建一个对象balanced = Trueindex = 0while index < len(parenthesis) and balanced:  # 若当前索引值小于输入的括号的总长度且变量balanced的值为正确时，一直执行while循环下去symbol = parenthesis[index]# 取输入的括号赋给变量symbol，变量index的初值为0if symbol == "(":  # 若匹配到左括号则通过push()方法将其添加至栈中s.push(symbol)else:if s.isEmpty():  # 检查栈是否为空，它不需要参数，会返回一个布尔值balanced = False  # 栈为空，变量balanced的值变为Falseelse:s.pop()  # 若匹配到右括号则通过pop()方法删除栈顶元素index = index + 1  # 索引加一，对下一个括号进行检查if balanced and s.isEmpty():  # 如果栈为空，则代表所有括号都匹配成功return Trueelse:return False#测试
print(Par_Checker("(()(("))#false
print(Par_Checker(")(("))#false
print(Par_Checker("(()(()))"))#true

匹配符号

通过改进匹配圆括号的程序从而实现对符号“()”、“[]”和“{}”的匹配，在原有的基础上加了一个函数matches()，该函数检查每一个从栈顶移除的符合是否与当前的右符合相匹配，匹配符号的程序完整代码及解析如下：

# 通过列表实现栈的操作（以列表尾部作为栈的顶端）
class Stack:def __init__(self):self.items = []  # 创建一个空栈，它不需要参数，且会返回一个空栈def isEmpty(self):return self.items == []  # 检查栈是否为空，它不需要参数，且会返回一个布尔值def push(self, item):self.items.append(item)  # 将一个元素添加到栈的顶端，它需要一个参数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)  # 返回栈中元素的数目，它不需要参数，且会返回一个整数# 定义一个有参函数matches()，该函数检查每一个从栈顶移除的符合是否与当前的右符合相匹配
def matches(left, right):left = "([{"right = ")]}"return left.index(left) == right.index(right)  # index()用于检查子字符串是否在字符串中# 定义一个有参函数Par_Checker()，其参数parenthesis是输入的括号
def Par_Checker(parenthesis):s = Stack()  # s是一个新创建的空栈，创建一个对象balanced = Trueindex = 0while index < len(parenthesis) and balanced:  # 若当前索引值小于输入的符号的总长度且变量balanced的值为正确时，一直执行while循环下去symbol = parenthesis[index]  # 取输入的符号赋给变量symbol，变量index的初值为0if symbol in "([{":  # 若匹配到左符号则通过push()方法将其添加至栈中s.push(symbol)else:if s.isEmpty():  # 检查栈是否为空，它不需要参数，会返回一个布尔值balanced = False  # 栈为空，变量balanced的值变为Falseelse:top = s.pop()  # 若匹配到右符号则通过pop()方法删除栈顶元素if not matches(top, symbol):  # 调用matches()函数检查每一个从栈顶移除的符合是否与当前的右符合相匹配，即若未匹配执行以下语句balanced = Falseindex = index + 1  # 索引加一，对下一个符号进行检查if balanced and s.isEmpty():  # 如果栈为空，则代表所有符号都匹配成功return Trueelse:return False#测试
print(Par_Checker("(({)("))
print(Par_Checker("]("))
print(Par_Checker("{([]})"))

模2除法（十进制转二进制）

我们知道将十进制转二进制可以通过模2除法的方法实现，也就是除2取余，逆序排列，如下十进制25转换为二进制：

我们从步骤上可以看出，计算出的第一个余数是得到结果的最后一位，而最后计算出的余数是结果的第一位，所以可以将得到的二进制数看成一系列数字，创建一个空栈，通过一系列方法得到二进制数字。
模2除法的程序完整代码及解析如下：

# 通过列表实现栈的操作（以列表尾部作为栈的顶端）
class Stack:def __init__(self):self.items = []  # 创建一个空栈，它不需要参数，且会返回一个空栈def isEmpty(self):return self.items == []  # 检查栈是否为空，它不需要参数，且会返回一个布尔值def push(self, item):self.items.append(item)  # 将一个元素添加到栈的顶端，它需要一个参数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)  # 返回栈中元素的数目，它不需要参数，且会返回一个整数# 创建一个有参函数DivideBy2()，参数为一个十进制数
def DivideBy2(decNumber):s = Stack()  # s是一个新创建的空栈，创建一个对象while decNumber > 0:  # 若输入的十进制大于0，则执行while循环一直下去rem = decNumber % 2  # 参数rem为余数，即十进制数每次除2得到的余数s.push(rem)  # 通过push()方法将得到的余数添加到栈的顶端decNumber = decNumber // 2  # 输入的十进制整数除2，即十进制与2的整数商binString = ""  # 定义一个空字符串binString用于存放二进制数字while not s.isEmpty():  # 若栈不为空，则执行while循环一直下去binString = binString + str(s.pop())  # 通过pop()方法将栈顶的元素移除，通过str()转换为字符串类型并通过"+"拼接赋值给字符串binStringreturn binString  # 得到的二进制值print(DivideBy2(17))
print(DivideBy2(255))
print(DivideBy2(1024))
print(DivideBy2(2022))

进制转换

根据十进制转二进制的程序代码可以进一步改进，首先该函数可以另外定义一个参数base，它表示相应的进制数（二进制、八进制、十六进制），另外创建一个字符串digits，由于有十进制转十六进制，所以该字符串的内容应该有ABCDEF，再加上数字0-9，即该字符串的内容为“0123456789ABCDEF”，它用于存储对应位置上的数字，当从栈中移除一个十进制余相应的进制数得到的余数时，就可以作为访问数字的下标，即对应的数字会被添加到结果中，最后再通过pop()方法将栈顶的元素移除，通过对字符串索引的方式依次索引移除的元素，并通过"+"拼接赋值给字符串newString。
十进制转其他进制（二进制、八进制、十六进制）的程序完整代码及解析如下：

# 通过列表实现栈的操作（以列表尾部作为栈的顶端）
class Stack:def __init__(self):self.items = []  # 创建一个空栈，它不需要参数，且会返回一个空栈def isEmpty(self):return self.items == []  # 检查栈是否为空，它不需要参数，且会返回一个布尔值def push(self, item):self.items.append(item)  # 将一个元素添加到栈的顶端，它需要一个参数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)  # 返回栈中元素的数目，它不需要参数，且会返回一个整数# 创建一个有参函数BaseConverter()，参数为进制数和进制
def BaseConverter(decNumber, base):digits = "0123456789ABCDEF"  # 创建一个字符串digits，存储对应位置上的数字，当从栈中移除一个余数时，它可以被用作访问数字的下标，对应的数字会被添加到结果中s = Stack()while decNumber > 0:  # 若输入的进制数大于0，则执行while循环一直下去rem = decNumber % base  # 参数rem为余数，即进制数每次除相应的进制得到的余数s.push(rem)  # 通过push()方法将得到的余数添加到栈的顶端decNumber = decNumber // base  # 输入的进制数整数除相应的进制newString = ""  # 定义一个空字符串newString用于存放二进制数字while not s.isEmpty():  # 若栈不为空，则执行while循环一直下去newString = newString + digits[s.pop()]  # 通过pop()方法将栈顶的元素移除，通过对字符串索引的方式依次索引移除的元素，并通过"+"拼接赋值给字符串newStringreturn newString  # 得到的相应进制值#测试
print(BaseConverter(17, 2))
print(BaseConverter(255, 8))
print(BaseConverter(1024, 16))
print(BaseConverter(2022, 16))

二、队列

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出的（First In First Out）的线性表，简称 FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

2.1 单向队列

单向队列操作

enqueue(item) ：往队列中添加一个item元素
dequeue()：从队列头部删除一个元素
is_empty()：判断一个队列是否为空
size()：返回队列的大小

同样地，这里也以 list 实现单向队列，当然你也可以使用链表实现。

class Queue(object):"""创建一个空的队列"""def __init__(self):"""用顺序表实现队列，Python 中 list 是顺序表队列：先进先出以列表尾部为队头（append：O(1)，就要从列表头就是队列尾部（pop(0)：O(n)）以列表头部为队头（insert(0, item)：O(n)，就要从列表就尾是队列尾部（pop()：O(1)）所有哪种方法都可以"""# 定义一个列表，用来存储元素self.__list = []def enqueue(self, item):"""往队列中添加一个item元素"""self.__list.append(item)def dequeue(self):"""从队列头部删除一个元素"""return self.__list.pop(0)def is_empty(self):"""判断栈是否为空若 self.__list 为空，则为 False，[] 也是 False，两者为真，返回 True"""return self.__list == []def size(self):"""返回栈的元素个数"""return len(self.__list)if __name__ == '__main__':q = Queue()print(q.is_empty())q.enqueue(1)q.enqueue(2)q.enqueue(3)print(q.size())print(q.is_empty())print(q.dequeue())print(q.dequeue())print(q.dequeue())print(q.is_empty())

2.2 双端队列

双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。
双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。
操作

add_front(item)：从队头加入一个item元素
add_rear(item) ：从队尾加入一个item元素
remove_front() ：从队头删除一个item元素
remove_rear()：从队尾删除一个item元素
is_empty() ：判断双端队列是否为空
size() ：返回队列的大小

class Deque(object):"""创建一个空的双端队列"""def __init__(self):"""用顺序表实现栈，Python 中 list 是顺序表栈：先进先出以列表尾部为队头（append：O(1)，就要从列表头就是队列尾部（pop(0)：O(n)）以列表头部为队头（insert(0, item)：O(n)，就要从列表就尾是队列尾部（pop()：O(1)）所有哪种方法都可以"""# 定义一个列表，用来存储元素self.__list = []def add_front(self, item):"""从队头加入一个item元素"""self.__list.insert(0, item)     # O(n)# self.__list.append(item)      # O(1)def add_rear(self, item):"""从队尾加入一个item元素"""self.__list.append(item)        # O(1)# self.__list.insert(0, item)   # O(n)def remove_front(self):"""从队头删除一个item元素"""return self.__list.pop(0)       # O(n)# return self.__list.pop()      # O(1)def remove_rear(self):"""从队尾删除一个item元素"""return self.__list.pop()        # O(1)# return self.__list.pop(0)     # O(n)def is_empty(self):"""判断栈是否为空若 self.__list 为空，则为 False，[] 也是 False，两者为真，返回 True"""return self.__list == []def size(self):"""返回栈的元素个数"""return len(self.__list)if __name__ == '__main__':q = Deque()print(q.is_empty())q.add_front(1)      # 1q.add_front(2)      # 2 1q.add_rear(3)       # 2 1 3print(q.size())     # 3print(q.is_empty())     # Falseprint(q.remove_front())     # 2print(q.remove_front())     # 1print(q.remove_rear())      # 3print(q.is_empty())         # True

2.3 队列的应用

验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: “A man, a plan, a canal: Panama”
输出: true
解释：“amanaplanacanalpanama” 是回文串

示例 2:
输入: “race a car”
输出: false
解释：“raceacar” 不是回文串

双端队列求解

import collections
class Solution:def isPalindrome(self, s):#s=strs = s.lower()# 检测字母与数字字符s = [i for i in s if i.isalpha() or i.isnumeric()]# 构造双端队列deque = collections.deque()# 回文词入对for i in s:deque.appendleft(i)state = Truewhile len(deque) > 1 and state:left = deque.popleft()right = deque.pop()if left != right:state = Falsereturn state

滑动窗口最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]

class Solution:# 方法二：双端队列def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:n = len(nums)q = collections.deque()# 先将k个元素生成单调递减队列for i in range(k):while q and nums[i] >nums[q[-1]]:q.pop()q.append(i)# 首个窗口的最大元素进列表res = [nums[q[0]]]# 再依次入单调递减队列for i in range(k,n):while q and nums[i]>nums[q[-1]]:q.pop()q.append(i)# 当队列长度超过k个，就弹出队首while q[0]<=i-k:q.popleft()res.append(nums[q[0]])return res

在这里插入图片描述