Chapter 8: Stack and Queue Algorithm from Elements of Programming Interviews

RPN
  public static int eval(String s) {
    LinkedList<Integer> evalStack = new LinkedList<Integer>();
    String[] symbols = s.split(",");
    for (String symbol : symbols) {
      if (symbol.length() == 1 && "+-*/".contains(symbol)) {
        int y = evalStack.pop();
        int x = evalStack.pop();
        switch (symbol.charAt(0)) {
        case '+':
          evalStack.push(x + y);
          break;
        case '-':
          evalStack.push(x - y);
          break;
        case '*':
          evalStack.push(x * y);
          break;
        case '/':
          evalStack.push(x / y);
          break;
        default:
          throw new IllegalArgumentException("Malformed RPN at :" + symbol);
        }
      } else { // number.
        evalStack.push(Integer.parseInt(symbol));
      }
    }
    return evalStack.pop();
  }

Search Postings List
  private static int searchPostingsListHelper(PostingListNode L, int order) {
    if (L != null && L.getOrder() == -1) {
      L.setOrder(order++);
      order = searchPostingsListHelper(L.getJump(), order);
      order = searchPostingsListHelper(L.getNext(), order);
    }
    return order;
  }

  public static void searchPostingsList(PostingListNode L) {
    searchPostingsListHelper(L, 0);
  }

  public static void searchPostingsList(PostingListNode L) {
    LinkedList<PostingListNode> s = new LinkedList<PostingListNode>();
    int order = 0;
    s.push(L);
    while (!s.isEmpty()) {
      PostingListNode curr = s.pop();
      if (curr != null && curr.getOrder() == -1) {
        curr.setOrder(order++);
        s.push(curr.getNext());
        s.push(curr.getJump());
      }
    }
  }
TowerHanoi - todo: iterative version
  private static void transfer(int n, ArrayList<LinkedList<Integer>> pegs,
      int from, int to, int use) {
    if (n > 0) {
      transfer(n - 1, pegs, from, use, to);
      pegs.get(to).push(pegs.get(from).pop());
      System.out.println("Move from peg " + from + " to peg " + to);
      transfer(n - 1, pegs, use, to, from);
    }
  }

  public static void moveTowerHanoi(int n) {
    ArrayList<LinkedList<Integer>> pegs = new ArrayList<LinkedList<Integer>>();
    for (int i = 0; i < 3; i++) {
      pegs.add(new LinkedList<Integer>());
    }

    // Initialize pegs.
    for (int i = n; i >= 1; --i) {
      pegs.get(0).push(i);
    }

    transfer(n, pegs, 0, 1, 2);
  }

ViewSunset
Stream from East to West
  public static <T extends Comparable<T>> LinkedList<Pair<Integer, T>>
      examineBuildingsWithSunset( InputStream sin) {
    int idx = 0; // building's index.
    T height;
    // Stores (building_idx, building_height) pair with sunset views.
    LinkedList<Pair<Integer, T>> buildingsWithSunset = new LinkedList<>();
    try {
      ObjectInputStream osin = new ObjectInputStream(sin);
      while (true) {
        height = (T) osin.readObject();
        while (!buildingsWithSunset.isEmpty()
            && height.compareTo(buildingsWithSunset.getLast().getSecond()) >= 0) {
          buildingsWithSunset.removeLast();
        }
        buildingsWithSunset.addLast(new Pair<Integer, T>(idx++, height));
      }
    } catch (ClassNotFoundException e) {
      System.out.println(e.getMessage());
    } catch (IOException e) {
      // Catching when there no more objects in InputStream
    }
    return buildingsWithSunset;
  }

Sort a Stack
  private static <T extends Comparable<T>> void insert(LinkedList<T> S, T e) {
    if (S.isEmpty() || S.peek().compareTo(e) <= 0) {
      S.push(e);
    } else {
      T f = S.pop();
      insert(S, e);
      S.push(f);
    }
  }

  public static <T extends Comparable<T>> void sort(LinkedList<T> S) {
    if (!S.isEmpty()) {
      T e = S.pop();
      sort(S);
      insert(S, e);
    }
  }

Normalized Path names
  public static String normalizedPathNames(String path) {
    LinkedList<String> s = new LinkedList<String>(); // Use LinkedList as a
                                                     // stack.
    // Special case: starts with "/", which is an absolute path.
    if (path.startsWith("/")) {
      s.push("/");
    }
    for (String token : path.split("/")) {
      if (token.equals("..")) {
        if (s.isEmpty() || s.peek().equals("..")) {
          s.push(token);
        } else {
          if (s.peek().equals("/")) {
            throw new RuntimeException("Path error");
          }
          s.pop();
        }
      } else if (!token.equals(".") && !token.isEmpty()) { // name.
        for (char c : token.toCharArray()) {
          if (c != '.' && !Character.isDigit(c) && !Character.isLetter(c)) {
            throw new RuntimeException("Invalid directory name");
          }
        }
        s.push(token);
      }
    }
    StringBuilder normalizedPath = new StringBuilder();
    if (!s.isEmpty()) {
      Iterator<String> it = s.descendingIterator();
      String prev = it.next();
      normalizedPath.append(prev);
      while (it.hasNext()) {
        if (!prev.equals("/")) {
          normalizedPath.append("/");
        }
        prev = it.next();
        normalizedPath.append(prev);
      }
    }
    return normalizedPath.toString();
  }
Binary TreeLevel Order -- Java Queue, better use ArrayQueue
public static <T> void printBinaryTreeLevelOrder(BinarySearchTree<T> n) {
// Prevent empty tree
if (n == null) {
return;
}
LinkedList<BinarySearchTree<T>> q = new LinkedList<BinarySearchTree<T>>();
q.push(n);
int count = q.size();
while (!q.isEmpty()) {
BinarySearchTree<T> front = q.pollLast();
System.out.print(front.getData() + " ");
if (front.getLeft() != null) {
q.push(front.getLeft());
}
if (front.getRight() != null) {
q.push(front.getRight());
}
if (--count == 0) {
System.out.println();
count = q.size();
}
}
}
Circular Queue
  public static class Queue<T> {
    private int head = 0, tail = 0, count = 0;
    private Object[] data;

    public Queue(int cap) {
      data = new Object[cap];
    }

    public void enqueue(T x) {
      // Dynamically resize due to data_.size() limit.
      if (count == data.length) {
        // Rearrange elements.
        Collections.rotate(Arrays.asList(data), -head);
        head = 0;
        tail = count;
        data = Arrays.copyOf(data, count << 1);
      }
      // Perform enqueue
      data[tail] = x;
      tail = (tail + 1) % data.length;
      ++count;
    }

    public T dequeue() {
      if (count != 0) {
        --count;
        T ret = (T) data[head];
        head = (head + 1) % data.length;
        return ret;
      }
      throw new RuntimeException("empty queue");
    }

    public int size() {
      return count;
    }
  }

Queue Using Two Integers
  public static class Queue {
    private int val = 0;
    private int size = 0, maxSize = (int) Math.floor(Math
        .log10(Integer.MAX_VALUE));

    public void enqueue(int x) {
      if (size >= maxSize) {
        throw new RuntimeException("queue overflow");
      }
      val = val * 10 + x;
      ++size;
    }

    public int dequeue() {
      if (size != 0) {
        int ret = 0, d = (int) Math.floor(Math.log10(val));
        if (d + 1 == size) {
          int powVal = (int) Math.pow(10, d);
          ret = val / powVal;
          val -= powVal * ret;
        }
        --size;
        return ret;
      }
      throw new RuntimeException("empty queue");
    }
  }

Queue From Stacks
 public static class Queue<T> {
    private LinkedList<T> a = new LinkedList<T>();
    private LinkedList<T> b = new LinkedList<T>();

    public void enqueue(T x) {
      a.push(x);
    }

    public T dequeue() {
      if (b.isEmpty()) {
        while (!a.isEmpty()) {
          b.push(a.pop());
        }
      }
      if (!b.isEmpty()) {
        return b.pop();
      }
      throw new RuntimeException("empty queue");
    }
  }

Queue With Max Using Deque
  public static class Queue<T extends Comparable<T>> {
    private LinkedList<T> q = new LinkedList<T>();
    private LinkedList<T> d = new LinkedList<T>();

    public void enqueue(T x) {
      q.addFirst(x);
      while (!d.isEmpty() && d.getLast().compareTo(x) < 0) {
        d.removeLast();
      }
      d.addLast(x);
    }

    public T dequeue() {
      if (!q.isEmpty()) {
        T ret = q.removeLast();
        if (ret.equals(d.getFirst())) {
          d.removeFirst();
        }
        return ret;
      }
      throw new RuntimeException("empty queue");
    }
      public T max() {
      if (!d.isEmpty()) {
        return d.getFirst();
      }
      throw new RuntimeException("empty queue");
    }

Maximum of A Sliding Window - O(n)
  public static void trafficVolumes(List<TrafficElement> A, int w) {
    QueueWithMaxUsingDeque<TrafficElement> Q = new QueueWithMaxUsingDeque<TrafficElement>();
    for (int i = 0; i < A.size(); i++) {
      Q.enqueue(A.get(i));
      while (A.get(i).getTime() - Q.head().getTime() > w) {
        Q.dequeue();
      }
      System.out.println("Max after inserting " + i + " is "
          + Q.max().getVolume());
    }
  }