【算法 | 第3章 栈与队列相关《程序员面试金典》#yyds干货盘点#】观书散遗帙，探古穷至妙。这篇文章主要讲述算法 | 第3章 栈与队列相关《程序员面试金典》#yyds干货盘点#相关的知识，希望能为你提供帮助。
@[TOC](第3章 栈与队列相关《程序员面试金典》)
前言本系列笔记主要记录笔者刷《程序员面试金典》算法的一些想法与经验总结，按专题分类，主要由两部分构成：经验值点和经典题目。其中重点放在经典题目上；
0. *经验总结 0.1 程序员面试金典 P82

• 栈 - 后进先出（LIFO）：
  • 栈无法在常数时间复杂度内访问第i个元素。但因为栈不需要在添加和删除时移动元素，可以在常数时间复杂度内完成此操作；
  • 对于递归算法：有时需要把临时变量加入到栈中，在回溯时删除；
• 队列 - 先进先出（FIFO）：
  
  • 更新队列第一个和最后一个节点容易出错，要再三确认；
  • 队列常用于广度优先搜索或缓存的实现；
  • 例如，在广度优先搜索中，可以使用队列来存储需要被处理的节点。每处理一个结点，就把其相邻节点加入队列尾部。这样可以按照发现顺序处理节点；
• 需要注意的共同点：
  
  • 要理清下标的栈大小的区别；
  • 涉及栈和队列的题目往往需要编写好几个方法，要理清楚前后逻辑； 0.2 java常用数据结构API详细见以下文章：
    Java | 个人总结的Java常用API手册汇总
    

0.3 关于延迟移动

• 有些时候我们需要访问栈底或者队列底的数据，往往需要对数据次序进行反转操作；
• 我们可以每次都进行两次反转，因为要保证回到原来的样子，这样会产生大量重复操作；
• 另一种做法是我们先对栈或队列进行反转，需要访问栈顶或队列顶元素时才翻转回来；
• 第二种方法需要注意翻转的时机；
• 下面《4. 化栈为队》和《5. 栈排序》都用到类似的思想；

1. 三合一 [easy]
文章图片

1.1 考虑点

• 注意看提示0& lt; =stackNum& lt; =2，说明三个栈在数组中排列是123123123；
• 可以试着跟面试官谈谈扩展问题，如：
  • 当运行栈块空间大小灵活可变时，要进行弹性分割，该怎么实现；
  • 可以将数组设计成环形，最后一个栈可能从数组尾处开始，环绕到数组起始处；
  • 方法实现起来比较复杂，可以试着提供伪代码或其中部分代码；

1.2 解法 1.2.1 三指针法

class TripleInOne int[] stack; int stackSize; int t0; int t1; int t2; public TripleInOne(int stackSize) stack = new int[stackSize*3]; int t0 = -3; int t1 = -2; int t2 = -1; this.stackSize = stackSize; this.t0 = t0; this.t1 = t1; this.t2 = t2; public void push(int stackNum, int value) if( stackNum == 0 ) this.t0 = pushVal( t0, value ); else if( stackNum == 1 ) this.t1 = pushVal( t1, value); else if( stackNum == 2) this.t2 = pushVal( t2, value); public int pushVal( int top, int value ) if( top + 3 < stackSize*3 ) top += 3; stack[top] = value; return top; public int pop(int stackNum) int val = peek(stackNum); if( val != -1 ) if( stackNum == 0 ) stack[t0] = -1; t0 -= 3; else if( stackNum == 1 ) stack[t1] = -1; t1 -= 3; else if( stackNum == 2) stack[t2] = -1; t2 -= 3; return val; return -1; public int peek(int stackNum) if( stackNum == 0 & & t0 > = 0 ) return stack[t0]; else if( stackNum == 1 & & t1 > = 1) return stack[t1]; else if( stackNum == 2 & & t2 > = 2) return stack[t2]; return -1; public boolean isEmpty(int stackNum) int value = https://www.songbingjia.com/android/peek(stackNum); if( value == -1) return true; return false;

• 执行时间：34.80%；内存消耗：44.07%；
• 定义三个指针，分别指向三个队列在数组的索引；

1.2.2 二维数组法（优）

class TripleInOne int N = 3; // 3 * n 的数组，每一行代表一个栈 int[][] data; // 记录每个栈「待插入」位置 int[] locations; public TripleInOne(int stackSize) data = https://www.songbingjia.com/android/new int[N][stackSize]; locations = new int[N]; public void push(int stackNum, int value) int[] stk = data[stackNum]; int loc = locations[stackNum]; if (loc < stk.length) stk[loc] = value; locations[stackNum]++; public int pop(int stackNum) int[] stk = data[stackNum]; int loc = locations[stackNum]; if (loc > 0) int val = stk[loc - 1]; locations[stackNum]--; return val; else return -1; public int peek(int stackNum) int[] stk = data[stackNum]; int loc = locations[stackNum]; if (loc > 0) return stk[loc - 1]; else return -1; public boolean isEmpty(int stackNum) return locations[stackNum] == 0;

• 执行时间：97.06%；内存消耗：69.49%；
• 时间复杂度：所有的操作均为 O(1)。
• 空间复杂度：O(k*n)。k 为我们需要实现的栈的个数，n 为栈的容量；
• 建立一个二维数组 datadata ；二维数组的每一行代表一个栈，同时使用一个locationslocations 记录每个栈「待插入」的下标；

1.2.3 一维数组法

class TripleInOne int N = 3; int[] data; int[] locations; int size; public TripleInOne(int stackSize) size = stackSize; data = https://www.songbingjia.com/android/new int[size * N]; locations = new int[N]; for (int i = 0; i < N; i++) locations[i] = i * size; public void push(int stackNum, int value) int idx = locations[stackNum]; if (idx < (stackNum + 1) * size) data[idx] = value; locations[stackNum]++; public int pop(int stackNum) int idx = locations[stackNum]; if (idx > stackNum * size) locations[stackNum]--; return data[idx - 1]; else return -1; public int peek(int stackNum) int idx = locations[stackNum]; if (idx > stackNum * size) return data[idx - 1]; else return -1; public boolean isEmpty(int stackNum) return locations[stackNum] == stackNum * size;

• 执行时间：97.06%；内存消耗：44.07%；

2. 栈的最小值 [easy]
文章图片

2.1 考虑点

• 把加入一个元素看成一种状态，每种状态都有对应最小值，这样得到解法2；

2.2 解法 2.2.1 循环遍历法

class MinStack Stack< Integer> stack; Stack< Integer> minStack; /** initialize your data structure here. */ public MinStack() Stack< Integer> stack = new Stack< > (); Stack< Integer> minStack = new Stack< > (); this.stack = stack; this.minStack = minStack; public void push(int x) stack.add(x); if( minStack.isEmpty() ) minStack.add(x); return; Stack< Integer> cache = new Stack< > (); boolean isMatter = false; while( !isMatter ) if( !minStack.isEmpty() & & minStack.peek() < x ) cache.add( minStack.pop() ); else minStack.add(x); isMatter = true; while( !cache.isEmpty() ) minStack.add(cache.pop()); public void pop() if( stack.isEmpty() ) return; int topNum = stack.pop(); Stack< Integer> cache = new Stack< > (); boolean isMatter = false; while( !isMatter ) if( minStack.peek() == topNum ) minStack.pop(); isMatter = true; else cache.add(minStack.pop()); while( !cache.isEmpty() ) minStack.add(cache.pop()); public int top() return stack.peek(); public int getMin() return minStack.peek();

• 执行时间：5.02%；内存消耗：5.18%；
• 不推荐用此方法，不满足O(1)的时间复杂度；

2.2.2 主辅栈法（优）

文章图片

class MinStack Deque< Integer> xStack; Deque< Integer> minStack; public MinStack() xStack = new LinkedList< Integer> (); minStack = new LinkedList< Integer> (); minStack.push(Integer.MAX_VALUE); public void push(int x) xStack.push(x); minStack.push(Math.min(minStack.peek(), x)); public void pop() xStack.pop(); minStack.pop(); public int top() return xStack.peek(); public int getMin() return minStack.peek();

• 执行时间：91.63%；内存消耗：58.64%；
• 创建两个栈，一个栈是主栈 stackstack，另一个是辅助栈 minStackminStack，用于存放对应主栈不同时期的最小值；

3. 堆盘子 [medium]
文章图片

• push是往最后一个栈中放数据，而不是从前遍历找到空位；

3.1 考虑点

• 注意讨论当传入cap=0时的情况；
• 可以跟面试官讨论push的两种情况：
  • 第一种是：往最后一个栈中放数据（下诉解法）；
  • 第二种是：从前遍历找到空位（需要推出栈n+1的栈底元素到栈n，循环往复到最后一个栈）；
  • 前者优点是能很大程度上改善时间复杂度，后者适用一些要求所有栈（除最后一个）都填满的场景；

3.2 解法 3.2.1 单链表寻栈法

class StackOfPlates int cap; List< Stack< Integer> > list; public StackOfPlates(int cap) List< Stack< Integer> > list = new ArrayList< > (); this.cap = cap; this.list = list; public void push(int val) if( cap == 0 ) return; Stack< Integer> stack; if( list.isEmpty() ) stack = new Stack< Integer> (); list.add(stack); else stack = list.get(list.size() - 1); if( stack.size() > = cap ) stack = new Stack< Integer> (); list.add(stack); if( stack.size() < cap ) stack.add(val); public int pop() if( cap == 0 ) return -1; if( list.isEmpty() ) return -1; Stack< Integer> stack = list.get(list.size() - 1); int result = stack.pop(); if(stack.isEmpty()) list.remove( list.size() - 1 ); return result; public int popAt(int index) if( cap == 0 ) return -1; if( index > list.size()-1 || index < 0 || list.isEmpty() ) return -1; Stack< Integer> stack = list.get(index); int result = stack.pop(); if(stack.isEmpty()) list.remove( index ); return result;

• 执行时间：60.44%；内存消耗：43.48%；

3.2.2 二维链表法（优）

class StackOfPlates private LinkedList< LinkedList< Integer> > setOfStacks; private int cap; public StackOfPlates(int cap) this.setOfStacks = new LinkedList< > (); this.cap = cap; private boolean setIsEmpty() return setOfStacks.isEmpty(); private boolean lastStackIsFUll() if (setIsEmpty()) return true; return setOfStacks.getLast().size()> =cap; private boolean lastStackIsEmpty() return setOfStacks.getLast().isEmpty(); public void push(int val) if (cap < = 0) return; if (setIsEmpty() || lastStackIsFUll()) setOfStacks.addLast(new LinkedList< > ()); setOfStacks.getLast().addLast(val); public int pop() int val = -1; if (setIsEmpty()) return val; val = setOfStacks.getLast().removeLast(); if (lastStackIsEmpty()) setOfStacks.removeLast(); return val; public int popAt(int index) int val = -1; if (setIsEmpty() ||setOfStacks.size()-1< index ) return val; val = setOfStacks.get(index).removeLast(); if (setOfStacks.get(index).isEmpty()) setOfStacks.remove(index); return val;

• 执行时间：96.23%；内存消耗：60.59%；
• 使用二维的链表存储，每次当前栈满了就新增；

4. 化栈为队 [easy]
文章图片

4.1 考虑点

• 下诉第一种解法会存在大量重复操作，可以使用第二种延迟移动的方法，在有必要时才反转次序；

4.2 解法 4.2.1 双栈法

class MyQueue Stack< Integer> stack; Stack< Integer> cache; /** Initialize your data structure here. */ public MyQueue() Stack< Integer> stack = new Stack< > (); Stack< Integer> cache = new Stack< > (); this.stack = stack; this.cache = cache; /** Push element x to the back of queue. */ public void push(int x) stack.add(x); /** Removes the element from in front of queue and returns that element. */ public int pop() if(stack.isEmpty()) return -1; while( !stack.isEmpty() ) cache.add(stack.pop()); int result = cache.pop(); while( !cache.isEmpty() ) stack.add(cache.pop()); return result; /** Get the front element. */ public int peek() if(stack.isEmpty()) return -1; while( !stack.isEmpty() ) cache.add(stack.pop()); int result = cache.peek(); while( !cache.isEmpty() ) stack.add(cache.pop()); return result; /** Returns whether the queue is empty. */ public boolean empty() return stack.isEmpty();

• 执行时间：81.59%；内存消耗：53.96%；

4.2.2 延迟移动法（优）

class MyQueue Deque< Integer> inStack; Deque< Integer> outStack; public MyQueue() inStack = new LinkedList< Integer> (); outStack = new LinkedList< Integer> (); public void push(int x) inStack.push(x); public int pop() if (outStack.isEmpty()) in2out(); return outStack.pop(); public int peek() if (outStack.isEmpty()) in2out(); return outStack.peek(); public boolean empty() return inStack.isEmpty() & & outStack.isEmpty(); private void in2out() while (!inStack.isEmpty()) outStack.push(inStack.pop());

• 执行时间：100.00%；内存消耗：35.19%；
• 只有进行pop()和peek()操作，并且输出栈为空时才需要翻转次序；
• 当有必要反转次序时才移动元素，用户进行连续pop()操作时不需要反转次序；

5. 栈排序 [medium]
文章图片

5.1 考虑点

• 需要注意细节；
• 可以考虑延迟移动；

5.2 解法 5.2.1 单栈法

class SortedStack Stack< Integer> stack; Stack< Integer> cache; public SortedStack() Stack< Integer> stack = new Stack< > (); Stack< Integer> cache = new Stack< > (); this.stack = stack; this.cache = cache; public void push(int val) if( stack.isEmpty() ) stack.add(val); return; if( stack.peek() > val ) stack.add(val); else cache.add(stack.pop()); stack.add(val); stack.add(cache.pop()); public void pop() if( stack.isEmpty() ) return; stack.pop(); int val; if( !stack.isEmpty() ) val = stack.peek(); //忘记peek else return; while(!stack.isEmpty()) if( stack.peek() > = val ) cache.add(stack.pop()); else val = stack.peek(); boolean isEliminate = false; while( !cache.isEmpty() ) if( cache.peek() == val & & !isEliminate ) cache.pop(); isEliminate = true; //忘记上锁 else stack.add( cache.pop() ); stack.add(val); public int peek() if(stack.isEmpty()) return -1; return stack.peek(); public boolean isEmpty() return stack.isEmpty();

• 执行时间：5.04%；内存消耗：70.80%；
• 这里的单栈指每次操作后数据都存储在一个栈，另一个栈只做辅助作用，可以用其他数据结构代替；

5.2.2 根据插入值分离栈法（优）

class SortedStack //原始栈 Deque< Integer> stack = new LinkedList< > (); //辅助栈 Deque< Integer> tmp = new LinkedList< > (); public SortedStack() public void push(int val) int max = stack.isEmpty() ? Integer.MAX_VALUE : stack.peek(); int min = tmp.isEmpty() ? Integer.MIN_VALUE : tmp.peek(); //比较原始栈与辅助栈栈顶值，使其满足 辅助栈 < = val < = 原始栈 while(true) if(val > max) tmp.push(stack.pop()); max = stack.isEmpty() ? Integer.MAX_VALUE : stack.peek(); else if(val < min) stack.push(tmp.pop()); min = tmp.isEmpty() ? Integer.MIN_VALUE : tmp.peek(); else stack.push(val); break; public void pop() //将辅助栈元素push回原始栈 while (!tmp.isEmpty()) stack.push(tmp.pop()); if (!stack.isEmpty()) stack.pop(); public int peek() //将辅助栈元素push回原始栈 while (!tmp.isEmpty()) stack.push(tmp.pop()); return stack.isEmpty() ? -1 : stack.peek(); public boolean isEmpty() return stack.isEmpty() & & tmp.isEmpty();

• 执行时间：99.65%；内存消耗：81.59%；
• push()操作后数据可以分布在两个栈中，只有pop()或peek()操作时才考虑将储存值比较小的栈归位；

6. 动物收容所 [easy]
文章图片

6.1 考虑点

• 可以问问面试官允许使用多少个链表（或其他数据结构）；
• 这个问题有多种解法，如果使用一个队列，对dequeueAny()操作简单，而dequeueCat()和dequeueDog()则需要遍历整个队列，降低执行效率；（对应解法一）
• 另一种解法是猫狗各自创建一个队列，放进包装类里，包装类有个时间戳属性，用来标记进入时间，在执行dequeueAny()操作时只需要查看两个队列的的首部，比较时间戳，返回较老那位；（对应解法二）

6.2 解法 6.2.1 单链表法

class AnimalShelf List< String> list; public AnimalShelf() List< String> list = new ArrayList< > (); this.list = list; public void enqueue(int[] animal) if( animal[0] < 0 || animal[1] < 0 || animal[1] > 2) return; String animalStr = String.valueOf(animal[0]) + String.valueOf(animal[1]); list.add(animalStr); public int[] dequeueAny() if( list.isEmpty() ) return new int[]-1, -1; String result = list.get(0); list.remove(0); int num = Integer.parseInt(result); return new int[]num/10, num%10; public int[] dequeueDog() if( list.isEmpty() ) return new int[]-1, -1; for( int i = 0; i < list.size(); i++) int num = Integer.parseInt( list.get(i) ); if( num%10 == 1 ) list.remove(i); return new int[]num/10, num%10; return new int[]-1, -1; public int[] dequeueCat() if( list.isEmpty() ) return new int[]-1, -1; for( int i = 0; i < list.size(); i++) int num = Integer.parseInt( list.get(i) ); if( num%10 == 0 ) list.remove(i); return new int[]num/10, num%10; return new int[]-1, -1;

• 执行时间：17.07%；内存消耗：97.72%；

6.2.2 双队列法（优）

class AnimalShelf LinkedList< int[]> queueCat; LinkedList< int[]> queueDog; public AnimalShelf() queueCat = new LinkedList< > (); queueDog = new LinkedList< > (); public void enqueue(int[] animal) // 判断种类后入队 if (animal[1] == 0) queueCat.addLast(animal); else if (animal[1] == 1) queueDog.addLast(animal); public int[] dequeueAny() // 取出cat的队首，判空则直接返回 int[] headCat; if (!queueCat.isEmpty()) headCat = queueCat.getFirst(); else if (!queueDog.isEmpty()) return queueDog.removeFirst(); else return new int[]-1,-1; // 取出dog的队首，判空则直接返回 int[] headDog; if (!queueDog.isEmpty()) headDog = queueDog.getFirst(); else return queueCat.removeFirst(); // 比较后返回 if (headCat[0]< =headDog[0]) return queueCat.removeFirst(); else return queueDog.removeFirst(); public int[] dequeueDog() if (!queueDog.isEmpty()) return queueDog.removeFirst(); else return new int[]-1,-1; public int[] dequeueCat() if (!queueCat.isEmpty()) return queueCat.removeFirst(); else return new int[]-1,-1;

• 执行时间：98.86；内存消耗：29.43%；
• 建立两个队列，分别存储猫和狗。dequeCat和dequeDog分别取对应的队首；

最后::: hljs-center
新人制作，如有错误，欢迎指出，感激不尽！
:::
::: hljs-center
欢迎关注公众号，会分享一些更日常的东西！
:::
::: hljs-center
如需转载，请标注出处！
:::
::: hljs-center

文章图片

:::

推荐阅读

• 

  漂完头发怎么护理
• 

  安卓设置菜单,安卓系统更新添特殊功能下拉菜单透明背景
• 

  进入王者荣耀职业战队需要具备哪些条件,王者荣耀职业战队的门槛是不是很低
• 

  2023年属兔的人几月出生命不好
• 

  夸父逐日的寓意和启示 夸父逐日的寓意和启示有哪些
• 

  塞尔达利兄弟岩在哪里
• 

  二次元狂热
• 

  徐州货车通行证怎么办理流程 2023徐州市区货车通行证有哪些车型?
• 

  初三男孩叛逆严重怎么办 初三叛逆期男孩子该怎么办
• 

  物联网|所有行业都应该开始做手机
• 

  厕所堵住了该怎么疏通最简单方法
• 

  chiniQOO 8最全配置表，背刺小米MIX4，网友：五千也想买
• 

  为何选在谷雨节祭祀仓颉 祭仓颉走谷雨是什么意思
• 

  空气炸锅炸鸡排要刷油吗
• 

  HTTP3/QUIC|HTTP3/QUIC 性能测试与配套组件
• 

  神经网络控制案例分析,matlab神经网络43个案例分析百度云
• 

  鞋子走路有声音是怎么回事 一走路鞋就发出唧唧响，Nike正品会走路摩擦地板响
• 

  交易猫提现手续费要多少？交易猫提现需要多长时间？
• 

  erp系统运营工作总结，erp系统运行情况报告
• 

  大金空调显示u8怎么回事，遇到这种故障解决步骤

• SpringBoot整合Redis 之 lettuce#私藏项目实操分享#
• Redis数据类型详细讲解（sethashzset）
• Shell脚本基本编辑规范及变量
• #yyds干货盘点#十大经典排序之（基数排序 ｜计数排序）
• 流水线pipeline招式之声明式（前篇）
• go -Unmarshal 错误的几种情况
• #yyds干货盘点#ECMAScript 6 - Symbol
• vue日期转换及时区问题 #yyds干货盘点#
• 未捕获的TypeError（无法读取未定义的属性”id”）