特点是只能从一端（栈顶）操作元素，先进后出（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
- 示意图
,
