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 = 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 = 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<Integer> {
ArrayDeque<Integer> s2;
public StackWithMin2() {
s2 = new ArrayDeque<Integer>();
}
@Override
public void push(Integer value){
if (value <= min()) {
s2.push(value);
}
super.push(value);
}
@Override
public Integer pop() {
int value = 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<Stack> stacks = new ArrayList<Stack>();
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 = 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<Integer> disks;
private int index;
public Tower(int i) {
disks = new ArrayDeque<Integer>();
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("<move_top_from_" + this.index + "_to_" + destination.index + ">");
System.out.println("<before>");
System.out.println("<source_print>");
this.print();
System.out.println("</source_print>");
System.out.println("<destination_print>");
destination.print();
System.out.println("</destination_print>");
System.out.println("</before>");
moveTopTo(destination);
System.out.println("<after>");
System.out.println("<source_print>");
this.print();
System.out.println("</source_print>");
System.out.println("<destination_print>");
destination.print();
System.out.println("</destination_print>");
System.out.println("</after>");
System.out.println("</move_top_from_" + this.index + "_to_" + destination.index + ">");
buffer.moveDisks(n - 1, destination, this);
System.out.println("</" + tag + ">");
}
}
}
Q5.实现一个MyQueue类，该类用两个栈来实现一个队列。
Ans.思路
- 一个栈用于入队；利用另一个栈反转次序，该栈用于出队。
- 当出队的栈为空时，此时再将入队的栈压入。
public class MyQueue<T> {
ArrayDeque<T> stackNewest, stackOldest;
public MyQueue() {
stackNewest = new ArrayDeque<T>();
stackOldest = new ArrayDeque<T>();
}
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<Integer> sort(ArrayDeque<Integer> s) {
ArrayDeque<Integer> r = new ArrayDeque<Integer>();
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<Integer> mergesort(ArrayDeque<Integer> inStack) {
if (inStack.size() <= 1) {
return inStack;
}
ArrayDeque<Integer> left = new ArrayDeque<Integer>();
ArrayDeque<Integer> right = new ArrayDeque<Integer>();
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<Integer> reverseStack = new ArrayDeque<Integer>();
while (inStack.size() > 0)
{
c++;
reverseStack.push(inStack.pop());
}
return reverseStack;
}
Q7.有家动物收容所收容狗和猫，且严格遵循“先进先出”原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”的动物，或者，可以挑选猫或狗（同时必须是此类中最老的）。请创建适用于这个系统的数据结构，实现enqueue dequeueAny dequeueDog dequeueCat。允许使用LinkedList。
Ans.思路
- 直观的方法是猫狗各创建一个队列，然后放入一个包裹类。
public class AnimalQueue {
LinkedList<Dog> dogs = new LinkedList<Dog>();
LinkedList<Cat> cats = new LinkedList<Cat>();
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;
}
}
