一给涕、棧和隊(duì)列的結(jié)構(gòu)
棧（先進(jìn)后出的容器）
隊(duì)列（先進(jìn)先出够庙，依次排列）
需要牢記的關(guān)鍵點(diǎn)：
- Stack：先進(jìn)后出（FILO）；添加昼榛、刪除皆為O(1)胆屿，查詢是O(n)
- Queue：先進(jìn)先出；添加非迹、刪除皆為O(1)憎兽，查詢是O(n)
小結(jié)：
所有的東西，都是現(xiàn)實(shí)中已有的邏輯纯命，我們進(jìn)行一個(gè)抽象，然后用計(jì)算機(jī)語(yǔ)言來(lái)進(jìn)行表達(dá)：
- 如果一個(gè)問(wèn)題亿汞，具有所謂的最近相關(guān)性 ---> 用棧來(lái)解決疗我。（最近相關(guān)性：很多現(xiàn)實(shí)的問(wèn)題，反映到工程里面碍粥，都具有這種從外向內(nèi)或者從內(nèi)向外逐漸擴(kuò)散嚼摩，最外層與最外層是一對(duì)枕面，最內(nèi)層與最內(nèi)層是一對(duì)）
- 還有一種就是先來(lái)后到缚去，講所謂的公平性 ---> 用隊(duì)列來(lái)解決
某些時(shí)候解決一些特殊的問(wèn)題：
- 只用棧實(shí)現(xiàn)隊(duì)列 ---> 用兩個(gè)棧
- 只用隊(duì)列實(shí)現(xiàn)棧 ---> 用兩個(gè)隊(duì)列
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. 柱狀圖中最大的矩形
二枕荞、雙端隊(duì)列（Deque - double ended queue）
- 理解為Queue和Stack的結(jié)合體躏精，兩端可以進(jìn)出的Queue，
- 插入和刪除都是O(1)操作矗烛；查詢是O(n)的瞭吃，因?yàn)檫@個(gè)元素是沒(méi)有任何順序的
雙端隊(duì)列
雙端隊(duì)列附例：
leetcode 滑動(dòng)窗口最大值 239?leetcode-cn.com
# 所有滑動(dòng)窗口的題目歪架，用雙端隊(duì)列去處理就行了开泽。
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的工程實(shí)現(xiàn)
- Java泣崩、Python、c++等已有基礎(chǔ)實(shí)現(xiàn)
# Stack的Python實(shí)現(xiàn)及常用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實(shí)現(xiàn)及常用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)
- 如何查詢接口信息凯沪？如何使用买优？(Java 舉例)
Stack的Java接口調(diào)用及常用API
Queue的Java接口調(diào)用及常用API
Deque的Java接口調(diào)用及常用API
四烘跺、優(yōu)先隊(duì)列（Priority queue)
優(yōu)先隊(duì)列也是一個(gè)接口脂崔，或者是定義的一種抽象的數(shù)據(jù)結(jié)構(gòu)砌左，底層有很多不同的實(shí)現(xiàn)。
插入操作是O(1)
取出操作是O(logN) - 按照元素的優(yōu)先級(jí)取出
底層具體實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)較為多樣和復(fù)雜：
heap(多種形式實(shí)現(xiàn)的文搂，不一定是二叉樹(shù))
bst(binary search tree) ---> 二叉搜索樹(shù)秤朗、也可以是平衡二叉樹(shù)實(shí)現(xiàn)取视，比如紅黑樹(shù)、AVL
treap(高級(jí)數(shù)據(jù)結(jié)構(gòu))
小結(jié)
- Stack稽物、Queue折欠、Deque的原理和操作復(fù)雜度
- PriorityQueue的特點(diǎn)和操作復(fù)雜度
- 查詢Stack、Queue咪奖、Deque羊赵、PriorityQueue的系統(tǒng)接口的方法
image.png
兩個(gè)棧實(shí)現(xiàn)隊(duì)列+兩個(gè)隊(duì)列實(shí)現(xiàn)棧----java
