目录
栈（stack）
队列 （queue）
高频面试题(leetcode)
20. 有效的括号
232. 用栈实现队列
703 数据流中的第 K 大元素
239. 滑动窗口最大值
255. 验证前序遍历序列二叉搜索树
栈（stack）
栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
基本函数：
5. 数据结构 — Python 3.8.13 文档
[stack - C++ Reference (cplusplus.com)]
栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
队列 （queue）
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。
成员函数
- C++ Reference (cplusplus.com)">
5. 数据结构 — Python 3.8.13 文档
列表也可以用作队列，其中先添加的元素被最先取出 (“先进先出”)；然而列表用作这个目的相当低效。因为在列表的末尾添加和弹出元素非常快，但是在列表的开头插入或弹出元素却很慢 (因为所有的其他元素都必须移动一位)。
若要实现一个队列，可使用 collections.deque，它被设计成可以快速地从两端添加或弹出元素。
collections --- 容器数据类型 — Python 3.8.13 文档
高频面试题(leetcode)
20. 有效的括号
20. 有效的括号 - 力扣（LeetCode） (leetcode-cn.com)
方法：使用栈
class Solution:
def isValid(self, s: str) -> bool:
if (len(s) % 2 == 1 ):return False
stk = []
pairs = {
')':'(',
'}':'{',
']':'[',}
for ch in s:
if ch in pairs:
if not stk or pairs[ch] != stk.pop():
return False
else:
stk.append(ch)
return not stk
class Solution {
public:
bool isValid(string s) {
if (s.size() % 2) return false;
stack stk;
unordered_map pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};
for (char ch:s){
if (pairs.count(ch)){
// stk.pop() 直接删除，不会弹出
if (stk.empty() || pairs[ch] != stk.top()) return false;
stk.pop();
}
else {
stk.push(ch);
}
}
return stk.empty();
}
}; 232. 用栈实现队列
232. 用栈实现队列 - 力扣（LeetCode） (leetcode-cn.com)
232. 用栈实现队列 - 力扣（LeetCode） (leetcode-cn.com)
方法：使用两个栈
class MyQueue{
private:
stack inStack,outStack;
void in2out(){
while (!inStack.empty()){
outStack.push(inStack.top());
inStack.pop();
}
}
public:
MyQueue(){
}
void push(int x){
inStack.push(x);
}
int pop(){
if (outStack.empty()){
in2out();
}
int x = outStack.top();
outStack.pop();
return x;
}
int peek(){
if (outStack.empty()){
in2out();
}
return outStack.top();
}
bool empty(){
return inStack.empty() && outStack.empty();
}
};
class MyQueue:
def __init__(self):
self.inStack = []
self.outStack = []
def push(self, x: int) -> None:
self.inStack.append(x)
def pop(self) -> int:
if self.outStack:
return self.outStack.pop()
else:
while (self.inStack):
self.outStack.append(self.inStack.pop())
return self.outStack.pop()
def peek(self) -> int:
x = self.pop()
self.outStack.append(x)
return x
def empty(self) -> bool:
return not self.inStack and not self.outStack
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()703 数据流中的第 K 大元素
703. 数据流中的第 K 大元素 - 力扣（LeetCode） (leetcode-cn.com)
方法：优先队列
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.nums = nums
# 使用堆队列
heapq.heapify(self.nums)
def add(self, val: int) -> int:
heapq.heappush(self.nums,val)
while len(self.nums) > self.k:
heapq.heappop(self.nums)
return self.nums[0]
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)class KthLargest {
public:
int k;
priority_queue ,greater> que;
KthLargest(int k, vector& nums) {
this->k = k;
for (auto num : nums){
add(num);
}
}
int add(int val) {
que.push(val);
if (que.size() > k){
que.pop();
}
return que.top();
}
};
拓展：
heapq --- 堆队列算法 — Python 3.10.4 文档
priority_queue - C++ Reference (cplusplus.com)
239. 滑动窗口最大值
239. 滑动窗口最大值 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
priority_queue > que;
for (int i = 0;i < k;i++){
que.emplace(nums[i],i);
}
vector ans;
ans.push_back(que.top().first);
for (int i = k;i < nums.size();i++){
que.emplace(nums[i],i);
// 通过下标判断当前最大值是否在窗口K中
while (que.top().second <= i - k){
que.pop();
}
ans.push_back(que.top().first);
}
return ans;
}
}; class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
que = [(-nums[i], i) for i in range(k)]
heapq.heapify(que)
ans = []
ans.append(-que[0][0])
for i in range(k,len(nums)):
heapq.heappush(que,(-nums[i],i))
while (que[0][1] <= i-k):
heapq.heappop(que)
ans.append(-que[0][0])
return ans
255. 验证前序遍历序列二叉搜索树
255. 验证前序遍历序列二叉搜索树 - 力扣（LeetCode） (leetcode-cn.com)
待补充
(2条消息) 【LeetCode - 255】验证前序遍历序列二叉搜索树_学哥斌的博客-CSDN博客
