棧

特點是隻能從一端（棧頂）操作元素，先進後出（FILO），操作主要包含出棧 ；入棧；獲取棧頂元素；判斷棧是否已滿（陣列棧）；判斷棧是否為空棧。

邏輯結構分類陣列棧棧的空間大小固定並且需要一次性申請。需要使用一個指標指向棧頂位置；棧為空時指標指向-1。連結串列棧棧空間上限取決於記憶體空間。入棧和出棧操作在連結串列的頭指標處，時間複雜度為O(1)。示例

設計一個棧，除了常規棧支援的pop與push函式以外，還支援min函式，該函式返回棧元素中的最小值。執行push、pop和min操作的時間複雜度必須為O(1)。

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); --> 返回 -3.

minStack.pop();

minStack.top(); --> 返回 0.

minStack.getMin(); --> 返回 -2.

class MinStack(object):    def __init__(self):        """        initialize your data structure here.        s: 陣列棧        m: 棧s中的最小元素        t: 臨時棧,s的輔助棧        pop操作由於將s中元素壓入到t中，所以時間複雜度為O(n); push和getMin操作時間複雜度為O(1)        """        self.s = []        self.m = None        self.t = []    def push(self, x):        """        :type x: int        :rtype: None        入棧        1: 如果x為第一個入棧元素，則為最小值，將x賦值給m        2: x < m 說明剛入棧的元素x為最小值，將x賦值給m        """        # x入棧        self.s.append(x)        if self.m is None:            self.m = x        else:            if self.m > x:                self.m = x                def pop(self):        """        :rtype: None        出棧        1: 如果s棧頂元素不是最小元素，則直接彈出s棧頂元素        2: s棧頂元素為最小元素:        2.1 將s中剩餘元素的棧頂元素賦值給m（當作最小元素）        2.2 將s中元素依次壓入t中，並與m比較，將小的值記錄到m中        2.3 將t中元素壓入s中        m記錄的為s中剩餘元素的最小值        """        r = self.s.pop()        if r == self.m:            self.m = None            if len(self.s):                self.m = self.s[-1]                        while len(self.s):                if self.s[-1] < self.m:                    self.m = self.s[-1]                self.t.append(self.s.pop())                        while len(self.t):                self.s.append(self.t.pop())    def top(self):        """        :rtype: int        返回棧頂元素        """        return self.s[-1]    def getMin(self):        """        :rtype: int        """        return self.m

示意圖佇列

允許從其中一端將元素寫入，從另一端進行移出。特點是先進先出（FIFO）。操作主要包含入隊；出隊；獲取隊首元素；判斷佇列是否已滿（陣列佇列）；判斷佇列是否為空。

邏輯結構分類陣列佇列從陣列一端入隊，從另一端進行出隊操作。空佇列存在兩種情況：隊首等於隊尾等於0；隊首等於隊尾等於陣列大小（N）-1，使用單獨一個變數標識佇列是滿佇列還是空佇列。迴圈佇列空出一個空間用來判斷是空佇列還是滿佇列情況（否則空佇列和滿佇列情況時隊首和隊尾指標相同）。空佇列時隊首指標和隊尾指標相同。滿佇列時隊首指標加1模上陣列大小（N）等於隊尾指標。連結串列佇列隊首指標指向頭節點；隊尾指標指向尾節點。入隊從頭節點位置操作；出隊從尾節點位置操作。示例

給定一個數組 nums 和滑動視窗的大小 k，請找出所有滑動窗口裡的最大值。

輸入: 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

class Solution(object):    def maxSlidingWindow(self, nums, k):        """        :type nums: List[int] 列表        :type k: int 視窗大小        :rtype: List[int]        1. 如果t中沒有元素，則將當前下標和元素值組成的元組(idx, nums[idx])追加到t中        2. 如果t中的第一個元素的下標小於當前視窗的最小下標或者第一個元素的值小於當前元素，t執行彈出第一個元素操作，直到不滿足上面兩個條件，將當前元素和下標(idx, nums[idx])追加到t中。        3. 如果當前下標 大於等於k-1,說明在視窗內，將t中的第一個元素的值（當前視窗中最大值）追加到r中。        3.1 追加之前向將佇列中小於當前元素的元素彈出(從右側彈出)。        4. 遍歷陣列重複1－3的操作。        """        # 記錄視窗中的元素（元素下標，元素值）:雙端佇列        t  = []        # 記錄每個視窗中的最大值        r = []        # 當前遍歷的下標        idx = 0        # 陣列nums的長度        l = len(nums)        while idx < l:            # 判斷條件2和3            # t[0][0] < idx + 1 - k  : 判斷t中的第一個元素（視窗中的最大值）是否在視窗內，不在視窗內需要移除            # t[0][1] < nums[idx] : 判斷t中第一個元素是否是當前視窗內的最大值，不是的話需要移除；否則將當前視窗中的其它元素追加到t中（不是當前視窗的最大值，可能是下一個視窗的最大值）            while t and (t[0][0] < idx + 1 - k or t[0][1] < nums[idx]):                t.pop(0)            # 因為元素會順序追加到t中,，經過上面的判斷，t中的元素都在一個視窗內            # 在追加當前元素之前，先將當前視窗內小於當前元素的元素移除            while t and t[-1][1] < nums[idx]:                t.pop()            t.append((idx,nums[idx]))            # 記錄視窗中的最大值            if idx >= k - 1:                r.append(t[0][1])                        idx += 1                return r

示意圖