栈Stack和队列Queue

embedded/2024/11/19 13:05:23/

目录

一、栈

（1）用数组实现

（2）用单链表实现

（3）用标注尾结点的单链表实现

（4）用双向链表实现

2、栈的实际应用

（1）改变元素的序列

（2）将递归转化为循环（逆序打印链表）

（3）括号匹配

（4）逆波兰表达式求值

（5）出栈入栈次序匹配

（6）最小栈

二、队列

1、队列的使用

 2、队列的模拟实现

3、循环队列

4、双端队列Deque

 三、面试题

1、用栈实现队列

2、用队列实现栈

一、栈

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作

进行数据插入和删除操作的一端称为栈顶，另一端称为栈底

栈中的数据元素遵守后进先出的原则

  • 压栈/进栈/入栈：栈的插入操作
  • 出栈：栈的删除操作
方法
功能
Stack()构造一个空的栈
E push(E e)将e入栈，并返回e
E pop()将栈顶元素出栈并返回
E peek()获取栈顶元素
int size()获取栈中有效元素个数
boolean empty()检测栈是否为空

1、栈的模拟实现

（1）用数组实现
（2）用单链表实现

  • 若使用尾插法，则入栈时间复杂度为O(n)，出栈时间复杂度为O(n)
  • 若使用头插法，则入栈复杂度为O(1)，出栈复杂度为O(1)
（3）用标注尾结点的单链表实现

  • 尾插法：入栈O(1)，出栈O(n)（因为删除尾结点依旧要遍历到前一个结点，改变其next值）
  • 头插法：入栈O(1)，出栈O(1)
（4）用双向链表实现

无论尾插还是头插时间复杂度都为O(1)

java"> LinkedList<Integer> stack=new LinkedList<>();stack.push(1);// addFirst(e);stack.push(2);stack.push(3);System.out.println(stack.peek());//拿到头结点3
2、栈的实际应用
（1）改变元素的序列
（2）将递归转化为循环（逆序打印链表）
java"> //1、递归方式void reverseprintList1(Node head){if(head!=null){printList(head.next);System.out.print(head.val + " ");}}
//2、循环方式void reverseprintList2(Node head){if(head==null){return;}Stack<Node> s = new Stack<>();// 将链表中的结点保存在栈中Node cur = head;while(cur!=null){s.push(cur);cur = cur.next;}// 将栈中的元素出栈while(!s.empty()){System.out.print(s.pop().val + " ");}}
（3）括号匹配

        给定一个只包含' ( '、' ) '、' { '、' } '、' [ '、' ] '的字符串s，判断括号是否匹配。匹配条件：左括号必须与相同类型的右括号闭合，不可交错排列

        匹配示例：(){}[]、({}[])、([{}])、()[{}]

java">public boolean isValid(String s) {Stack<Character> stack=new Stack<Character>();for (int i = 0; i < s.length(); i++) {char c=s.charAt(i);if (c=='(' || c=='[' || c=='{'){//c为左括号就添加进来等着对称匹配stack.push(c);}else {//c为右括号//此时栈中可能有左括号等着匹配，也可能为空（无法匹配）if (stack.empty()){return false;}//不为空，则栈中存放的是左括号，那就判断c与栈顶元素是否匹配（因为两括号必须要对称匹配）char top=stack.peek();if (c==')' && top=='(' || c==']' && top=='[' || c=='}' && top=='{'){//对称匹配了则弹出此左括号stack.pop();}else {//遇到一个右括号无法与栈顶左括号对称匹配，则无法匹配return false;}}}//如果s遍历完发现栈中不为空，即栈中仍有残存左括号未进行匹配，不匹配if (!stack.empty()){return false;}//否则匹配return true;}
（4）逆波兰表达式求值

中缀表达式转化为后缀表达式技巧：

java">public int evalRPN(String[] tokens) {Stack<Integer> stack=new Stack<>();for (String s : tokens) {if (!isOperation(s)) {//压入数字字符stack.push(Integer.parseInt(s));}else {//运算符则弹出栈顶2个元素进行操作（先弹出的放运算符右边）int num2=stack.pop();int num1=stack.pop();switch (s){case "+":stack.push(num1+num2);break;case "-":stack.push(num1-num2);break;case "*":stack.push(num1*num2);break;case "/":stack.push(num1/num2);break;}}}return stack.pop();}private boolean isOperation(String s) {if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){//是运算符return true;}return false;}
（5）出栈入栈次序匹配

java"> public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack=new Stack<>();int j=0;for (int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);while (!stack.empty() && j<popV.length && stack.peek()==popV[j]){stack.pop();j++;}}return stack.empty();}
（6）最小栈
java">class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack;//存储阶段性最小值private int minValue;public MinStack() {stack=new Stack<>();minStack=new Stack<>();}public void push(int val) {stack.push(val);if (minStack.empty()){minStack.push(val);}else {if (val<=minStack.peek()){minStack.push(val);}}}public void pop() {if (!stack.empty()){int ret=stack.pop();if (minStack.peek()==ret){minStack.pop();}}}public int top() {//获取stack栈顶元素if (stack.empty()){return -1;}return stack.peek();}public int getMin() {//获取minStack栈顶元素if (minStack.empty()){return -1;}return minStack.peek();}
}
  • 栈：一种数据结构。是一种特殊的线性表，只允许在栈顶进行插入和删除操作，栈顶的数据元素遵守后进先出的原则
  • 虚拟机栈：JVM内存管理的一部分，用于管理函数调用的内存和回收。属于线程私有，确保每个线程的内存隔离和安全。
  • 栈帧：函数调用过程中的内存管理单元。包含局部变量表、操作栈等信息。每个方法在运行时JVM都会创建一个栈帧，并将其压入虚拟机栈中；当方法调用结束时对应的栈帧会从虚拟机栈中出栈，确保函数调用的顺利进行和结束后的资源释放

二、队列

队列：只允许在一端进行插入和删除数据操作，在另一端进行删除数据操作的特殊线性表

  • 进行插入操作的一端称为队尾，进行删除操作的一端称为队头
  • 队列遵守先进先出的原则
1、队列的使用

在Java中，Queue是个接口，底层是通过链表实现的

方法
功能
boolean offer(E e)入队列
E poll()出队列
peek()获取队头元素
int size()获取队列中有效元素个数
boolean isEmpty()检测队列是否为空

Queue是个接口，在实例化时必须实例化LInkedList的对象，因为LinkedList实现了Queue接口

java">        Queue<Integer> q = new LinkedList<>();// 从队尾入队列q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5);System.out.println(q.size());//5System.out.println(q.peek()); // 获取队头元素 1q.poll();//弹出队头元素 1System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回 2if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());//3}
 2、队列的模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间。通过前面线性表的学习了解到常见的空间类型有2种：顺序结构和链式结构。那是用哪种结构实现比较好呢？

（1）双向链表实现

（2）数组实现

如果rear==elem.length-1之后发现数组前面还有位置还可以往前面插入元素就好了，这时候也就是我们的循环队列

3、循环队列

数组设计循环队列 

4、双端队列Deque

双端队列是指允许两端都可以进行入队和出队操作的队列

Deque是一个接口，使用时必须创建LinkedList对象

在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口

java">Deque<Integer>stack =newArrayDeque<>();//双端队列的线性实现
Deque<Integer>queue=newLinkedList<>();//双端队列的链式实现

 三、面试题

1、用栈实现队列

java">class MyQueue {Stack<Integer> inStack;Stack<Integer> outStack;public MyQueue() {inStack=new Stack<>();outStack=new Stack<>();}public void push(int x) {inStack.push(x);}public int pop() {if (empty()){return -1;//队列此时为空}if (outStack.empty()){while (!inStack.empty()){outStack.push(inStack.pop());}}return outStack.pop();}public int peek() {if (empty()){return -1;}if (outStack.empty()){while (!inStack.empty()){outStack.push(inStack.pop());}}return outStack.peek();}public boolean empty() {return inStack.empty() && outStack.empty();}
}
2、用队列实现栈

java">class MyStack {private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack() {qu1=new LinkedList<>();qu2=new LinkedList<>();}//入栈入到不为空的队列，都为空则入到qu1即可public void push(int x) {if (!qu1.isEmpty()){qu1.offer(x);}else if (!qu2.isEmpty()){qu2.offer(x);}else {qu1.offer(x);}}//出栈出不为空的队列size-1个。最后一个元素就是要出栈的元素public int pop() {if (empty()){return -1;//栈为空}if (!qu1.isEmpty()){int size=qu1.size();for (int i = 0; i < size - 1; i++) {qu2.offer(qu1.poll());}return qu1.poll();}else {int size=qu2.size();for (int i = 0; i < size - 1; i++) {qu1.offer(qu2.poll());}return qu2.poll();}}public int top() {int tmp=-1;if (empty()){return -1;//栈为空}if (!qu1.isEmpty()){int size=qu1.size();for (int i = 0; i < size; i++) {tmp=qu1.poll();qu2.offer(tmp);//出的最后一个元素存在tmp即为栈顶元素}return tmp;}else {int size=qu2.size();for (int i = 0; i < size; i++) {tmp=qu2.poll();qu1.offer(tmp);}return tmp;}}public boolean empty() {return qu2.isEmpty() && qu1.isEmpty();}
}

http://www.ppmy.cn/embedded/138772.html

相关文章

学习日记_20241110_聚类方法（K-Means）

学习日记_20241110_聚类方法（K-Means）

前言 提醒&#xff1a; 文章内容为方便作者自己后日复习与查阅而进行的书写与发布&#xff0c;其中引用内容都会使用链接表明出处&#xff08;如有侵权问题&#xff0c;请及时联系&#xff09;。 其中内容多为一次书写&#xff0c;缺少检查与订正&#xff0c;如有问题或其他拓展…
阅读更多...
R语言/Rstudio 报错

R语言/Rstudio 报错

记录R语言和Rstudio的报错&#xff1a; 1. Error 28 (inotify_add_watch: No watches available) File monitoring failed for project at "~xxx" Error 28 (inotify_add_watch: No watches available) Features disabled: R source file indexing, Diagnostics不少…
阅读更多...
力扣（leetcode）题目总结——辅助栈篇

力扣（leetcode）题目总结——辅助栈篇

leetcode 经典题分类 链表数组字符串哈希表二分法双指针滑动窗口递归/回溯动态规划二叉树辅助栈 本系列专栏&#xff1a;点击进入 leetcode题目分类 关注走一波 前言&#xff1a;本系列文章初衷是为了按类别整理出力扣&#xff08;leetcode&#xff09;最经典题目&#xff0c…
阅读更多...
【C++之STL】摸清 string 的模拟实现（上）

【C++之STL】摸清 string 的模拟实现（上）

文章目录 1. 为什么要模拟实现&#xff1f;2. 基本框架搭建3. 构造函数3. 1 默认构造/from c_str3. 2 拷贝构造3. 2. 1 深浅拷贝 3. 3 fill3. 4 迭代器区间构造 4. 容量操作4. 1 size()和capacity()和empty()4. 2 clear()4. 3 resize()4. 4 reserve() 1. 为什么要模拟实现&…
阅读更多...
【青牛科技】汽车收音机调频中频放大器——D1145

【青牛科技】汽车收音机调频中频放大器——D1145

性能优势 内置多种电路&#xff1a;内置芯片中频计数缓冲电路及 ETR 微处理控制开关电路&#xff0c;这些电路的集成有助于提升整体性能和功能的集成度&#xff0c;减少外部电路的复杂性和成本1.线性输出信号好&#xff1a;能够输出质量较高的线性信号&#xff0c;这对于保证收…
阅读更多...
Linux 中怎样把正在执行的任务放到后台执行

Linux 中怎样把正在执行的任务放到后台执行

在使用 Linux 的过程中&#xff0c;可能会遇到某些任务需要在后台运行的情况&#xff0c;例如长时间运行的脚本或占用终端的命令。将正在执行的任务放到后台&#xff0c;可以提高操作效率&#xff0c;不需要为每个任务单独开一个终端窗口。本文将介绍几种常用的方法来实现这一目…
阅读更多...
Android OpenGL ES详解——实例化

Android OpenGL ES详解——实例化

目录 一、实例化 1、背景 2、概念 实例化、实例数量 gl_InstanceID 应用举例 二、实例化数组 1、概念 2、应用举例 三、应用举例——小行星带 1、不使用实例化 2、使用实例化 四、总结 一、实例化 1、背景 假如你有一个有许多模型的场景&#xff0c;而这些模型的…
阅读更多...
Amazon Linux 搭建Zookeeper+Kafka集群

Amazon Linux 搭建Zookeeper+Kafka集群

Zookeeper集群搭建 Kafka集群是把状态保存在Zookeeper中的&#xff0c;首先要搭建Zookeeper集群。 Zookeeper 集群模式一共有三种类型的角色 Leader: 处理所有的事务请求&#xff08;写请求&#xff09;&#xff0c;可以处理读请求&#xff0c;集群中只能有一个Leader。 Follo…
阅读更多...
最新文章

Copyright @ 2022~2023