栈与队列算法

232.用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

思路：

• 用栈来实现队列，栈是先进后出，队列是先进先出
• 栈相当于数组，用两个栈来实现队列，数据先进入stack_in中，取出时再放入stack_out中原先的底部数据变成顶部数据

代码：

'''
用栈实现队列
队列是先进先出
栈是先进后出
用栈来实现后进的后出
'''

class MyQueue:

    def __init__(self):
        """
        in主要负责push，out主要负责pop
        """
        self.stack_in = []
        self.stack_out = []

    def push(self, x: int) -> None:
        """
        有新元素进来，就往in里面push
        """
        self.stack_in.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if self.empty():
            return None
        if self.stack_out:
            return self.stack_out.pop()
        else:
            for i in range(len(self.stack_in)):
                self.stack_out.append(self.stack_in.pop())
            return self.stack_out.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        ans = self.pop()
        self.stack_out.append(ans)
        return ans

    def empty(self) -> bool:
        """
        只要in或者out有元素，说明队列不为空
        """
        return not (self.stack_in or self.stack_out)

225.用队列实现栈

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

实现 MyStack 类：

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

注意：

• 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

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

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

思路：

这里的思想跟栈的类似，但这边只采用一个deque

当添加元素时，直接append

当删除元素时，popleft然后将取出的append在末尾，这样实现了掉头的功能，起始的元素即为末尾的元素popleft取出的即为刚添加的元素，这样就实现了先进先出

代码：

'''
用队列来实现栈
队列是先进先出
栈是先进后出
要实现栈的后出的功能
把最后进来的移到最前面
'''
from collections import deque


class MyStack:

    def __init__(self):
        """
        Python普通的Queue或SimpleQueue没有类似于peek的功能
        也无法用索引访问，在实现top的时候较为困难。

        用list可以，但是在使用pop(0)的时候时间复杂度为O(n)
        因此这里使用双向队列，我们保证只执行popleft()和append()，因为deque可以用索引访问，可以实现和peek相似的功能

        in - 存所有数据
        out - 仅在pop的时候会用到
        """
        self.que = deque()

    def push(self, x: int) -> None:
        """
        直接append即可
        """
        self.que.append(x)

    def pop(self) -> int:
        """
        1. 首先确认不空
        2. 因为队列的特殊性，FIFO，所以我们只有在pop()的时候才会使用queue_out
        3. 先把queue_in中的所有元素（除了最后一个），依次出列放进queue_out
        4. 交换in和out，此时out里只有一个元素
        5. 把out中的pop出来，即是原队列的最后一个

        tip：这不能像栈实现队列一样，因为另一个queue也是FIFO，如果执行pop()它不能像
        stack一样从另一个pop()，所以干脆in只用来存数据，pop()的时候两个进行交换
        """
        if self.empty():
            return None

        for i in range(len(self.que) - 1):
            self.que.append(self.que.popleft())
        return self.que.popleft()
    def top(self) -> int:
        """
        1. 首先确认不空
        2. 我们仅有in会存放数据，所以返回第一个即可
        """
        if self.empty():
            return None
        return self.que[-1]

    def empty(self) -> bool:
        """
        因为只有in存了数据，只要判断in是不是有数即可
        """
        return not self.que

20.有效的括号

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true

示例 2：

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

示例 3：

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

思路：

使用栈来表示先进后出的特性

使用record={‘(‘:’)’,’[‘:’]’,’{‘:’}’}来存储键值对

遍历s，取出元素i，如果i存在于record的键中，则用栈来存储i对应的值

如果栈为空或者i不等于栈末尾元素，返回False

否则i等于栈中末尾元素则取出栈末尾元素

最后判断栈是否为空来输出错误与否

代码：

class Solution:
    def isValid(s):
        sta=[]
        record={'(':')','[':']','{':'}'}
        for i in s:
            if i in record.keys():
                sta.append(record[i])
            elif not sta or i !=sta[-1]:
                return False
            else:
                sta.pop()
        return True if not sta else False

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

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

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

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

思路：

跟上题类似，比上题稍简单，不用建立字典来存储键值对

遍历字符串s，如果栈不为空，判断末尾元素与自己是否相同，如果相同则删除末尾元素

否则添加元素

最后输出栈

代码：

class Solution:
    def removeDuplicates(s):
        stack=[]
        for i in s:
            if stack and stack[-1]==i:
                stack.pop()
            elif not stack:
                stack.append(i)
            else:
                stack.append(i)
        return ''.join(stack)

150.逆波兰表达式求值

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

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

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

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

示例 2：

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

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

思路：

用栈的思想来实现，用数组record来记录 '+'、'-'、'*' 和 '/'

遍历tokens，当发现record元素时，取出栈中末后两个元素，将计算结果append

代码：

class Solution:
    def evalRPN(tokens):
        stack=[]
        record=['+','-','*','/']
        for i in tokens:
            if i not in record:
                stack.append(i)
            else:
                tmp1,tmp2=stack.pop(),stack.pop()
                stack.append(int(eval(f'{tmp2} {i} {tmp1}')) )
        return int(stack.pop())

239.滑动窗口最大值

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

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

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

思路：

• 利用双端队列记录当前滑动窗口的元素索引
• 队列最左侧元素记录滑动窗口中最大元素的索引
• 遍历数组：
• 如果队列最左侧索引已不在滑动窗口范围内，弹出队列最左侧索引
• 通过循环确保队列的最左侧索引所对应元素值最大
• 新元素入队
• 从第一个滑动窗口的末尾索引开始将最大值存储到结果res中

代码：

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        queue = collections.deque()
        for i, num in enumerate(nums):
            if queue and queue[0] == i - k:# 队列中最左侧元素索引不在窗口范围，出列
                queue.popleft()
            while queue and nums[queue[-1]] < num:# 新入列元素，比新的入列小的都出列
                queue.pop()
            queue.append(i)# 入列
            if i >= k - 1:# 取出res
                res.append(nums[queue[0]])
        return res

347.前 K 个高频元素

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

示例 1:

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

示例 2:

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

思路：

使用字典统计每个元素出现的次数

对字典中的值进行排序

取前k个高频元素

代码：

class Solution:
    def topKFrequent(nums, k):
        record={}
        result=[]
        for i in nums:
            if  i in record:
                record[i]+=1
            else:
                record[i]=1
        # 2.使用列表解析方法将学生字典转换为(value, key)的元组格式
        tuplelist = [(val, key) for key, val in record.items()]
        # 3.使用sorted函数对元组列表student_list由分数高低进行排序
        tuplelist_sorted = sorted(tuplelist,reverse=True)
        for j in range(k):
            result.append(tuplelist_sorted[j][1])
        return result