3.3 Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structureSetOf Stacks that mimics this. SetOf Stacks should be composed of several stacks and should create a new stack once the previou…

3.3 setOfStacks

import java.util.ArrayList;

class Node {
    int val;
    Node pre;
    Node next;
    
    Node(int val) {
        this.val = val;
        pre = null;
        next = null;
    }
}

class Stack {
    int size;
    Node head;
    Node tail;

    Stack() {
        size = 0;
        head = new Node(0);
        tail = new Node(0);
        head.next = tail;
        // Link tail.pre to head.
        tail.pre = head;
    }
    
    void push(int val) {
        Node node = new Node(val);
        tail.pre.next = node;
        node.pre = tail.pre;
        node.next = tail;
        tail.pre = node;
        // Increase size.
        size++;
    }
    
    int pop() {
        Node peek = tail.pre;
        peek.pre.next = tail;
        tail.pre = peek.pre;
        // Decrease size.
        size--;
        return peek.val;
    }
    
    int popFirst() {
        Node first = head.next;
        first.next.pre = head;
        head.next = first.next;
        size--;
        return first.val;
    }
}

public class SetOfStacks {
    private ArrayList<Stack> setOfStacks;
    private int capacity;
    
    public SetOfStacks(int capacity) {
        this.capacity = capacity;
        setOfStacks = new ArrayList<Stack>();
    }
    
    public int size() {
        int size = 0;
        for (int i = 0; i < setOfStacks.size(); i++) {
            size += setOfStacks.get(i).size;
        }
        return size;
    }
    
    public boolean empty() {
        return setOfStacks.isEmpty();
    }
    
    public void push(int val) {
        // Consider empty()
        if (empty() || setOfStacks.get(setOfStacks.size() - 1).size == capacity) {
            Stack stack = new Stack();
            setOfStacks.add(stack);
        }
        
        setOfStacks.get(setOfStacks.size() - 1).push(val);
    }
    
    public int pop() throws Exception {
        if (empty()) {
            throw new Exception("Stack is empty.");
        }
        
        return popAt(setOfStacks.size() - 1);
    }
    
    public int popAt(int index) throws Exception {
        if (index < 0 || index >= setOfStacks.size()) {
            throw new Exception("Index is not valid.");
        }
        
        Stack stack = setOfStacks.get(index);
        int val = stack.pop();
        
        int last = setOfStacks.size() - 1;
        for (int i = index; i < last; i++) {
            int first = setOfStacks.get(i + 1).popFirst();
            setOfStacks.get(i).push(first);
        }
        
        if (setOfStacks.get(last).size == 0) {
            setOfStacks.remove(last);
        }
        
        return val;
    }
    
    public static void main(String[] args) throws Exception {
        SetOfStacks set = new SetOfStacks(5);
        for (int i = 0; i < 34; i++) {
            set.push(i);
        }
        for (int i = 0; i < 34; i++) {
            System.out.println("Popped " + set.pop());
        }        
    }
}