1.数据结构 1.1 ArrayDeque （栈、队列） 1.2 LinkedList 1.3 PriorityQueue 2.编程题 Q1.描述如何只用一个数组来实现三个栈
Ans.思路：

• 简单的方法是分配固定空间大小
• 较难的方式：弹性处理栈空间。将数组设计成环状。
  1）push的实现方式：
  1-1）正常情况，直接增加，注意是环形的；
  1-2）当栈的size达到capacity时，此时需要扩容该栈。
  当三个栈全满时，无法处理，此时抛出异常；
  否则，将当前栈的下一个栈向后移动一个位置，如果下一个栈也满了，递归处理（总会有一个栈没满，因为全满时会抛出异常）。移动时，因为是环形的，处理时也要注意。
  2）pop实现方式：
  size为空，抛出异常；
  否则，按照栈的正常弹出处理，注意是环形的。比push要简单。

简单的方式：

static int stackSize = 10; static int [] buffer = new int [stackSize * 3]; // 3 stack pointers to keep track of the index of the top element static int [] stackPointer = {-1, -1, -1}; static void push(int stackNum, int value) throws Exception { /* Check that we have space for the next element */ if (stackPointer[stackNum] + 1 >= stackSize) { throw new FullStackException(); } /* Increment stack pointer and then update top value*/ stackPointer[stackNum]++; buffer[absTopOfStack(stackNum)] = value; }static int pop(int stackNum) throws Exception { if (isEmpty(stackNum)) { throw new EmptyStackException(); } int value = https://www.it610.com/article/buffer[absTopOfStack(stackNum)]; // Get top buffer[absTopOfStack(stackNum)] = 0; // Clear index stackPointer[stackNum]--; // Decrement pointer return value; }static int peek(int stackNum) { if (isEmpty(stackNum)) { throw new EmptyStackException(); } return buffer[absTopOfStack(stackNum)]; }static boolean isEmpty(int stackNum) { return stackPointer[stackNum] == -1; }/* returns index of the top of the stack"stackNum", in absolute terms */ static int absTopOfStack(int stackNum) { return stackNum * stackSize + stackPointer[stackNum]; }

弹性方式：

static void push(int stackNum, int value) throws Exception { StackData stack = stacks[stackNum]; /* Check that we have space */ if (stack.size >= stack.capacity) { if (numberOfElements() >= total_size) { // Totally full throw new Exception("Out of space."); } else { // just need to shift things around expand(stackNum); } } /* Find the index of the top element in the array + 1, * and increment the stack pointer */ stack.size++; stack.pointer = nextElement(stack.pointer); buffer[stack.pointer] = value; }static int pop(int stackNum) throws Exception { StackData stack = stacks[stackNum]; if (stack.size == 0) { throw new Exception("Trying to pop an empty stack."); } int value = https://www.it610.com/article/buffer[stack.pointer]; buffer[stack.pointer] = 0; stack.pointer = previousElement(stack.pointer); stack.size--; return value; }static int peek(int stackNum) { StackData stack = stacks[stackNum]; return buffer[stack.pointer]; }static boolean isEmpty(int stackNum) { StackData stack = stacks[stackNum]; return stack.size == 0; }

辅助方法：

public static int numberOfElements() { return stacks[0].size + stacks[1].size + stacks[2].size; }public static int nextElement(int index) { if (index + 1 == total_size) { return 0; } else { return index + 1; } }public static int previousElement(int index) { if (index == 0) { return total_size - 1; } else { return index - 1; } }public static void shift(int stackNum) { StackData stack = stacks[stackNum]; if (stack.size >= stack.capacity) { int nextStack = (stackNum + 1) % number_of_stacks; shift(nextStack); // make some room stack.capacity++; } for (int i = (stack.start + stack.capacity - 1) % total_size; // end of array stack.isWithinStack(i, total_size); i = previousElement(i)) { buffer[i] = buffer[previousElement(i)]; } buffer[stack.start] = 0; stack.start = nextElement(stack.start); // move start start stack.pointer = nextElement(stack.pointer); // move stack pointer stack.capacity--; // return capacity to original }

栈数据为：

public class StackData { public int start; public int pointer; public int size = 0; public int capacity; public StackData(int _start, int _capacity) { start = _start; pointer = _start - 1; capacity = _capacity; }public boolean isWithinStack(int index, int total_size) { // Note: if stack wraps, the head (right side) wraps around to the left. if (start <= index && index < start + capacity) { // non-wrapping, or "head" (right side) of wrapping case return true; } else if (start + capacity > total_size && index < (start + capacity) % total_size) { // tail (left side) of wrapping case return true; } return false; } }

Q2.设计一个栈，除pop与push方法，还支持min方法，可返回栈元素中的最小值。push、pop和min三个方法的时间复杂度必须为O(1)。
Ans.思路：

• 使用举例方法，即可发现规律
  push(5) —— 栈:5，min 5
  push(6) —— 栈:5 6，min 5
  push(3) —— 栈:5 6 3，min 3
  push(7) —— 栈:5 6 3 7，min 3
  pop() —— 栈:5 6 3, min 3
  pop() —— 栈:5 6, min 5
  pop() —— 栈:5, min 5
  一种直接的思路是，对于每个入栈的元素，会记录下当前最小值。
• 改进：上面做法较为浪费空间，一种改进的做法，利用栈来记录这些min。当压入栈的值value <= min当前最小值，则入栈。必须要取等号，防止多个想等值入栈后，弹出时出错。

public class StackWithMin2 extends ArrayDeque { ArrayDeque s2; public StackWithMin2() { s2 = new ArrayDeque(); }@Override public void push(Integer value){ if (value <= min()) { s2.push(value); } super.push(value); }@Override public Integer pop() { int value = https://www.it610.com/article/super.pop(); if (value == min()) { s2.pop(); } return value; }public int min() { if (s2.isEmpty()) { return Integer.MAX_VALUE; } else { return s2.peek(); } } }

Q3.设想有一堆盘子，堆太高可能会倒下。因此，在现实生活中，盘子堆到一定高度时，就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同。 实现一个popAt(int index)方法，根据指定子栈，执行pop操作。
Ans.思路：

• push：对当前最后一个栈调用push，若最后一个栈是满的，则新建一个栈
• pop：操作最后一个栈，弹出后，若最后一个栈为空，则必须移除该栈
• popAt(int index)：1）弹出时，后续栈补入，这样操作对于用户是透明的；2）弹出时，后续不进行补入，但是底层的假设有变化，即所有栈都是满的这一条件不再满足。

public class SetOfStacks { ArrayList stacks = new ArrayList(); public int capacity; public SetOfStacks(int capacity) { this.capacity = capacity; }public Stack getLastStack() { if (stacks.size() == 0) { return null; } return stacks.get(stacks.size() - 1); }public void push(int v) { Stack last = getLastStack(); if (last != null && !last.isFull()) { // add to last last.push(v); } else { // must create new stack Stack stack = new Stack(capacity); stack.push(v); stacks.add(stack); } }public int pop() { Stack last = getLastStack(); int v = last.pop(); if (last.size == 0) { stacks.remove(stacks.size() - 1); } return v; }public int popAt(int index) { return leftShift(index, true); }public int leftShift(int index, boolean removeTop) { Stack stack = stacks.get(index); int removed_item; if (removeTop) removed_item = stack.pop(); else removed_item = stack.removeBottom(); if (stack.isEmpty()) { stacks.remove(index); } else if (stacks.size() > index + 1) { int v = leftShift(index + 1, false); stack.push(v); } return removed_item; }public boolean isEmpty() { Stack last = getLastStack(); return last == null || last.isEmpty(); } }

单个栈：

public class Stack { private int capacity; public Node top; public Node bottom; public int size = 0; public Stack(int capacity) { this.capacity = capacity; }public boolean isFull() { return capacity == size; }public void join(Node above, Node below) { if (below != null) below.above = above; if (above != null) above.below = below; }public boolean push(int v) { if (size >= capacity) return false; size++; Node n = new Node(v); if (size == 1) bottom = n; join(n, top); top = n; return true; }public int pop() { Node t = top; top = top.below; size--; return t.value; }public boolean isEmpty() { return size == 0; }public int removeBottom() { Node b = bottom; bottom = bottom.above; if (bottom != null) bottom.below = null; size--; return b.value; } }

元素类型：

public class Node { public Node above; public Node below; public int value; public Node(int value) { this.value = https://www.it610.com/article/value; } }

Q4.在经典问题汉诺塔中，有三根柱子及N个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自底向上从大到小依次套在第一根柱子上（即每一个盘子只能放在更大的盘子上面）。移动圆盘时有以下限制：
1）每次只能移动一个盘子
2）盘子只能从柱子顶端滑出移到下一根柱子
3）盘子只能叠在比它大的盘子上
请运用栈，编写程序将所有盘子从第一根柱子移动到最后一根柱子。
Ans.思路：

• 一种很显然的思路是：递归法。
  从最终状态（所有盘子在第三根柱子）回退至前面一大步（最大盘子在第三根柱子，其他盘子在第二根柱子）；
  然后转化为解决子问题：怎样将n-1个盘子从第一个柱子移动到第二根柱子。
  递归子问题性质一样，可以一直这样向下进行解决。

思路伪代码描述：

moveDisks(int n, Tower origin, Tower destination, Tower buffer) { if (n <= 0) return; // 将n-1个盘子从origin移动到buffer moveDisks(n - 1, origin, buffer, destination); // 将剩下的最大的盘子移动到destination moveTop(origin, destination); // 将顶部n - 1个盘子从buffer移至destination moveDisks(n - 1, buffer, destination, origin); }

【栈与队列】代码：

public class Tower { private ArrayDeque disks; private int index; public Tower(int i) { disks = new ArrayDeque(); index = i; }public int index() { return index; }public void add(int d) { if (!disks.isEmpty() && disks.peek() <= d) { System.out.println("Error placing disk " + d); } else { disks.push(d); } }public void moveTopTo(Tower t) { int top = disks.pop(); t.add(top); }public void print() { System.out.println("Contents of Tower " + index() + ": " + disks.toString()); }public void moveDisks(int n, Tower destination, Tower buffer){ if (n > 0) { String tag = "move_" + n + "_disks_from_" + this.index + "_to_" + destination.index + "_with_buffer_" + buffer.index; System.out.println("<" + tag + ">"); moveDisks(n - 1, buffer, destination); System.out.println(""); System.out.println(""); System.out.println(""); this.print(); System.out.println(""); System.out.println(""); destination.print(); System.out.println(""); System.out.println(""); moveTopTo(destination); System.out.println(""); System.out.println(""); this.print(); System.out.println(""); System.out.println(""); destination.print(); System.out.println(""); System.out.println(""); System.out.println(""); buffer.moveDisks(n - 1, destination, this); System.out.println(""); } } }

Q5.实现一个MyQueue类，该类用两个栈来实现一个队列。
Ans.思路

• 一个栈用于入队；利用另一个栈反转次序，该栈用于出队。
• 当出队的栈为空时，此时再将入队的栈压入。

public class MyQueue { ArrayDeque stackNewest, stackOldest; public MyQueue() { stackNewest = new ArrayDeque(); stackOldest = new ArrayDeque(); }public int size() { return stackNewest.size() + stackOldest.size(); }public void add(T value) { // Push onto stack1 stackNewest.push(value); }/* Move elements from stackNewest into stackOldest. This is usually done so that we can * do operations on stackOldest. */ private void shiftStacks() { if (stackOldest.isEmpty()) { while (!stackNewest.isEmpty()) { stackOldest.push(stackNewest.pop()); } } }public T peek() { shiftStacks(); return stackOldest.peek(); // retrieve the oldest item. }public T remove() { shiftStacks(); return stackOldest.pop(); // pop the oldest item. } }

Q6.编写程序，按升序对栈进行排序（即最大元素位于栈顶）。最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中（如数组）。该栈支持如下操作：push、pop、peek和isEmpty。
Ans.思路：

• 核心点是：s1栈是乱序的，s2是有序的，怎样将s1中的数有序插入到s2中？
• 方法（本质跟汉诺塔一样）：
  step1.弹出s1的数到临时变量top
  step2.将s2中大于top的全部弹出到s1中，压入top
  step3.再将之前弹出到s1中的压回到s2

public static ArrayDeque sort(ArrayDeque s) { ArrayDeque r = new ArrayDeque(); while(!s.isEmpty()) { int tmp = s.pop(); while(!r.isEmpty() && r.peek() > tmp) { s.push(r.pop()); } r.push(tmp); } return r; }

如果不限栈数量，可以使用mergesort思路，实现时要特别注意：要保持栈里面的顺序是栈顶为最大，随意最后有一个reverse的过程必不可少。

static int c = 0; public static ArrayDeque mergesort(ArrayDeque inStack) { if (inStack.size() <= 1) { return inStack; }ArrayDeque left = new ArrayDeque(); ArrayDeque right = new ArrayDeque(); int count = 0; while (inStack.size() != 0) { count++; c++; if (count % 2 == 0) { left.push(inStack.pop()); } else { right.push(inStack.pop()); } }left = mergesort(left); right = mergesort(right); while (left.size() > 0 || right.size() > 0) { if (left.size() == 0) { inStack.push(right.pop()); } else if (right.size() == 0) { inStack.push(left.pop()); } else if (right.peek().compareTo(left.peek()) <= 0) { inStack.push(left.pop()); } else { inStack.push(right.pop()); } }ArrayDeque reverseStack = new ArrayDeque(); while (inStack.size() > 0) { c++; reverseStack.push(inStack.pop()); }return reverseStack; }

Q7.有家动物收容所收容狗和猫，且严格遵循“先进先出”原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”的动物，或者，可以挑选猫或狗（同时必须是此类中最老的）。请创建适用于这个系统的数据结构，实现enqueue dequeueAny dequeueDog dequeueCat。允许使用LinkedList。
Ans.思路

• 直观的方法是猫狗各创建一个队列，然后放入一个包裹类。

public class AnimalQueue { LinkedList dogs = new LinkedList(); LinkedList cats = new LinkedList(); private int order = 0; public void enqueue(Animal a) { a.setOrder(order); order++; if (a instanceof Dog) { dogs.addLast((Dog) a); } else if (a instanceof Cat) { cats.addLast((Cat)a); } }public Animal dequeueAny() { if (dogs.size() == 0) { return dequeueCats(); } else if (cats.size() == 0) { return dequeueDogs(); } Dog dog = dogs.peek(); Cat cat = cats.peek(); if (dog.isOlderThan(cat)) { return dogs.poll(); } else { return cats.poll(); } }public Animal peek() { if (dogs.size() == 0) { return cats.peek(); } else if (cats.size() == 0) { return dogs.peek(); } Dog dog = dogs.peek(); Cat cat = cats.peek(); if (dog.isOlderThan(cat)) { return dog; } else { return cat; } }public int size() { return dogs.size() + cats.size(); }public Dog dequeueDogs() { return dogs.poll(); }public Dog peekDogs() { return dogs.peek(); }public Cat dequeueCats() { return cats.poll(); }public Cat peekCats() { return cats.peek(); } }

动物类：

public abstract class Animal { private int order; protected String name; public Animal(String n) { name = n; }public abstract String name(); public void setOrder(int ord) { order = ord; }public int getOrder() { return order; }public boolean isOlderThan(Animal a) { return this.order < a.getOrder(); } }

public class Cat extends Animal { public Cat(String n) { super(n); }public String name() { return "Cat: " + name; } }

public class Dog extends Animal { public Dog(String n) { super(n); }public String name() { return "Dog: " + name; } }

推荐阅读

• 

  vb.net操作硬件 vbnet implements
• 

  今日淘汰鸡全国价格 今日鸡蛋价格
• 

  小宅vr眼镜好用吗 小宅魔镜头盔使用说明
• 

  毕业季家长的感言美句 家长对老师的感言简短
• 

  洛神花怎么养护 洛神花怎么养能开花
• 

  鸿蒙3安全流畅，鸿蒙系统安全程度
• 

  2022三九天时间表 三九天2021时间表图
• 

  暗杀动作手机游戏，暗杀系列游戏大全
• 

  ospf路由表分析,OSPF路由表的作用
• 

  植发3000个毛囊面积图 植发三千个毛囊单位有多少面积
• 

  美股怎么选 美股怎么选股
• 

  世界word安卓,如何使用安卓用手机打印pdf?
• 

  关于重阳节的诗词 重阳节有哪些诗词
• 

  红豆薏米芡实茶哪些人不能喝
• 

  香辣帝王蟹的做法 帝王蟹做法
• 

  万像素|荣耀X30 MAX，不只有大！
• 

  想减肥的人少吃鸡翅 这些高热量食物减肥期间不要碰
• 

  郭德纲的麒麟剧社有发展前途吗？能不能最后收编主流京剧界？
• 

  传统的汽配公司在干什么 汽配公司属于什么行业
• 

  桌游黑暗之魂好玩吗 黑暗之魂游戏介绍和攻略

• JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
• Docker应用:容器间通信与Mariadb数据库主从复制
• 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
• 第326天
• Shell-Bash变量与运算符
• 逻辑回归的理解与python示例
• Guava|Guava RateLimiter与限流算法
• 我和你之前距离
• CGI，FastCGI，PHP-CGI与PHP-FPM
• 原生家庭之痛与超越