Interview Questions: Stacks and Queues

Stacks and Queues

Queue with two stacks. Implement a queue with two stacks so that each queue operations takes a constant amortized number of stack operations.

利用两个栈来实现队列，具体方法为：入队等同于栈A进栈；出队时如果栈B不空，则栈B出栈，如果栈B为空，则依次将栈A元素出栈，并压入栈B。(因Stack被官方不推荐，采用LinkedList来实现栈结构)

import java.util.LinkedList;public class StackQueue<E> {LinkedList<E> stackA;LinkedList<E> stackB;public StackQueue() {stackA = new LinkedList<>();stackB = new LinkedList<>();}public boolean isEmpty() {return stackA.isEmpty() && stackB.isEmpty();}public void enqueue(E item) {stackA.push(item);}public E dequeue() {if (stackB.isEmpty()) {if (stackA.isEmpty()) {return null;}while (!stackA.isEmpty()) {E temp = stackA.pop();stackB.push(temp);}}return stackB.pop();}public int size() {return stackA.size() + stackB.size();}
}

Stack with max. Create a data structure that efficiently supports the stack operations (push and pop) and also a return-the-maximum operation. Assume the elements are real numbers so that you can compare them.

维护两个栈来实现输出最大值：一个为普通栈stack，一个用于保存与当前普通栈中元素相对应的最大值栈maxStack。push新元素x时，如果当前maxStack为空，或者x值大于等于maxStack栈顶元素，说明x是加入后普通栈中的最大值，需要在maxStack入栈；pop栈顶元素x时，如果x与maxStack栈顶元素相同，说明x正是当前普通栈中的最大值，也需要在maxStack出栈。

import java.util.LinkedList;public class MaxStack {private LinkedList<Integer> stack;private LinkedList<Integer> maxStack;public MaxStack() {stack = new LinkedList<>();maxStack = new LinkedList<>();}public boolean isEmpty() {return stack.isEmpty();}public void push(int x) {if (maxStack.isEmpty() || x >= maxStack.peek()) {maxStack.push(x);}stack.push(x);}public void pop() {// 注意不能用stack.peek()==maxStack.peek()进行判断，// 这样做比较的是Integer对象本身而不是int值int max = maxStack.peek();if (stack.peek() == max) {maxStack.pop();}stack.pop();}public int findMax() {return maxStack.peek();}
}

Java generics. Explain why Java prohibits generic array creation.

• 泛型的实现是靠类型擦除。 类型擦除是在编译期完成的， 也就是在编译期， 编译器会将泛型的类型参数都擦除成它的限定类型，如果没有则擦除为object类型，之后在获取的时候再强制类型转换为对应的类型。 在运行期间并没有泛型的任何信息。

• 泛型设计的原则是：如果编译期间没有提出“未经检查的转换”警告，则程序在运行时不会引发ClassCastException警告。

• 如果允许创建泛型数组，则有以下代码：

  A<String>[] arr = new A<String>[1];
  Object[] objArr = arr;
  objArr[0] = new A<Integer>();
  string a = arr[0].get(0);
  

  上述代码能够通过编译，但在运行时会引发ClassCastException警告，这就违背了泛型的设计原则。