上一篇讲了线性表顺序表和链表这一篇讲线性表的两种特殊形式——栈Stack和队列Queue。它们在 408 考研和面试中出现频率极高。一、栈——后进先出1. 什么是栈栈Stack是限定只能在一端进行插入和删除操作的线性表。允许操作的一端 → 栈顶Top 不允许操作的一端 → 栈底Bottom 插入 → 入栈Push 删除 → 出栈Pop ← 出栈 ┌───┐ │ 5 │ ← 栈顶 ├───┤ │ 4 │ ├───┤ │ 3 │ ├───┤ │ 2 │ ├───┤ │ 1 │ ← 栈底 └───┘ push(6) → 放到栈顶特点后进先出LIFO, Last In First Out生活中的例子一叠盘子——你只能从上面拿后放上去的先用浏览器的后退——最后访问的页面最先回退函数调用——最里层的函数最先返回2. 顺序栈数组实现publicclassArrayStackE{privatestaticfinalintDEFAULT_CAPACITY10;privateE[]data;privateinttop;// 栈顶指针指向当前栈顶元素位置publicArrayStack(){data(E[])newObject[DEFAULT_CAPACITY];top-1;// 初始为空栈}// 入栈publicvoidpush(Eelement){if(topdata.length-1){grow();// 扩容}data[top]element;}// 出栈publicEpop(){if(isEmpty())thrownewEmptyStackException();Eelementdata[top];data[top--]null;// 清空引用帮助 GCreturnelement;}// 查看栈顶不删除publicEpeek(){if(isEmpty())thrownewEmptyStackException();returndata[top];}publicbooleanisEmpty(){returntop-1;}publicintsize(){returntop1;}}时间复杂度push/pop/peek 都是O(1)。3. 链栈链表实现publicclassLinkedStackE{privateNodeEtop;// 栈顶链表头privateintsize;privatestaticclassNodeE{Edata;NodeEnext;Node(Edata){this.datadata;}}publicvoidpush(Eelement){NodeEnewNodenewNode(element);newNode.nexttop;// 新节点指向旧栈顶topnewNode;// 新节点成为栈顶size;}publicEpop(){if(isEmpty())thrownewEmptyStackException();Edatatop.data;toptop.next;// 栈顶下移size--;returndata;}publicEpeek(){if(isEmpty())thrownewEmptyStackException();returntop.data;}publicbooleanisEmpty(){returntopnull;}}注意链栈的 push/pop 都是在链表头部操作不需要遍历时间复杂度O(1)。二、队列——先进先出1. 什么是队列队列Queue是限定在一端插入、另一端删除的线性表。插入队尾→ ┌───┬───┬───┬───┬───┐ → 删除队头 │ 1 │ 2 │ 3 │ 4 │ 5 │ └───┴───┴───┴───┴───┘ front ↑ ↑ rear特点先进先出FIFO, First In First Out生活中的例子排队买奶茶——先来的先买到打印机任务队列——先提交的先打印消息队列——生产者发送消费者按顺序处理2. 顺序队列的问题// 直接使用数组实现队列的问题// 出队时 front 后移导致数组前面的空间被浪费初始 front0,rear0[][][][][]A入队[A][][][][]B入队[A][B][][][]A出队 front1[][B][][][]← 下标0的空间浪费了解决方案循环队列3. 循环队列┌──────────────────────┐ │ rear │ │ ↓ │ │ ┌──┬──┬──┬──┬──┐ │ │ │ │ │E │F │G │ │ │ ├──┼──┼──┼──┼──┤ │ │ │D │ │ │ │ │ │ │ └──┴──┴──┴──┴──┘ │ │ ↑ │ │ front │ └──────────────────────┘publicclassCircularQueueE{privateE[]data;privateintfront;// 队头指针privateintrear;// 队尾指针指向下一个插入位置privateintsize;privateintcapacity;publicCircularQueue(intcapacity){this.capacitycapacity;data(E[])newObject[capacity];front0;rear0;size0;}// 入队publicbooleanenqueue(Eelement){if(isFull())returnfalse;data[rear]element;rear(rear1)%capacity;// 循环size;returntrue;}// 出队publicEdequeue(){if(isEmpty())returnnull;Eelementdata[front];data[front]null;front(front1)%capacity;// 循环size--;returnelement;}publicbooleanisEmpty(){returnsize0;}publicbooleanisFull(){returnsizecapacity;}}关键rear (rear 1) % capacity实现循环——到达数组末尾后回到开头。4. 链式队列publicclassLinkedQueueE{privateNodeEfront;// 队头出队privateNodeErear;// 队尾入队privateintsize;publicvoidenqueue(Eelement){NodeEnewNodenewNode(element);if(isEmpty()){frontrearnewNode;}else{rear.nextnewNode;rearnewNode;}size;}publicEdequeue(){if(isEmpty())returnnull;Edatafront.data;frontfront.next;if(frontnull)rearnull;// 队列变空size--;returndata;}}三、栈和队列的对比对比栈队列规则后进先出LIFO先进先出FIFO插入/删除位置同一端栈顶两端队尾/队头常用实现数组顺序栈循环数组循环队列适用场景递归转非递归、括号匹配排队系统、BFS、消息队列四、408 考研经典考题题1括号匹配publicbooleanisValid(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();// 所有左括号都匹配完}题2用两个栈实现队列classMyQueue{privateStackIntegerinStack;// 入队栈privateStackIntegeroutStack;// 出队栈publicMyQueue(){inStacknewStack();outStacknewStack();}publicvoidpush(intx){inStack.push(x);// 直接压入入队栈}publicintpop(){if(outStack.isEmpty()){// 把入队栈的元素全部倒入出队栈while(!inStack.isEmpty()){outStack.push(inStack.pop());}}returnoutStack.pop();}}原理入队时放入 inStack出队时从 outStack 取。outStack 空了就把 inStack 全部倒过来——倒一次后元素的顺序就变成了队列顺序。题3循环队列判空判满两种判断方式 方法1size 字段推荐简单明了 isEmpty() → size 0 isFull() → size capacity 方法2牺牲一个存储单元 空 → rear front 满 → (rear 1) % capacity front题4用队列实现栈了解即可classMyStack{privateQueueIntegerqueue;publicvoidpush(intx){queue.offer(x);// 把前面的元素移到后面让新元素在队头for(inti0;iqueue.size()-1;i){queue.offer(queue.poll());}}publicintpop(){returnqueue.poll();}}五、实际开发中的应用栈的应用 JVM 虚拟机栈 → 方法调用和返回 表达式求值 → 中缀转后缀 撤销操作 → CtrlZ 队列的应用 线程池任务队列 → 等待执行的任务 消息队列 MQ → 异步解耦 树的层序遍历 → BFS六、Java 中的栈和队列// 栈Java 官方推荐用 Deque 代替 StackDequeStringstacknewArrayDeque();stack.push(A);// 入栈stack.pop();// 出栈stack.peek();// 查看栈顶// 队列QueueStringqueuenewLinkedList();queue.offer(A);// 入队queue.poll();// 出队queue.peek();// 查看队头// 双端队列两端都可操作DequeStringdequenewArrayDeque();deque.addFirst(A);deque.addLast(B);deque.removeFirst();deque.removeLast();总结栈和队列其实就是限制了操作位置的线性表。栈只在一端操作LIFO队列在两端操作FIFO。代码实现时注意循环队列的取模运算和判空判满条件。 觉得有用的话点赞 关注【张老师技术栈】吧每周更新 Java/Python/爬虫 实战干货不让你白来。