Java 面试题 - Stack and Queue

ArrayDeque

• Resizable-array implementation of the Deque interface.
• 此类很可能在用作堆栈时快于 Stack，在用作队列时快于 LinkedList。大多数 ArrayDeque 操作以摊销的固定时间运行。

JAVA中Stack和Heap的区别

• 每个应用程序运行时，都有属于自己的一段内存空间，用于存放临时变量、参数传递、函数调用时的PC值的保存。这叫stack。
• 所有的应用可以从一个系统共用的空间中申请供自己使用的内存，这个共用的空间叫heap。
• Java中对象都是分配在heap(堆)中。从heap中分配内存所消耗的时间远远大于从stack产生存储空间所需的时间。
• 要使用heap中申请的变量或对象只能定义变量指针，并要求在运行过程中通过new来动态分配内存空间，而且必须显示地free你申请过的内存，不过Java的垃圾回收机解决了这个问题，它会帮你释放这部分内存。
• 另外，栈有一个很重要的特殊性，就是存在栈中的数据可以共享。int a=3; int b=3; 创建 a 变量后，由于在栈中已经有3这个字面值，于是 b 直接指向3的地址。在编译器内部，遇到 a=4；时，它就会重新搜索栈中是否有4的字面值，如果没有，重新开辟地址存放4的值；如果已经有了，则直接将a指向这个地址。因此a值的改变不会影响到b的值。
• 像String str = “abc”；这种场合下，其字符串值是保存了一个指向存在栈中数据的引用；

面试题补充

1、 Describe how you could use a single array to implement three stacks

int stackSize = 300;
int[] buffer = new int [stackSize * 3];
int[] stackPointer = {0, 0, 0}; // stack pointers to track top elem
void push(int stackNum, int value) {
  /* Find the index of the top element in the array + 1, and
    * increment the stack pointer */
  int index = stackNum * stackSize + stackPointer[stackNum] + 1;
  stackPointer[stackNum]++;
  buffer[index] = value; 
}
int pop(int stackNum) {
  int index = stackNum * stackSize + stackPointer[stackNum];
  stackPointer[stackNum]--;
  int value = buffer[index];
  buffer[index]=0;
  return value;
}
int peek(int stackNum) {
  int index = stackNum * stackSize + stackPointer[stackNum];
  return buffer[index];
}
boolean isEmpty(int stackNum) {
  return stackPointer[stackNum] == stackNum*stackSize;
}

2、How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

// first solution:
public class StackWithMin extends Stack<NodeWithMin> {
    public void push(int value) {
        int newMin = Math.min(value, min());
        super.push(new NodeWithMin(value, newMin));
    }
    
    public int min() {
      if (this.isEmpty()) {
        return Integer.MAX_VALUE;
      } else {
        return peek().min;
      }
    }
}
class NodeWithMin {
    public int value;
    public int min;
    public NodeWithMin(int v, int min){
        value = v;
        this.min = min;
    }
}
// second:
public class StackWithMin2 extends Stack<Integer> {
  Stack<Integer> s2;
  public StackWithMin2() {
    s2 = new Stack<Integer>();   
  }
  public void push(int value){
    if (value <= min()) {
      s2.push(value);
    }
    super.push(value);
  }
  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();
    }
  }
}

4、Implement a MyQueue class which implements a queue using two stacks

public class MyQueue<T> {
  Stack<T> s1, s2;
  public MyQueue() {
    s1 = new Stack<T>();
    s2 = new Stack<T>();
  }
 
  public int size() { 
    return s1.size() + s2.size(); 
  }
 
  public void add(T value) { 
    s1.push(value); 
  }
 
  public T peek() {
    if (!s2.empty()) return s2.peek();
    while (!s1.empty()) s2.push(s1.pop());
    return s2.peek(); 
  }
 
  public T remove() {
    if (!s2.empty()) return s2.pop();
    while (!s1.empty()) s2.push(s1.pop());
    return s2.pop();
  }
}

5、Write a program to sort a stack in ascending order You should not make any assumptions about how the stack is implemented The following are the only functions that should be used to write this program: push | pop | peek | isEmpty

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