栈与队列

栈和队列都比较好理解，栈是先进后出，队列是先进先出

栈

# Python 没有内置的栈类，可以用 List 当作栈来代替
stack = []
# 元素入栈
stack.append(1)
stack.append(2)
stack.append(3)
# 访问栈顶元素
peek = stack[-1]
# 元素出栈
pop = stack.pop()
# 获取栈的长度
size = len(stack)
# 判断是否为空
is_empty = len(stack) == 0

队列

from collections import deque

# 新建一个 deque，并初始化内容为 [1, 2, 3]
queue = deque([1, 2, 3])

# 在队尾插入元素 4
queue.append(4)

# 在队首插入元素 0
queue.appendleft(0)

# 访问队列
# >>> queue
# deque([0, 1, 2, 3, 4])

栈的链表实现

栈的数组实现

队列

队列的链表实现

队列的数组实现

20. 有效的括号

20. 有效的括号

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False

        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

150. 逆波兰表达式求值

150. 逆波兰表达式求值

# 逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。

# 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

# 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

# 逆波兰表达式主要有以下两个优点：

# 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

# 适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。


class Solution:
    def evalRPN(self, tokens) -> int:
        stack = []
        for item in tokens:
            if item == "+":
                stack.append(stack.pop() + stack.pop())
            elif item == "-":
                stack.append(-stack.pop() + stack.pop())
            elif item == "*":
                stack.append(stack.pop() * stack.pop())
            elif item == "/":
                stack.append(int(1 / stack.pop() * stack.pop()))
            else:
                stack.append(int(item))
        return stack.pop()

155. 最小栈

155. 最小栈

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append(val)
            self.min_stack.append(val)
        else:
            self.stack.append(val)
            self.min_stack.append(min(val, self.min_stack[-1]))

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

225. 用队列实现栈

225. 用队列实现栈

class MyStack:

    def __init__(self):
        from collections import deque
        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:
        if self.empty():
            return None
        return self.queue_in[-1]

    def empty(self) -> bool:
        return len(self.queue_in) == 0


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

232. 用栈实现队列

232. 用栈实现队列

class MyQueue:

    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def push(self, x: int) -> None:
        self.stack_in.append(x)

    def pop(self) -> int:
        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:
        x = self.pop()
        self.stack_out.append(x)
        return x

    def empty(self) -> bool:
        return not (self.stack_in or self.stack_out)


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

239. 滑动窗口最大值

239. 滑动窗口最大值

class Solution:
    def maxSlidingWindow(self, nums, k: int):
        queue = MyQueue()
        res = []
        for i in range(k):  # 先将前k的元素放进队列
            queue.push(nums[i])
        res.append(queue.front())  # 记录前k的元素的最大值

        for i in range(k, len(nums)):
            queue.pop(nums[i - k])  # 滑动窗口移除最前面元素
            queue.push(nums[i])  # 滑动窗口前加入最后面的元素
            res.append(queue.front())  # 记录对应的最大值
        return res


class MyQueue:
    def __init__(self):
        from collections import deque
        self.queue = deque()

    # 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出
    # 同时pop之前判断队列当前是否为空
    def pop(self, val):
        if self.queue and val == self.queue[0]:
            self.queue.popleft()

    # 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止
    # 这样就保持了队列里的数值是单调从大到小的了
    def push(self, val):
        while self.queue and val > self.queue[-1]:
            self.queue.pop()
        self.queue.append(val)

    # 当前队列里的最大值
    def front(self):
        return self.queue[0]

347. 前 K 个高频元素

347. 前 K 个高频元素

class Solution:
    def topKFrequent(self, nums, k: int):
        maps = {}
        # 一次循环跑出元素出现的次数
        # nums[i] 对应出现的次数
        for i in range(len(nums)):
            maps[nums[i]] = maps.get(nums[i], 0) + 1

        # 对频次排序
        # 小顶堆
        import heapq
        small_que = []
        for key, val in maps.items():
            heapq.heappush(small_que, (val, key))
            if len(small_que) > k:
                heapq.heappop(small_que)

        res = [0] * k
        for i in range(k - 1, -1, -1):
            res[i] = heapq.heappop(small_que)[1]
        return res

622. 设计循环队列

622. 设计循环队列

class MyCircularQueue:

    def __init__(self, k: int):


    def enQueue(self, value: int) -> bool:


    def deQueue(self) -> bool:


    def Front(self) -> int:


    def Rear(self) -> int:


    def isEmpty(self) -> bool:


    def isFull(self) -> bool:



# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()

739. 每日温度

739. 每日温度

# 描述：给定一个列表 temperatures，temperatures[i] 表示第 i 天的气温。

# 要求：输出一个列表，列表上每个位置代表「如果要观测到更高的气温，至少需要等待的天数」。如果之后的气温不再升高，则用 0 来代替。

# 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer
# 其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

class Solution:
    def dailyTemperatures(self, temperatures):
        n = len(temperatures)
        stack = []
        res = [0 for _ in range(n)]
        for i in range(n):
            temperature = temperatures[i]
            while stack and temperature > temperatures[stack[-1]]:
                index = stack.pop()
                res[index] = i - index
            stack.append(i)

        return res

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

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

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for item in s:
            if stack and stack[-1] == item:
                stack.pop()
            else:
                stack.append(item)
        return "".join(stack)

剑指 Offer 09. 用两个栈实现队列

剑指 Offer 09. 用两个栈实现队列

class CQueue:

    def __init__(self):
        self.instack = []
        self.outstack = []

    def appendTail(self, value: int) -> None:
        self.instack.append(value)

    def deleteHead(self) -> int:
        if len(self.outstack) == 0 and len(self.instack) == 0:
            return -1
        if len(self.outstack) == 0:
            while len(self.instack) != 0:
                self.outstack.append(self.instack[-1])
                self.instack.pop()
        top = self.outstack[-1]
        self.outstack.pop()
        return top


# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()