算法（7）：队列和堆栈（附赠BFS和DFS）

今天开始讲队列和堆栈结构，另外，大家对我这个系列有什么建议尽管提，我会尽力写的清晰一点~

其实也就八个字：
堆栈：后进先出（Last In First Out）
队列：先进先出（First In First Out）
最后再附带两块骚操作代码：（1）用堆栈实现队列；（2）用队列实现堆栈。

队列（Queue）

  • 顺序队列：（不好意思我又要搬图了，，，）
    （1）队头不动，出队列时队头后的所有元素向前移动 。缺陷：操作是如果出队列比较多，要搬移大量元素，时间复杂度较高。

    情况1

    （2）队头移动，出队列时队头向后移动一个位置 。缺陷：如果还有新元素进行入队列容易造成假溢出。（假溢出：顺序队列因多次入队列和出队列操作后出现的尚有存储空间但不能进行入队列操作的溢出。真溢出：顺序队列的最大存储空间已经存满二又要求进行入队列操作所引起的溢出。）
    情况2

  • 循环队列：用两个指针，分配固定大小的内存，front指向队头，rear指向对尾元素的下一个位置，元素出队时front往后移动，如果到了对尾则转到头部，同理入队时rear后移，如果到了对尾则转到头部。这样就可以克服顺序队列时间复杂度高或假溢出问题。
    但是如何判断循环队列是空还是满？（因为如果不做任何操作，空和满时，front和rear都指向同一个地方）
    这里给出三种方法：
    （1）少用一个存储单元
    （2）设置一个标记flag； 初始值 flag = 0；有元素入队时，flag = 1；有元素出队列时。flag = 0。那么判断标志为下：队列为空时：（front == rear && flag == 0），队列为满时：（front == rear && flag == 1）
    （3）设置一个计数器

  • 链式队列：用链表做一个队列，操作受限一下即可，使其只能在链表头部删除元素，链表尾部添加元素。

队列，其实跟BFS更配哦~
使用BFS，一般是用来找最小路径问题，详情可参考以下链接：

Queue and DFS

不带环结构的BFS伪代码：（如树结构）

/**
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                add next to queue;
            }
            remove the first node from queue;
        }
    }
    return -1;          // there is no path from root to target
}

可能存在环结构的BFS伪代码：（如图结构，其实代码就加了一个visited变量，保存见过的节点）

/**
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    Set<Node> visited;  // store all the nodes that we've visited
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    add root to visited;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                if (next is not in used) {
                    add next to queue;
                    add next to visited;
                }
                remove the first node from queue;   
            }
        }
    }
    return -1;          // there is no path from root to target
}
队列习题：

问题1：开密码锁，你手中有一个四个滚轮的密码锁。每个滚轮有十个值：'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'（就是我们常见的密码锁啦）。每拨动一下记为一次，然后给出一组deadends和一个target，在拨动的过程中不能出现deadends里面的值，求解锁（值等于target）所需的最少次数（如果无法解开锁，则输出-1）。

例子1：
输入: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出: 6
解释：最小移动方式如下 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。注意这么走是错误的： "0000" -> "0001" -> "0002" -> "0102" -> "0202" ，因为不能出现"0102"这种情况。

例子2：
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出: -1

代码思路：
这种求最小路径的，一般可以考虑使用BFS，而避免陷入循环以及避免遇到deadends，我们可以使用 visited 变量保存已经走过的路径。下文使用了双端队列deque（其实就是队列和堆栈的合体，队列两端都可以装数据和弹出数据）。

from collections import deque
class Solution:
    def openLock(self, deadends: list, target: str) -> int:
        marker, depth = 'x', -1
        visited, q = set(deadends), deque(['0000'])

        while q:
            size = len(q)
            depth += 1
            for _ in range(size):
                node = q.popleft()
                if node == target: return depth
                if node in visited: continue
                visited.add(node)
                q.extend(self.successors(node))
        return -1

    def successors(self, src):
        res = []
        for i, ch in enumerate(src):
            num = int(ch)
            res.append(src[:i] + str((num - 1) % 10) + src[i+1:])
            res.append(src[:i] + str((num + 1) % 10) + src[i+1:])
        return res

if __name__ == '__main__':
    deadends = ["0201", "0101", "0102", "1212", "2002"]
    target = "0202"
    solution = Solution()
    steps = solution.openLock(deadends,target)
    print(steps)

    deadends = ["8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"]
    target = "8888"
    steps = solution.openLock(deadends, target)
    print(steps)

问题2：完全平方数（Perfect Squares）。给定一个正整数n，返回最小的完全平方数（1, 4, 9, 16, ...）的个数，使它们之和为n。

例子：
输入: n = 12
输出: 3 （ 12 = 4 + 4 + 4.）

例子2：
输入: n = 13
输出: 2（ 13 = 4 + 9.）

代码思路：
也是利用了BFS的思路（毕竟又是求最小个数之类的问题）。首先，先看看从0到n中所有数，只需要一个完全平方数便可以到达的值有哪些（也就是1，4，9，16......)，然后将这些数装入队列当中；其次，对该队列当中的每个数，都再加上一个完全平方数（每个数都加上1，4，9，16......当然，结果大于n就结束），这时可以到达的值便是 最少需要两个完全平方数才能到达的值......如此循环往复，直到第一次可以到达n，返回我们执行循环的次数，便可收工结束。

class Solution:
    def numSquares(self, n: int) -> int:
        q1 = [0]
        q2 = []
        level = 0
        visited = [False] * (n + 1)
        while True:
            level += 1
            for v in q1:
                i = 0
                while True:
                    i += 1
                    t = v + i * i
                    if t == n: return level
                    if t > n: break
                    if visited[t]: continue
                    q2.append(t)
                    visited[t] = True
            q1 = q2
            q2 = []

        return 0

if __name__ == '__main__':
    solution = Solution()
    steps = solution.numSquares(12)
    print(steps)

    steps = solution.numSquares(13)
    print(steps)

问题3：

问题4：

问题5：

堆栈（Stack)

  栈（stack）又名堆栈，它是一种运算受限的数据结构（即先进后出的线性表）。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。栈可以看作一个桶，后放进去的先拿出来，它下面本来有的东西要等它出来之后才能出来（先进后出）。后一个放入堆栈中的物体总是被最先拿出来， 这个特性通常称为后进先出(LIFO)队列。 堆栈中定义了一些操作。 两个最重要的是PUSH和POP。 PUSH操作在堆栈的顶部加入一 个元素。POP操作相反， 在堆栈顶部移去一个元素， 并将堆栈的大小减一。

萝卜配青菜，堆栈配DFS：
不出意外，能用BFS的地方也可以用DFS（反之亦然）。DFS一般也是用来解决找路径问题，但一般首次找到的并不是最小路径。

Stack and DFS

当然，DFS也时常通过递归实现（有没有发现，知识开始相互渗入，交错使用了）。
下面是DFS递归实现的伪代码（说句实在话，下面的代码再稍微改一改，就是另一种算法，回溯法~），表面上看起来没有用到 Stack，但其实隐式的用到了，并且该种堆栈的准确称呼叫：调用堆栈（Call stack）。

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(Node cur, Node target, Set<Node> visited) {
    return true if cur is target;
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visted;
            return true if DFS(next, target, visited) == true;
        }
    }
    return false;
}

使用递归来实现DFS好处就是简单易理解，但是这个需要时刻注意递归深度的问题（一般情况堆栈大小等于递归深度）。此时，我们就需要用到显式的堆栈，不使用递归。伪代码如下：

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(int root, int target) {
    Set<Node> visited;
    Stack<Node> stack;
    add root to stack;
    while (s is not empty) {
        Node cur = the top element in stack;
        remove the cur from the stack;
        return true if cur is target;
        for (Node next : the neighbors of cur) {
            if (next is not in visited) {
                add next to visited;
                add next to stack;
            }
        }
    }
    return false;
}
堆栈习题：

问题1：日常温度：给定一个表示日常温度的数组，返回一个数组，表示从当天开始，最少再过多久会出现比现在温度高的天气。如果不存在，该值则为0。
例子：
输入：[73, 74, 75, 71, 69, 72, 76, 73]
输出：[1, 1, 4, 2, 1, 1, 0, 0]
代码思路：注意两个循环，一个for循环，遍历该温度数组，一个while循环，将所有满足条件的值从stack当中弹出。

class Solution:
    def dailyTemperatures(self, T: list) -> list:
        ans = len(T) * [0]
        stack = []
        for i in range(len(T)):
            while stack != [] and T[stack[-1]] < T[i]:
                j = stack.pop()
                ans[j] = i - j
            stack.append(i)
        return ans

if __name__ == '__main__':
    T = [73, 74, 75, 71, 69, 72, 76, 73]
    solution = Solution()
    steps = solution.dailyTemperatures(T)
    print(steps)

问题2：逆波兰表示法（Evaluate Reverse Polish Notation）（这个问题我们曾经在二叉树章节提到过，也就是后缀表示法）
例子1：
输入：["2", "1", "+", "3", "*"]
输出：9 （解释：((2 + 1) * 3) = 9）

例子2：
输入：["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

class Solution:
    def evalRPN(self, tokens: list) -> int:
        stack = []
        for t in tokens:
            if t not in ["+", "-", "*", "/"]:
                stack.append(int(t))
            else:
                r, l = stack.pop(), stack.pop()
                if t == "+":
                    stack.append(l+r)
                elif t == "-":
                    stack.append(l-r)
                elif t == "*":
                    stack.append(l*r)
                else:
                    # here take care of the case like "1/-22",
                    # in Python 3.x, it returns -1, while in
                    # Leetcode it should return 0
                    if l*r < 0 and l % r != 0:
                        stack.append(l//r+1)
                    else:
                        stack.append(l//r)
        return stack.pop()

if __name__ == '__main__':
    T = ["2", "1", "+", "3", "*"]
    solution = Solution()
    steps = solution.evalRPN(T)
    print(steps)

问题3：求目标和（Target Sum）。给定一个数组以及一个目标数S，你可以给数组中每个数分配 运算符‘+’ 或 ‘-’ 其中之一，使得数组之和为目标S。输出共有多少种分配方式。
输入: nums is [1, 1, 1, 1, 1], S is 3.
输出: 5
解释:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
代码解析：其实就是递归到末端，如果s-nums[-1] ==0或者s + nums[-1] == 0，返回1，否则返回0。（如果s ==nums[-1] ==0，则返回2），然后我们把这个返回值累加即可。其中用了记忆机制hm，减少了递归调用次数（不用hm也行，但是会TLE，即Time Limit Exceeded）。

class Solution:
    def findTargetSumWays(self, nums: list, S: int, ) -> int:
        def _helper(s,idx,hm):
            if (s,idx) in hm:   #搞个备忘录，降低递归的复杂度
                return hm[(s,idx)]
            if idx == len(nums)-1:
                return (s == nums[idx]) + (s == -nums[idx])   #到达列表末端，返回 0，1，2（当s=nums[-1]=0时为2）
            return hm.setdefault((s,idx), _helper(s + nums[idx], idx+1,hm) + _helper(s - nums[idx], idx+1,hm))
        return _helper(S,0,{})

if __name__ == '__main__':
    nums = [1, 1, 1, 1, 1]
    S = 3.
    solution = Solution()
    steps = solution.findTargetSumWays(nums,S)
    print(steps)
    print((0==0) + (0==0))

问题4：二叉树前中后序遍历，详情见算法（5）：二叉树。

问题5：

附录：

堆栈实现队列：思路是有两个栈，一个用来放数据（数据栈），一个用来辅助（辅助栈）。数据添加时，会依次压人栈，取数据时肯定会取栈顶元素，但我们想模拟队列的先进先出，所以就得取栈底元素，那么辅助栈就派上用场了，把数据栈的元素依次弹出到辅助栈，然后从辅助栈弹出元素即可（大家想想是不是有点负负得正的感觉）。当有新数据进入是，继续将数据放入数据栈，而又想弹出数据时，如果辅助栈有元素，我们就直接弹，如果没有，再重新将数据栈数据全部放入辅助栈当中。以此类推。

class MyQueue:

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

    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.inStack.append(x)

    def pop(self):
        """
        :rtype: int
        """
        self.move()
        return self.outStack.pop()

    def peek(self):
        """
        :rtype: int
        """
        self.move()
        return self.outStack[-1]

    def empty(self):
        """
        :rtype: bool
        """
        return (not self.inStack) and (not self.outStack)

    def move(self):
        """
        :rtype nothing
        """
        if not self.outStack:
            while self.inStack:
                self.outStack.append(self.inStack.pop())

if __name__ == '__main__':
    queue = MyQueue()

    a = queue.push(1)
    b = queue.push(2)
    c = queue.peek()
    d = queue.pop()
    e = queue.empty()
    print(a,b,c,d,e)

队列实现堆栈：也是需要两个队列，数据队列和辅助队列。进数据时进入数据队列，弹出数据时使用辅助队列。模拟栈的先进后出，队列是队尾进队头出，也就是说每次取值要取队列的队尾元素，数据队列出队到辅助队列，留下最后一个元素返回。此时我们让数据队列和辅助队列换个名字（相当于之后再进数据，进入原来的辅助队列，即现在的数据队列当中），以此类推。

import collections
class MyStack:

    def __init__(self):
        self.stack = collections.deque([])

    # @param x, an integer
    # @return nothing
    def push(self, x):
        self.stack.append(x)

    # @return nothing
    def pop(self):
        #重点放在这里，用了双端队列，
        #循环的长度不是len(self.stack)，而是其减一。
        for i in range(len(self.stack) - 1):   
            self.stack.append(self.stack.popleft())

        return self.stack.popleft()

    # @return an integer
    def top(self):
        return self.stack[-1]

    # @return an boolean
    def empty(self):
        return len(self.stack) == 0

if __name__ == '__main__':
    stack = MyStack()
    a = stack.push(1)
    b = stack.push(2)
    c = stack.top()
    d = stack.pop()
    e = stack.empty()
    print(a,b,c,d,e)
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,723评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,003评论 3赞 391
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 161,512评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,825评论 1赞 290
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,874评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,841评论 1赞 295
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,812评论 3赞 416
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,582评论 0赞 271
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,033评论 1赞 308
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,309评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,450评论 1赞 345
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,158评论 5赞 341
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,789评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,409评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,609评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,440评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,357评论 2赞 352