文章目录

• • • 一、栈和队列
    • • 1. 栈
      • • （1）栈的基础知识
        • （2）栈的函数
      • 2. 队列
      • • （1）队列的基础知识
        • （2）队列的函数
    • 二、leetcode例题讲解栈和队列问题
    • • 1. 基础题目
      • • 232. 用栈实现队列
        • 225. 用队列实现栈
      • 2. 栈的经典问题
      • • （1） 括号匹配问题
        • • 20. 有效的括号
        • （2） 字符串去重问题
        • • 1047. 删除字符串中的所有相邻重复项
        • （3）逆波兰表达式问题
        • • 150. 逆波兰表达式求值
      • 3. 队列的经典问题
      • • （1）滑动窗口最大值问题
        • • 239. 滑动窗口最大值
        • （2）求前 K 个高频元素问题
        • • 347. 前 K 个高频元素
    • 三、其它算法分析

一、栈和队列

队列是先进先出，栈是先进后出。

1. 栈

（1）栈的基础知识

Java Stack类，栈是Vector的一个子类，实现后进先出的栈。

Stack stackA = new Stack();

栈是一种 “特殊” 的线性存储结构，因此栈的具体实现有以下两种方式：

1. 顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；
2. 链栈：采用链式存储结构实现栈结构；

（2）栈的函数

Stack<Integer> stack = new Stack<Integer>();//建栈
stack.push(Element);//进栈
stack.pop();//出栈
stack.peek();//取栈顶值（不出栈）
stack.isEmpty();//判断栈是否为空

2. 队列

（1）队列的基础知识

LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

Queue<String> queue = new LinkedList<String>();

队列存储结构的实现有以下两种方式：

1. 顺序队列：在顺序表的基础上实现的队列结构；
2. 链队列：在链表的基础上实现的队列结构；

（2）队列的函数

添加：queue.offer() queue.add()
删除队列第一个元素：queue.poll()返回null queue.remove()返回异常
查询队列头部元素：peek()返回null element()返回异常

二、leetcode例题讲解栈和队列问题

1. 基础题目

232. 用栈实现队列

leetcode题目链接：232. 用栈实现队列

225. 用队列实现栈

leetcode题目链接：225. 用队列实现栈

2. 栈的经典问题

（1） 括号匹配问题

20. 有效的括号

leetcode题目链接：20. 有效的括号

（2） 字符串去重问题

1047. 删除字符串中的所有相邻重复项

leetcode题目链接： 1047. 删除字符串中的所有相邻重复项

（3）逆波兰表达式问题

150. 逆波兰表达式求值

leetcode题目链接：150. 逆波兰表达式求值

3. 队列的经典问题

（1）滑动窗口最大值问题

239. 滑动窗口最大值

leetcode题目链接：239. 滑动窗口最大值

（2）求前 K 个高频元素问题

347. 前 K 个高频元素

leetcode题目链接：347. 前 K 个高频元素

三、其它算法分析

参考：

代码随想录：栈和队列

算法（Java）——栈、队列、堆