第04课丨01栈和队列的实现与特性

一、栈和队列的结构

栈（先进后出的容器）

队列（先进先出，依次排列）

需要牢记的关键点：

Stack：先进后出（FILO）；添加、删除皆为O(1)，查询是O(n)
Queue：先进先出；添加、删除皆为O(1)，查询是O(n)

小结：

所有的东西，都是现实中已有的逻辑，我们进行一个抽象，然后用计算机语言来进行表达：

如果一个问题，具有所谓的最近相关性 ---> 用栈来解决。（最近相关性：很多现实的问题，反映到工程里面，都具有这种从外向内或者从内向外逐渐扩散，最外层与最外层是一对，最内层与最内层是一对）
还有一种就是先来后到，讲所谓的公平性 ---> 用队列来解决

某些时候解决一些特殊的问题：

只用栈实现队列 ---> 用两个栈
只用队列实现栈 ---> 用两个队列

栈附例
leetcode20 有效的括号

class Solution:
    def isValid(self, s: str) -> bool:
        stack, match = [], {')': '(', ']': '[', '}': '{'}
        for ch in s:
            if ch in match:
                if not (stack and stack.pop() == match[ch]):
                    return False
            else:
                stack.append(ch)
        return not stack

155. 最小栈

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        if not self.stack:
            self.stack.append((x, x))
        else:
            self.stack.append((x, min(x, self.stack[-1][1])))
        

    def pop(self):
        """
        :rtype: void
        """
        self.stack.pop()
        

    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1][0]
        

    def getMin(self):
        """
        :rtype: int
        """
        return self.stack[-1][1]

84. 柱状图中最大的矩形

二、双端队列（Deque - double ended queue）

理解为Queue和Stack的结合体，两端可以进出的Queue，
插入和删除都是O(1)操作；查询是O(n)的，因为这个元素是没有任何顺序的

双端队列

双端队列附例：
leetcode 滑动窗口最大值 239leetcode-cn.com

# 所有滑动窗口的题目，用双端队列去处理就行了。
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        deque = collections.deque()
        res = []
        for i, num in enumerate(nums):
            while deque and deque[0] <= i - k: deque.popleft()
            while deque and num > nums[deque[-1]]: deque.pop()
            deque.append(i)
            if i >= k - 1:
                res.append(nums[deque[0]])
        return res

三、Stack、Queue、Deque的工程实现

Java、Python、c++等已有基础实现

# Stack的Python实现及常用API
class Stack:
    def __init__(self):
        self.items = ["x","y"]
    def push(self,item):
        self.items.append(item)
    def pop(self):
        self.items.pop()
    def length(self):
        return len(self.items)

# Queue的Python实现及常用API
class Queue:
    def __init__(self):
        self.queue = []
    def enqueue(self,item):
        self.queue.append(item)
    def dequeue(self):
        if len(self.queue)<1:
            return None
        return self.queue.pop(0)
    def size(self):
        return len(self.queue)