今天開(kāi)始講隊(duì)列和堆棧結(jié)構(gòu)献幔，另外，大家對(duì)我這個(gè)系列有什么建議盡管提蹬蚁，我會(huì)盡力寫(xiě)的清晰一點(diǎn)~

• 目錄：
  算法：附錄
  算法（1）：遞歸
  算法（2）：鏈表
  算法（3）：數(shù)組
  算法（4）：字符串
  算法（5）：二叉樹(shù)
  算法（6）：二叉查找樹(shù)
  算法（7）：隊(duì)列和堆棧（附贈(zèng)BFS和DFS）
  算法（8）：動(dòng)態(tài)規(guī)劃
  算法（9）：哈希表
  算法（10）：排序
  算法（11）：回溯法
  算法（12）：位操作

其實(shí)也就八個(gè)字：
堆棧：后進(jìn)先出（Last In First Out）
隊(duì)列：先進(jìn)先出（First In First Out）
最后再附帶兩塊騷操作代碼：（1）用堆棧實(shí)現(xiàn)隊(duì)列犀斋；（2）用隊(duì)列實(shí)現(xiàn)堆棧叽粹。

隊(duì)列（Queue）

• 順序隊(duì)列：（不好意思我又要搬圖了，锤灿，持钉，）
  （1）隊(duì)頭不動(dòng)每强，出隊(duì)列時(shí)隊(duì)頭后的所有元素向前移動(dòng) 州刽。缺陷：操作是如果出隊(duì)列比較多，要搬移大量元素辨绊，時(shí)間復(fù)雜度較高门坷。
  

  情況1
  
  （2）隊(duì)頭移動(dòng)袍镀，出隊(duì)列時(shí)隊(duì)頭向后移動(dòng)一個(gè)位置 苇羡。缺陷：如果還有新元素進(jìn)行入隊(duì)列容易造成假溢出。（假溢出：順序隊(duì)列因多次入隊(duì)列和出隊(duì)列操作后出現(xiàn)的尚有存儲(chǔ)空間但不能進(jìn)行入隊(duì)列操作的溢出锦茁。真溢出：順序隊(duì)列的最大存儲(chǔ)空間已經(jīng)存滿二又要求進(jìn)行入隊(duì)列操作所引起的溢出叉存。）
  
  情況2

• 循環(huán)隊(duì)列：用兩個(gè)指針歼捏，分配固定大小的內(nèi)存笨篷，front指向隊(duì)頭冕屯，rear指向?qū)ξ苍氐南乱粋€(gè)位置拂苹，元素出隊(duì)時(shí)front往后移動(dòng)瓢棒，如果到了對(duì)尾則轉(zhuǎn)到頭部，同理入隊(duì)時(shí)rear后移念颈，如果到了對(duì)尾則轉(zhuǎn)到頭部连霉。這樣就可以克服順序隊(duì)列時(shí)間復(fù)雜度高或假溢出問(wèn)題。
  但是如何判斷循環(huán)隊(duì)列是空還是滿窟感？（因?yàn)槿绻蛔鋈魏尾僮魇疗恚蘸蜐M時(shí)哩至，front和rear都指向同一個(gè)地方）
  這里給出三種方法：
  （1）少用一個(gè)存儲(chǔ)單元
  （2）設(shè)置一個(gè)標(biāo)記flag； 初始值 flag = 0卢佣；有元素入隊(duì)時(shí)珠漂，flag = 1尾膊；有元素出隊(duì)列時(shí)。flag = 0待笑。那么判斷標(biāo)志為下：隊(duì)列為空時(shí)：（front == rear && flag == 0）抓谴，隊(duì)列為滿時(shí)：（front == rear && flag == 1）
  （3）設(shè)置一個(gè)計(jì)數(shù)器

• 鏈?zhǔn)疥?duì)列：用鏈表做一個(gè)隊(duì)列，操作受限一下即可荆陆，使其只能在鏈表頭部刪除元素集侯，鏈表尾部添加元素。

隊(duì)列浓体，其實(shí)跟BFS更配哦~
使用BFS命浴，一般是用來(lái)找最小路徑問(wèn)題贱除，詳情可參考以下鏈接：

Queue and DFS

不帶環(huán)結(jié)構(gòu)的BFS偽代碼：（如樹(shù)結(jié)構(gòu)）

/**
 * 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
}

可能存在環(huán)結(jié)構(gòu)的BFS偽代碼：（如圖結(jié)構(gòu)月幌，其實(shí)代碼就加了一個(gè)visited變量飞醉，保存見(jiàn)過(guò)的節(jié)點(diǎn)）

/**
 * 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
}

隊(duì)列習(xí)題：

問(wèn)題1：開(kāi)密碼鎖缅帘，你手中有一個(gè)四個(gè)滾輪的密碼鎖难衰。每個(gè)滾輪有十個(gè)值：'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'（就是我們常見(jiàn)的密碼鎖啦）盖袭。每撥動(dòng)一下記為一次，然后給出一組deadends和一個(gè)target弟塞，在撥動(dòng)的過(guò)程中不能出現(xiàn)deadends里面的值拙已，求解鎖（值等于target）所需的最少次數(shù)（如果無(wú)法解開(kāi)鎖，則輸出-1）系宫。

例子1：
輸入: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
輸出: 6
解釋：最小移動(dòng)方式如下 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"扩借。注意這么走是錯(cuò)誤的： "0000" -> "0001" -> "0002" -> "0102" -> "0202" ，因?yàn)椴荒艹霈F(xiàn)"0102"這種情況康谆。

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

代碼思路：
這種求最小路徑的秉宿，一般可以考慮使用BFS屯碴，而避免陷入循環(huán)以及避免遇到deadends，我們可以使用 visited 變量保存已經(jīng)走過(guò)的路徑忱叭。下文使用了雙端隊(duì)列deque（其實(shí)就是隊(duì)列和堆棧的合體今艺，隊(duì)列兩端都可以裝數(shù)據(jù)和彈出數(shù)據(jù)）虚缎。

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)

問(wèn)題2：完全平方數(shù)（Perfect Squares）实牡。給定一個(gè)正整數(shù)n创坞，返回最小的完全平方數(shù)（1, 4, 9, 16, ...）的個(gè)數(shù)，使它們之和為n偎谁。

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

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

代碼思路：
也是利用了BFS的思路（畢竟又是求最小個(gè)數(shù)之類的問(wèn)題）纲堵。首先婉支，先看看從0到n中所有數(shù)，只需要一個(gè)完全平方數(shù)便可以到達(dá)的值有哪些（也就是1蝌以，4跟畅，9徊件，16......)，然后將這些數(shù)裝入隊(duì)列當(dāng)中睹耐；其次部翘，對(duì)該隊(duì)列當(dāng)中的每個(gè)數(shù)新思，都再加上一個(gè)完全平方數(shù)（每個(gè)數(shù)都加上1，4纵刘，9荸哟，16......當(dāng)然鞍历，結(jié)果大于n就結(jié)束），這時(shí)可以到達(dá)的值便是 最少需要兩個(gè)完全平方數(shù)才能到達(dá)的值......如此循環(huán)往復(fù)，直到第一次可以到達(dá)n秆剪，返回我們執(zhí)行循環(huán)的次數(shù)，便可收工結(jié)束爵政。

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)

問(wèn)題3：

問(wèn)題4：

問(wèn)題5：

堆棧（Stack)

??棧（stack）又名堆棧钾挟，它是一種運(yùn)算受限的數(shù)據(jù)結(jié)構(gòu)（即先進(jìn)后出的線性表）。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算徽千。這一端被稱為棧頂双抽，相對(duì)地，把另一端稱為棧底铐维。椛鞣疲可以看作一個(gè)桶露该，后放進(jìn)去的先拿出來(lái)，它下面本來(lái)有的東西要等它出來(lái)之后才能出來(lái)（先進(jìn)后出）闸拿。后一個(gè)放入堆棧中的物體總是被最先拿出來(lái)书幕， 這個(gè)特性通常稱為后進(jìn)先出(LIFO)隊(duì)列台汇。 堆棧中定義了一些操作。 兩個(gè)最重要的是PUSH和POP痒芝。 PUSH操作在堆棧的頂部加入一 個(gè)元素牵素。POP操作相反笆呆， 在堆棧頂部移去一個(gè)元素， 并將堆棧的大小減一俄精。

蘿卜配青菜竖慧，堆棧配DFS：
不出意外，能用BFS的地方也可以用DFS（反之亦然）踱讨。DFS一般也是用來(lái)解決找路徑問(wèn)題碳胳，但一般首次找到的并不是最小路徑挨约。

Stack and DFS

當(dāng)然，DFS也時(shí)常通過(guò)遞歸實(shí)現(xiàn)（有沒(méi)有發(fā)現(xiàn)翁锡，知識(shí)開(kāi)始相互滲入夕土，交錯(cuò)使用了）怨绣。
下面是DFS遞歸實(shí)現(xiàn)的偽代碼（說(shuō)句實(shí)在話，下面的代碼再稍微改一改减细，就是另一種算法未蝌，回溯法~）茧妒，表面上看起來(lái)沒(méi)有用到 Stack桐筏，但其實(shí)隱式的用到了，并且該種堆棧的準(zhǔn)確稱呼叫：調(diào)用堆棧（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;
}

使用遞歸來(lái)實(shí)現(xiàn)DFS好處就是簡(jiǎn)單易理解，但是這個(gè)需要時(shí)刻注意遞歸深度的問(wèn)題（一般情況堆棧大小等于遞歸深度）蹋笼。此時(shí)，我們就需要用到顯式的堆棧圾笨，不使用遞歸擂达。偽代碼如下：

/*
 * 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;
}

堆棧習(xí)題：

問(wèn)題1：日常溫度：給定一個(gè)表示日常溫度的數(shù)組胶滋，返回一個(gè)數(shù)組究恤，表示從當(dāng)天開(kāi)始，最少再過(guò)多久會(huì)出現(xiàn)比現(xiàn)在溫度高的天氣抄腔。如果不存在赫蛇，該值則為0雾叭。
例子：
輸入：[73, 74, 75, 71, 69, 72, 76, 73]
輸出：[1, 1, 4, 2, 1, 1, 0, 0]
代碼思路：注意兩個(gè)循環(huán)拷况，一個(gè)for循環(huán)，遍歷該溫度數(shù)組粟誓，一個(gè)while循環(huán)鹰服，將所有滿足條件的值從stack當(dāng)中彈出揽咕。

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)

問(wèn)題2：逆波蘭表示法（Evaluate Reverse Polish Notation）（這個(gè)問(wèn)題我們?cè)?jīng)在二叉樹(shù)章節(jié)提到過(guò)亲善，也就是后綴表示法）
例子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)

問(wèn)題3：求目標(biāo)和（Target Sum）顿肺。給定一個(gè)數(shù)組以及一個(gè)目標(biāo)數(shù)S屠尊，你可以給數(shù)組中每個(gè)數(shù)分配 運(yùn)算符‘+’ 或 ‘-’ 其中之一，使得數(shù)組之和為目標(biāo)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
代碼解析：其實(shí)就是遞歸到末端掺炭，如果s-nums[-1] ==0或者s + nums[-1] == 0涧狮，返回1，否則返回0肤视。（如果s ==nums[-1] ==0涉枫，則返回2）愿汰，然后我們把這個(gè)返回值累加即可。其中用了記憶機(jī)制hm摇予，減少了遞歸調(diào)用次數(shù)（不用hm也行侧戴，但是會(huì)TLE跌宛，即Time Limit Exceeded）疆拘。

class Solution:
    def findTargetSumWays(self, nums: list, S: int, ) -> int:
        def _helper(s,idx,hm):
            if (s,idx) in hm:   #搞個(gè)備忘錄，降低遞歸的復(fù)雜度
                return hm[(s,idx)]
            if idx == len(nums)-1:
                return (s == nums[idx]) + (s == -nums[idx])   #到達(dá)列表末端回右，返回 0，1楣黍，2（當(dāng)s=nums[-1]=0時(shí)為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))

問(wèn)題4：二叉樹(shù)前中后序遍歷，詳情見(jiàn)算法（5）：二叉樹(shù)棱烂。

問(wèn)題5：

附錄：

堆棧實(shí)現(xiàn)隊(duì)列：思路是有兩個(gè)棧租漂，一個(gè)用來(lái)放數(shù)據(jù)（數(shù)據(jù)棧），一個(gè)用來(lái)輔助（輔助棧）颊糜。數(shù)據(jù)添加時(shí)哩治，會(huì)依次壓人棧，取數(shù)據(jù)時(shí)肯定會(huì)取棧頂元素衬鱼，但我們想模擬隊(duì)列的先進(jìn)先出业筏，所以就得取棧底元素鸟赫，那么輔助棧就派上用場(chǎng)了蒜胖，把數(shù)據(jù)棧的元素依次彈出到輔助棧，然后從輔助棧彈出元素即可（大家想想是不是有點(diǎn)負(fù)負(fù)得正的感覺(jué)）抛蚤。當(dāng)有新數(shù)據(jù)進(jìn)入是台谢，繼續(xù)將數(shù)據(jù)放入數(shù)據(jù)棧，而又想彈出數(shù)據(jù)時(shí)岁经，如果輔助棧有元素朋沮，我們就直接彈，如果沒(méi)有缀壤，再重新將數(shù)據(jù)棧數(shù)據(jù)全部放入輔助棧當(dāng)中樊拓。以此類推。

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)

隊(duì)列實(shí)現(xiàn)堆棧：也是需要兩個(gè)隊(duì)列塘慕，數(shù)據(jù)隊(duì)列和輔助隊(duì)列筋夏。進(jìn)數(shù)據(jù)時(shí)進(jìn)入數(shù)據(jù)隊(duì)列，彈出數(shù)據(jù)時(shí)使用輔助隊(duì)列苍糠。模擬棧的先進(jìn)后出叁丧，隊(duì)列是隊(duì)尾進(jìn)隊(duì)頭出，也就是說(shuō)每次取值要取隊(duì)列的隊(duì)尾元素岳瞭，數(shù)據(jù)隊(duì)列出隊(duì)到輔助隊(duì)列拥娄，留下最后一個(gè)元素返回。此時(shí)我們讓數(shù)據(jù)隊(duì)列和輔助隊(duì)列換個(gè)名字（相當(dāng)于之后再進(jìn)數(shù)據(jù)瞳筏，進(jìn)入原來(lái)的輔助隊(duì)列稚瘾，即現(xiàn)在的數(shù)據(jù)隊(duì)列當(dāng)中），以此類推姚炕。

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):
        #重點(diǎn)放在這里摊欠，用了雙端隊(duì)列丢烘，
        #循環(huán)的長(zhǎng)度不是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)