栈与队列1.栈与队列理论基础栈和队列是STLC标准库里面的两个数据结构队列是先进先出栈是先进后出其中栈是以底层容器完成其所有的工作对外提供统一的接口底层容器是可插拔的就是说我们可以控制使用哪种容器来实现栈的功能队列中先进先出的数据结构同样不允许有遍历行为不提供迭代器SGI STL指的是标准模板库STL史上一个里程碑式的实现版本中队列一样是以deque指的是一个双向队列为缺省情况下的底部结构2.用栈实现队列使用栈实现队列的下列操作push(x)--将一个元素放入队列的尾部pop()--从队列首部移除元素peek()--返回队列首部的元素empty()--返回队列是否为空这个题目是一道模拟题不涉及到具体的算法就是考察会栈和队列的掌握程度。这里用到了两个栈一个输出一个输入,这道题的力扣是编号232题我在这里给出代码3.用队列实现栈使用队列实现栈的下列操作push(x)--元素x入栈pop()--移除栈顶元素top()--获取栈顶元素empty()--返回栈是否为空然后这里用队列模拟栈用一个队列就够了。一个队列在模拟栈弹出元素的时候只要将队列头部的元素除了最后一个元素外重新添加到队列尾部此时再去弹出元素就是栈的顺序了。力扣题目编号225题我在这里给出代码4.有效的括号有效字符串需满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。这道题就是利用栈结构的特殊性来做这个对称匹配类的题。这道题的力扣编号为20题我在这里给出代码5.删除字符串中的所有相邻重复项这个题目和上面这个题目有点相似也是匹配问题这个题目是匹配相邻元素到最后都是做消除的操作力扣题目编号1047题我在这里给出代码6.逆波兰表达式求值逆波兰表达式是一种后缀表达式所谓后缀就是指运算符写在后面例如正常我们看到的是1 2*3 4逆波兰表达式是1 2 3 4 *这个表达式就方便在去掉括号没有歧义还有就是方便入栈这道题目的力扣编号是150题我在这里给出代码7.滑动窗口最大值这个题目就需要用到一个队列放进去的元素随着窗口移动队列也一进一出每次移动之后队列告诉我们里面的最大值是什么每次窗口移动的时候调用que.pop(滑动窗口中移除元素的数值)que.push(滑动窗口添加元素的数值)然后que.front()就返回我们要的最大值。这里利用deque做底层容器来实现单调队列这个题目的力扣编号为239题我在这里给出代码8.前K个高频元素这个题目主要涉及三个内容1.要统计元素出现频率2.对频率排序3.找出前k个高频元素用map来统计出现频率用优先级队列是一个看起来像队列的堆对部分频率排序利用小顶堆从小到大排列统计最大前k个元素只有小顶堆每次将最小的元素弹出最后小顶堆积累的才是前k个最大元素这道题目的力扣编号为347题我在这里给出代码ok,到这里代码随想录的栈的部分已经结束了有问题欢迎指出。