首页 > 编程语言 >【算法】栈与队列

【算法】栈与队列

时间：2023-09-26 11:11:06浏览次数：69  
标签：队列 self 元素 pop int 算法 stack

1 栈与队列理论基础

队列先进先出，栈先进后出；不允许有遍历行为，不提供迭代器

2 用栈实现队列

题目：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

  • 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

思路：使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈：一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。

Python中可以使用列表（list）来实现栈。可以使用append()方法来将元素添加到栈的顶部，并使用pop()方法来从栈的顶部移除元素。

class MyQueue:
    def __init__(self):
        # in主要负责push，out主要负责pop
        self.stack_in = []
        self.stack_out = []
    def push(self, x: int) -> None:
        self.stack_in.append(x) # 有新元素进来，就往in里面push
    def pop(self) -> int:
        if self.empty():
            return None
        if not self.stack_out: # 输出栈为空
            while len(self.stack_in) != 0:
                self.stack_out.append(self.stack_in.pop())
        return self.stack_out.pop()
    def peek(self) -> int:
        res = self.pop()
        self.stack_out.append(res)
        return res
    def empty(self) -> bool:
        # 只要in或者out有元素，说明队列不为空
        return not (self.stack_in or self.stack_out)
        # return (len(self.stack_in) + len(self.stack_out)) == 0

3 用队列实现栈

题目：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

思路：用两个队列que1和que2实现栈的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。

Python普通的Queue或SimpleQueue没有类似于peek的功能也无法用索引访问，在实现top的时候较为困难。因此这里使用双向队列，我们保证只执行popleft()和append()，因为deque可以用索引访问，可以实现和peek相似的功能。

class MyStack:
    def __init__(self):
        self.queue_in = deque()
        self.queue_out = deque()
    def push(self, x: int) -> None:
        self.queue_in.append(x)
    def pop(self) -> int:
        if self.empty():
            return None
        for i in range(len(self.queue_in) - 1):
            self.queue_out.append(self.queue_in.popleft())
        self.queue_in, self.queue_out = self.queue_out, self.queue_in
        return self.queue_out.popleft()
    def top(self) -> int:
        ans = self.pop()
        self.queue_in.append(ans)
        return ans
    def empty(self) -> bool:
        return not self.queue_in

其实这道题目用一个队列就够了。

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。

class MyStack:
    def __init__(self):
        self.queue = deque()
    def push(self, x: int) -> None:
        self.queue.append(x)
    def pop(self) -> int:
        if self.empty():
            return None
        for i in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())
        return self.queue.popleft()
    def top(self) -> int:
        return self.queue[-1]
    def empty(self) -> bool:
        return len(self.queue) == 0

4 有效的括号*

题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()[]{}"
输出：true

示例 2：

输入：s = "(]"
输出：false

思路：先来分析一下这里有三种不匹配的情况：

  1. 第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
  2. 第二种情况，括号没有多余，但是括号的类型没有匹配上。
  3. 第三种情况，字符串里右方向的括号多余了，所以不匹配。

第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有匹配，return false

第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符，所以return false

第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

1. 在遍历到左括号的时候让右括号入栈，就只需要比较当前元素和栈顶是否相等就可以 
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for item in s:
            if item == '(':
                stack.append(')')
            elif item == '[':
                stack.append(']')
            elif item == '{':
                stack.append('}')
            elif not stack or stack[-1] != item: # 栈已经为空（右括号多）或遇到不匹配括号
                return False
            else:
                stack.pop()      
        return not stack # 栈不为空说明左括号多
2. 使用字典 
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping = {
            '(': ')',
            '[': ']',
            '{': '}'
        }
        for item in s:
            if item in mapping.keys():
                stack.append(mapping[item])
            elif not stack or stack[-1] != item: 
                return False
            else: 
                stack.pop()
        return True if not stack else False

5 删除字符串中的所有相邻重复项

题目：给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"

思路：用栈存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for i in s:
            if stack and stack[-1] == i:
                stack.pop()
            else:
                stack.append(i)
        return "".join(stack)
  • 用双指针模拟栈***
class Solution:
    def removeDuplicates(self, s: str) -> str:
        fast = slow = 0
        res = list(s)
        while fast < len(s):
            res[slow] = res[fast]
            if slow > 0 and res[slow] == res[slow - 1]: # 如果相同，回退一格
                slow -= 1
            else:
                slow += 1
            fast += 1
        return "".join(res[:slow])

6 逆波兰表达式

题目： 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/' 。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

题解：

注意除法要写成int(num1 / num2)

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for i in tokens:
            if i not in {'+', '-', '*', '/'}: # 说明是数字
                stack.append(int(i))
            else:
                num2 = stack.pop()
                num1 = stack.pop()
                if i == '+':
                    stack.append(num1 + num2)
                elif i == '-':
                    stack.append(num1 - num2)
                elif i == '*':
                    stack.append(num1 * num2)
                elif i == '/':
                    stack.append(int(num1 / num2))
        return stack[0]

还看到两种写法，用了map和eval()

from operator import add, sub, mul
class Solution:
    op_map = {'+': add, '-': sub, '*': mul, '/': lambda x, y: int(x / y)}
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token not in {'+', '-', '*', '/'}:
                stack.append(int(token))
            else:
                op2 = stack.pop()
                op1 = stack.pop()
                stack.append(self.op_map[token](op1, op2))  # 第一个出来的在运算符后面
        return stack.pop()

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for item in tokens:
            if item not in {"+", "-", "*", "/"}:
                stack.append(item)
            else:
                first_num, second_num = stack.pop(), stack.pop()
                stack.append(
                    int(eval(f'{second_num} {item} {first_num}'))   # 第一个出来的在运算符后面
                )
        return int(stack.pop()) # 如果一开始只有一个数，那么会是字符串形式的

7 滑动窗口最大值**

题目：给你一个整数数组 nums，有一个大小为 k **的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

思路：这是使用单调队列的经典题目。

队列里的元素一定是要排序的，而且要最大值放在出队口，要不然怎么知道最大值呢。

但如果把窗口里的元素都放进队列里，窗口移动的时候，队列需要弹出元素。那么问题来了，已经排序之后的队列怎么能把窗口要移除的元素（这个元素可不一定是最大值）弹出呢。

其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。

设计单调队列的时候，pop，和push操作要保持如下规则：

  1. pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
  2. push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止

保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。

❗踩了个坑，push操作最开始设计成value大于等于入口元素时都会把入口元素覆盖。出现问题：当value=入口元素=最大值，也就是新来的这个value一下子跑到单调队列最前面去了，那么下一次窗口滑动需要pop时，如果原先最大的元素正好就是要被移出窗口的元素，刚进来的value会代替那个最大值被移出去，队列里失去了应有的最大值！所以不能加等号！


class MyQueue:
    def __init__(self):
        self.que = deque() # 双向
    def pop(self, val):
        if self.que and self.que[0] == val: # 要弹出的元素就是当前最大值
            self.que.popleft()
    def push(self, val):
        while self.que and val > self.que[-1]: # 要放入的元素比入口元素大
            self.que.pop()
        self.que.append(val)
    def top(self):
        return self.que[0]
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        que = MyQueue()
        res = []
        for i in range(k):
            que.push(nums[i])
        res.append(que.top())
        for i in range(k, len(nums)):
            que.pop(nums[i - k])
            que.push(nums[i])
            res.append(que.top())
        return res

8 前k个高频元素*

题目：给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入:nums = [1,1,1,2,2,3], k = 2
输出:[1,2]

思路：这道题目主要涉及到如下三块内容：

  1. 要统计元素出现频率
  2. 对频率排序
  3. 找出前K个高频元素
  • 用字典自己写了个解
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = defaultdict(int)
        for i in nums:
            freq[i] += 1
        sorted_items = sorted(freq.items(), key = lambda x: x[1]) # 根据频率排序，得到元组列表
        res = sorted_items[-k:] # 获取频率最高的k项，每一项为(val, freq)元组
        return [item[0] for item in res] # 返回频率最高的k个val组成的列表
  • 优先级队列 - 小顶堆

对频率进行排序，可以使用优先级队列priority_queue。

优先级队列就是一个披着队列外衣的堆，内部元素自动依照元素的权值排列。

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆（堆头是最大元素），小于等于左右孩子就是小顶堆。

我们要用小顶堆而不是大顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。存放元组时，小顶堆会根据元组的第一个元素（整数）进行排序。

import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = defaultdict(int)
        for i in nums:
            freq[i] += 1   
        min_heap = [] # 小顶堆
        for val, freq in freq.items():
            heapq.heappush(min_heap, (freq, val))
            if len(min_heap) > k: # 固定大小为k
                heapq.heappop(min_heap)
        res = []
        for i in range(k):
            res.append(heapq.heappop(min_heap)[1]) # 此时小顶堆里一定是最大的k个
        return res
  • 优先级队列 - 我直接用大顶堆也不是不行啊！
import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = defaultdict(int)
        for i in nums:
            freq[i] += 1    
        max_heap = [] 
        for val, freq in freq.items():
            heapq.heappush(max_heap, (-freq, val)) # 负频率实现大顶堆     
        res = []
        for i in range(k):
            res.append(heapq.heappop(max_heap)[1])
        return res

❗一开始用了切片结果踩坑了，注意大顶堆的列表不是整体有序的，还是得用heappop

标签：队列,self,元素,pop,int,算法,stack
From： https://www.cnblogs.com/Aikoin/p/17729669.html

相关文章

  • centos安装rabbitmq消息队列
    开源的消息队列系统很多如erlang开发的rabbitmq，java开发的activemq，redis的list也可以实现，workerman也有消息队列我们项目用的是rabbitmq，它的优点1、基于erlang语言开发具有高可用高并发的优点，适合集群服务器2、健壮、稳定、易用、跨平台、支持多种语言、文档齐全3、有消息确认机......
  • 算法训练day20 LeetCode654
    算法训练day20LeetCode654.617.700.98654.最大二叉树题目654.最大二叉树-力扣（LeetCode）题解代码随想录(programmercarl.com)使用递归返回节点地址，输入父节点地址，数组终止条件是输入地数组为空单层操作：如果输入数组为空，则返回父节点地址否则找到数组中最大......
  • 基于图像形态学处理的目标几何形状检测算法matlab仿真
    1.算法运行效果图预览  2.算法运行软件版本matlab2022a 3.算法理论概述      目标几何形状检测是计算机视觉领域中的重要任务之一，旨在从图像中自动识别和定位不同的几何形状，例如矩形、圆形、三角形等。这些形状检测在许多领域中都具有广泛的应用，如工业自动化......
  • 关于Pohlig-Hellmen算法喵
    \(g^x\equiva(mod\;p)\)当\(g\)为原根时拆分\(p-1=\prod_{i=1}p_i^{ki}\)对于每一个\(p_i\)进行处理将\(x\)转化为\(p\)进制数\(x=c_0+c_1p_i+c_2p_i^2+...+c_{k_i-1}p_i^{k_i-1}\)\(g^{x(\frac{p-1}{p_i})}\equiva^{\frac{p-1}{p_i}}(mod\;p)\)用1展开2中......
  • 队列环形数组实现两种实现
      1importjava.util.Iterator;//环形队列，数组容量应该比实际需要大一publicclassMain{publicstaticvoidmain(String[]args){ArrayQueue<Integer>a=newArrayQueue<>(10);a.push(1);a.push(2);a.push(3);a.push(4)......
  • 【算法】莫队
    一、概念莫队是一种应用于离线询问的优美暴力算法。它是主要思想是让区间的左端点和右端点移动的距离加起来最短。二、实现假设现在有这样一串序列：\(1,1,4,5,1,4\)，我们现在要求询问区间内的\(1\)的出现次数。如果我们现在已经统计到了区间\((2,3)\)，现在询问\((1,5)\)。现......
  • 什么是消息队列
    今天，我们一起来看看，消息队列是个啥？消息队列是否了解？消息队列初步来看，是由“消息”和“队列”组成，英文叫做：MessageQueue，一般这些玩意都会根据英文名称来个简称，而简称一般就是英文名字的首字母缩写，所以消息队列即MQ。可能你对消息队列有点陌生，但是你一定听过消息队列四个字，而且......
  • 文心一言 VS 讯飞星火 VS chatgpt （100）-- 算法导论9.3 6题
    六、用go语言，对一个包含n个元素的集合来说，k分位数是指能把有序集合分成k个等大小集合的第k-1个顺序统计量。给出一个能找出某一集合的k分位数的O(nlgk)时间的算法。文心一言：要找到一个集合的k分位数，可以使用Go语言编写以下算法：packagemainimport("fmt""sort"......
  • [剑指offer] 其他算法[上]篇
    JZ66构建乘积数组/*暴力*/publicclassJZ66_1{publicstaticint[]multiply(int[]A){int[]res=newint[A.length];Arrays.fill(res,1);for(inti=0;i<A.length;i++){for(intj=0;j<A.len......
  • 快速排序/选择算法
    ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99