营销型网站的类型网页设计与制作网站教程

营销型网站的类型,网页设计与制作网站教程,物流erp管理系统,仿简书WordPress一文彻底搞懂「栈和队列」——从零基础到面试常考#xff08;含详细 Java 代码#xff09;适合人群#xff1a;零基础 / 小白#xff0c;刚接触数据结构与 Java 学完收获#xff1a;能听懂概念、写出代码、看懂面试题#xff0c;对“栈”和“队列”形成一套完整的知识体系…一文彻底搞懂「栈和队列」——从零基础到面试常考含详细 Java 代码适合人群零基础 / 小白刚接触数据结构与 Java学完收获能听懂概念、写出代码、看懂面试题对“栈”和“队列”形成一套完整的知识体系。目录速览一、为什么要学栈和队列二、栈Stack——像“盘子堆”一样的结构栈的生活类比栈的基本概念和术语栈的常见操作三、用 Java 实现一个“顺序栈”基于数组四、用 Java 的标准库来使用栈五、队列Queue——像“排队买票”一样的结构队列的生活类比队列的基本概念和术语队列的常见操作六、用数组实现一个“顺序队列”简单版七、进阶循环队列解决空间浪费问题八、用 Java 标准库来使用队列九、栈和队列的典型应用场景十、常见面试题附思路代码十一、栈 vs 队列一张表帮你对比记忆十二、给初学者的一些小建议快速记忆小口诀栈一头进出后进先出像盘子堆队列一头进一头出先进先出像排队一、为什么要学栈和队列栈Stack和队列Queue是最基础的两种数据结构很多高级数据结构和算法都是在它们之上构建的各大公司面试中这两个是反复考、常考、必考的知识点先记住一句话栈后进先出LIFO, Last In First Out队列先进先出FIFO, First In First Out我们先从生活中的例子理解再看 Java 代码。二、栈Stack——像“盘子堆”一样的结构1. 栈的生活类比想象一下食堂洗好的一摞盘子盘子示意图上面是栈顶 ┌───────┐ ← 栈顶 Top │ 盘子3 │ 后放进去先拿出来 ├───────┤ │ 盘子2 │ ├───────┤ │ 盘子1 │ 最先放进去最后才拿出来 └───────┘ ← 栈底 Bottom新盘子只能放在最上面压在上一个盘子上要拿盘子时也只能从最上面拿所以最后放上去的盘子最先被拿走—— 这就是后进先出LIFO2. 栈的基本概念和术语压栈push向栈顶放入一个元素弹栈pop从栈顶取出一个元素栈顶top当前可以操作的“最上面”的那个元素栈底bottom最早被压入、在最下面的元素空栈栈中没有任何元素3. 栈的常见操作一般包含以下几个方法用伪代码描述push(x)把元素x压入栈顶pop()弹出栈顶元素并返回peek() / top()只看一眼栈顶元素但不删除isEmpty()栈是否为空size()栈中有多少个元素三、用 Java 实现一个“顺序栈”基于数组我们先不用现成的java.util.Stack自己实现一个栈这样理解更深刻。1. 核心设计思路用一个数组data[]来存元素用一个整型变量top来记录“当前栈顶的位置”约定当栈为空时top -1当有元素时栈顶元素在data[top]每次push先top然后赋值data[top] x每次pop取出data[top]然后top--2. 代码基于数组实现的栈含详细注释/** * 一个简单的顺序栈实现基于数组 * 为了方便理解我们只存 int 类型 */publicclassArrayStack{// 用数组存储栈中的元素privateint[]data;// top 代表“栈顶”下标-1 代表空栈privateinttop;// 构造方法指定栈的容量publicArrayStack(intcapacity){datanewint[capacity];// 初始化数组top-1;// 一开始是空栈}/** * 入栈压栈操作 * param value 要压入栈顶的元素 * return 是否压入成功 */publicbooleanpush(intvalue){// 栈满的判断top 已经到了数组最后一个下标if(topdata.length-1){System.out.println(栈满了无法再压栈);returnfalse;}// 先移动 top再赋值top;data[top]value;returntrue;}/** * 出栈弹栈操作 * return 栈顶元素如果为空则抛出异常或返回一个特殊值 */publicintpop(){if(isEmpty()){thrownewRuntimeException(栈为空无法弹栈);}// 先取值再移动 topintvaluedata[top];top--;returnvalue;}/** * 查看栈顶元素但不删除 */publicintpeek(){if(isEmpty()){thrownewRuntimeException(栈为空没有栈顶元素);}returndata[top];}/** * 栈是否为空 */publicbooleanisEmpty(){returntop-1;}/** * 当前栈中元素个数 */publicintsize(){returntop1;}/** * 打印当前栈中元素从栈底到栈顶 */publicvoidprintStack(){if(isEmpty()){System.out.println(栈是空的);return;}System.out.print(栈中元素从栈底到栈顶);for(inti0;itop;i){System.out.print(data[i] );}System.out.println();}// 简单测试一下publicstaticvoidmain(String[]args){ArrayStackstacknewArrayStack(5);stack.push(10);stack.push(20);stack.push(30);stack.printStack();// 10 20 30System.out.println(当前栈顶元素stack.peek());// 30intpoppedstack.pop();System.out.println(弹出了元素popped);// 30stack.printStack();// 10 20System.out.println(当前栈大小stack.size());// 2}}四、用 Java 的标准库来使用栈在真实开发中我们通常不会自己写栈而是用 JDK 提供的容器。1. 方式一java.util.Stackimportjava.util.Stack;publicclassStackDemo{publicstaticvoidmain(String[]args){// 创建一个栈元素类型为 IntegerStackIntegerstacknewStack();// 压栈stack.push(1);stack.push(2);stack.push(3);System.out.println(栈顶元素stack.peek());// 3// 弹栈System.out.println(弹出stack.pop());// 3System.out.println(弹出stack.pop());// 2// 判断是否为空System.out.println(栈是否为空stack.isEmpty());// false}}2. 方式二面试常问用Deque代替StackJava 官方文档更推荐使用Deque双端队列来实现栈因为Stack是比较老的类基于Vector有一些性能/设计上的历史包袱。importjava.util.ArrayDeque;importjava.util.Deque;publicclassDequeAsStackDemo{publicstaticvoidmain(String[]args){// 用 Deque 来模拟栈DequeIntegerstacknewArrayDeque();// 压栈使用 pushstack.push(10);stack.push(20);stack.push(30);// 查看栈顶元素System.out.println(栈顶元素stack.peek());// 30// 弹栈System.out.println(弹出stack.pop());// 30System.out.println(弹出stack.pop());// 20System.out.println(是否为空stack.isEmpty());// false}}面试小知识问Java 中实现栈用什么答可以用Stack但更推荐使用Deque的实现类比如ArrayDeque来实现栈结构。五、队列Queue——像“排队买票”一样的结构1. 队列的生活类比最经典的例子排队买奶茶。最先排队的人最先买到奶茶然后离开队伍新来的人排到队伍的末尾所以队列的规则是先来先服务先进先出FIFO, First In First Out2. 队列的基本概念和术语入队enqueue / offer从队尾插入一个元素出队dequeue / poll从队头取出一个元素队头front / head下一个要被取出的那个元素队尾rear / tail最后进入队列的那个元素空队列没有任何元素3. 队列的常见操作队列方向示意图 入队方向 → [ 队头 ... 队列中间 ... 队尾 ] → 出队方向 front rearoffer(x) / add(x)入队poll() / remove()出队peek() / element()只看一下队头元素不删除isEmpty()是否为空size()当前元素个数六、用数组实现一个“顺序队列”最简单版本为了更容易理解我们先写一个最简单的数组队列版本暂时不考虑“循环利用空间”的问题。1. 核心思路用一个数组data[]存元素用两个指针下标front指向队头元素的位置rear指向队尾后面一个位置也可以理解为“下一个可以插入的位置”简单版本约定初始时front 0,rear 0队列为空每次入队把元素放在data[rear]然后rear每次出队返回data[front]然后front当front rear队列为空缺点当rear走到数组末尾时即使前面有空间也不能再插入浪费空间。不过没关系这个版本先帮你理解基本原理后面我们再改进成循环队列。2. 代码简单数组队列实现/** * 一个简单的顺序队列基于数组不循环利用空间 */publicclassSimpleArrayQueue{privateint[]data;privateintfront;// 指向队头元素privateintrear;// 指向队尾后面一个位置下一次入队的位置publicSimpleArrayQueue(intcapacity){datanewint[capacity];front0;rear0;}/** * 入队 */publicbooleanoffer(intvalue){if(reardata.length){System.out.println(队列已满简单实现不可再入队);returnfalse;}data[rear]value;rear;returntrue;}/** * 出队 */publicintpoll(){if(isEmpty()){thrownewRuntimeException(队列为空无法出队);}intvaluedata[front];front;returnvalue;}/** * 查看队头元素 */publicintpeek(){if(isEmpty()){thrownewRuntimeException(队列为空没有队头元素);}returndata[front];}/** * 是否为空 */publicbooleanisEmpty(){returnfrontrear;}/** * 当前元素个数 */publicintsize(){returnrear-front;}publicvoidprintQueue(){if(isEmpty()){System.out.println(队列为空);return;}System.out.print(队列中的元素从队头到队尾);for(intifront;irear;i){System.out.print(data[i] );}System.out.println();}publicstaticvoidmain(String[]args){SimpleArrayQueuequeuenewSimpleArrayQueue(5);queue.offer(1);queue.offer(2);queue.offer(3);queue.printQueue();// 1 2 3System.out.println(队头元素queue.peek());// 1System.out.println(出队queue.poll());// 1queue.printQueue();// 2 3}}七、进阶循环队列解决空间浪费问题刚刚的简单队列有一个问题前面空出来的位置用不了。解决办法把数组当成一个“环”来使用这就是循环队列circular queue。1. 循环队列的思想模运算我们依然用front和rear两个指针只是每次移动时都让下标绕圈入队时rear (rear 1) % capacity出队时front (front 1) % capacity为了区分“队满”和“队空”常用办法是保留一个空位约定当(rear 1) % capacity front时队列“满”当front rear时队列“空”2. 代码循环队列实现/** * 循环队列实现基于数组保留一个空位来区分满和空 */publicclassCircularQueue{privateint[]data;privateintfront;// 队头下标privateintrear;// 队尾后一个位置publicCircularQueue(intcapacity){// 注意实际可用的元素个数是 capacity - 1因为要空出一个datanewint[capacity];front0;rear0;}/** * 队列是否为空 */publicbooleanisEmpty(){returnfrontrear;}/** * 队列是否已满 * 条件再往前走一步就撞上 front 了 */publicbooleanisFull(){return(rear1)%data.lengthfront;}/** * 入队操作 */publicbooleanoffer(intvalue){if(isFull()){System.out.println(循环队列已满无法入队);returnfalse;}data[rear]value;rear(rear1)%data.length;// 让 rear 向前走一步绕圈returntrue;}/** * 出队操作 */publicintpoll(){if(isEmpty()){thrownewRuntimeException(循环队列为空无法出队);}intvaluedata[front];front(front1)%data.length;// front 向前走一步returnvalue;}/** * 查看队头元素 */publicintpeek(){if(isEmpty()){thrownewRuntimeException(循环队列为空);}returndata[front];}/** * 当前元素个数 */publicintsize(){// 环形队列的长度计算公式return(rear-frontdata.length)%data.length;}publicvoidprintQueue(){if(isEmpty()){System.out.println(队列为空);return;}System.out.print(队列中的元素从队头到队尾);intifront;while(i!rear){System.out.print(data[i] );i(i1)%data.length;}System.out.println();}publicstaticvoidmain(String[]args){// 注意数组长度为 5最多只能存 4 个元素CircularQueuequeuenewCircularQueue(5);queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.printQueue();// 1 2 3 4System.out.println(队列是否已满queue.isFull());// trueSystem.out.println(出队queue.poll());// 1System.out.println(出队queue.poll());// 2queue.printQueue();// 3 4queue.offer(5);queue.offer(6);queue.printQueue();// 3 4 5 6 通过“绕圈”复用了空间}}八、用 Java 标准库来使用队列Java 中常用的队列接口是java.util.Queue最常见的实现类有LinkedList基于链表的队列ArrayDeque基于数组的双端队列既可以当队列也可以当栈1. 使用LinkedList实现队列importjava.util.LinkedList;importjava.util.Queue;publicclassLinkedListQueueDemo{publicstaticvoidmain(String[]args){// 使用 LinkedList 来实现 Queue 接口QueueIntegerqueuenewLinkedList();// 入队queue.offer(10);// 推荐使用 offer队满时返回 false 不会抛异常queue.offer(20);queue.offer(30);System.out.println(队头元素queue.peek());// 10// 出队System.out.println(出队queue.poll());// 10System.out.println(出队queue.poll());// 20System.out.println(队列是否为空queue.isEmpty());// false}}2. 使用ArrayDeque作为队列importjava.util.ArrayDeque;importjava.util.Queue;publicclassArrayDequeQueueDemo{publicstaticvoidmain(String[]args){QueueIntegerqueuenewArrayDeque();queue.offer(1);queue.offer(2);queue.offer(3);System.out.println(队头queue.peek());// 1System.out.println(出队queue.poll());// 1System.out.println(出队queue.poll());// 2}}小提示offer()/poll()/peek()推荐在队列中使用更安全不容易抛异常add()/remove()/element()在特殊情况下队满、队空会抛出异常九、栈和队列在实际中的典型应用帮助你更好理解1. 栈的典型应用函数调用栈每调用一个方法就压入栈方法执行完就从栈中弹出这就是为什么有“栈溢出StackOverflowError”撤销Undo功能比如文本编辑器的“撤销”每次操作压栈撤销时从栈顶取出上一步操作括号匹配面试高频如判断({[]})是否是合法括号序列表达式求值中缀表达式转后缀表达式计算后缀表达式等2. 队列的典型应用操作系统的任务调度等待执行的任务通常排队处理消息队列MQKafka、RabbitMQ 等系统本质上都在实现队列结构广度优先搜索BFS图/树的层序遍历用队列来实现排队业务场景银行排号、打印任务排队、网络请求处理等十、常见面试题附详解答案下面整理一些关于栈和队列的常见面试题适合初级同学。面试题 1用栈实现队列题目大意请用两个栈实现一个队列要求实现队列的两个基本操作入队push和出队pop。1. 思路讲解队列是先进先出栈是后进先出。用两个栈倒来倒去可以“反转顺序”从而模拟队列准备两个栈stackIn和stackOut入队时永远往stackIn里压栈出队时如果stackOut不为空直接从stackOut弹栈如果stackOut为空把stackIn中的所有元素依次弹出压入stackOut然后再从stackOut弹出元素这样进入顺序1, 2, 3入stackIn第一次出队时把stackIn中的1, 2, 3依次弹出压入stackOut顺序变成3, 2, 1然后从stackOut弹出栈顶1—— 就实现了“先来的先出队”2. 代码实现Javaimportjava.util.Stack;/** * 用两个栈实现一个队列 */publicclassMyQueueByTwoStacks{privateStackIntegerstackIn;// 负责入队privateStackIntegerstackOut;// 负责出队publicMyQueueByTwoStacks(){stackInnewStack();stackOutnewStack();}/** * 入队操作 */publicvoidoffer(intvalue){stackIn.push(value);}/** * 出队操作 */publicintpoll(){if(isEmpty()){thrownewRuntimeException(队列为空无法出队);}// 如果 stackOut 为空就把 stackIn 的元素全部倒过去if(stackOut.isEmpty()){while(!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}returnstackOut.pop();}/** * 查看队头元素 */publicintpeek(){if(isEmpty()){thrownewRuntimeException(队列为空);}if(stackOut.isEmpty()){while(!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}returnstackOut.peek();}/** * 队列是否为空 */publicbooleanisEmpty(){returnstackIn.isEmpty()stackOut.isEmpty();}publicstaticvoidmain(String[]args){MyQueueByTwoStacksqueuenewMyQueueByTwoStacks();queue.offer(1);queue.offer(2);queue.offer(3);System.out.println(queue.poll());// 1System.out.println(queue.poll());// 2queue.offer(4);System.out.println(queue.poll());// 3System.out.println(queue.poll());// 4}}复杂度分析入队offer平均时间复杂度为 (O(1))出队poll平均时间复杂度为 (O(1))虽然有时会一次性搬很多元素但摊还下来仍是常数级面试题 2用队列实现栈题目大意只使用队列的基本操作入队、出队等实现一个栈的功能push、pop、top。1. 核心思路栈是后进先出我们用一个队列来模拟方法一每次push时保证新元素最后出队常用做法push(x)先把x入队然后把队列中前面的所有元素依次出队再入队这样新来的x会被“旋转”到队头之后pop时总是先出x2. 代码实现Javaimportjava.util.LinkedList;importjava.util.Queue;/** * 用一个队列实现栈 */publicclassMyStackByQueue{privateQueueIntegerqueue;publicMyStackByQueue(){queuenewLinkedList();}/** * 压栈操作 */publicvoidpush(intx){// 1. 先把新元素入队queue.offer(x);// 2. 再把之前的元素“旋转”到新元素后面intsizequeue.size();// 除了刚入队的 x 之外其它 size-1 个元素依次出队再入队for(inti0;isize-1;i){intvaluequeue.poll();queue.offer(value);}}/** * 弹栈操作 */publicintpop(){if(isEmpty()){thrownewRuntimeException(栈为空无法弹栈);}// 因为我们在 push 的时候保证了“栈顶”总在队头returnqueue.poll();}/** * 查看栈顶元素 */publicinttop(){if(isEmpty()){thrownewRuntimeException(栈为空);}returnqueue.peek();}/** * 栈是否为空 */publicbooleanisEmpty(){returnqueue.isEmpty();}publicstaticvoidmain(String[]args){MyStackByQueuestacknewMyStackByQueue();stack.push(1);stack.push(2);stack.push(3);System.out.println(stack.top());// 3System.out.println(stack.pop());// 3System.out.println(stack.pop());// 2System.out.println(stack.pop());// 1}}复杂度分析push时间复杂度 (O(n))每次要旋转前面的元素pop、top时间复杂度 (O(1))面试题 3用栈判断括号是否合法经典高频题题目描述给定一个只包含()、[]、{}的字符串判断括号是否成对、顺序是否正确。例如()[]合法(]不合法([)]不合法{[]}合法1. 思路讲解遍历字符串遇到左括号入栈遇到右括号如果栈为空不合法否则弹出栈顶看是否是对应的左括号最后栈必须为空才算完全匹配2. 代码实现Javaimportjava.util.Stack;publicclassValidParentheses{publicstaticbooleanisValid(Strings){StackCharacterstacknewStack();for(charc:s.toCharArray()){// 如果是左括号就入栈if(c(||c[||c{){stack.push(c);}else{// 如果遇到右括号if(stack.isEmpty()){returnfalse;// 没有左括号与之匹配}chartopstack.pop();// 判断是否匹配if(c)top!()returnfalse;if(c]top![)returnfalse;if(c}top!{)returnfalse;}}// 最后栈必须为空returnstack.isEmpty();}publicstaticvoidmain(String[]args){System.out.println(isValid(()[]{}));// trueSystem.out.println(isValid(([)]));// falseSystem.out.println(isValid({[]}));// true}}这道题几乎是“栈”的最经典应用题力扣LeetCode上非常高频建议熟练掌握。十一、栈 vs 队列一张表帮你对比记忆对比项栈Stack队列Queue核心规则后进先出 LIFO先进先出 FIFO形象类比一摞盘子只能从上面拿排队买票先到先走主要操作push / pop / peekoffer / poll / peekJava 常用实现Stack、DequeQueueLinkedList/ArrayDeque典型应用函数调用栈、撤销、括号匹配任务调度、BFS、消息队列十二、给初学者的一些小建议多画图、多类比画出数组 指针top / front / rear的变化印象更深手动模拟一遍操作拿纸和笔模拟入栈、出栈入队、出队亲手敲一遍文中的代码不要只复制粘贴自己打字可以加深记忆尝试自己扩展把int改成泛型T让栈 / 队列可以存任意类型给栈 / 队列加一个clear()方法