3.3 皿が積み上がっている状況をイメージしてください。もし、高く積み上がり過ぎたら倒れてしまうでしょう。ですから、実生活ではスタックがある領域を超えたとき、新しいスタックを用意することになるでしょう。これをまねたデータ構造SetOfStacksを実装してください。SetOfStacksはいくつかのスタックを持ち、スタックのデータが一杯になったらスタックを新たに作らなければなりません。また、SetOfStacks.push()とSetOfStacks.pop()は普通のスタックのように振る舞うようにしてください。(つまり、pop()は通常の1つのスタックの場合と同じ値を返さなければなりません)。

SetOfStacksTest.java

import java.util.*;
import org.junit.*;
import static org.junit.Assert.*;

public class SetOfStacksTest {
  @Test
  public void testSetOfStacks(){
    SetOfStacks set = new SetOfStacks();
    set.push(1);
    set.push(2);
    set.push(3);
    assertEquals(Integer.valueOf(3), set.pop());
  }

  @Test
  public void testSetOfStacks2(){
    SetOfStacks set = new SetOfStacks();
    set.push(1);
    set.push(2);
    set.push(3);
    set.push(4);
    assertEquals(Integer.valueOf(4), set.pop());
  }

  @Test
  public void testSetOfStacks3(){
    SetOfStacks set = new SetOfStacks();
    set.push(1);
    set.push(2);
    set.push(3);
    set.push(4);
    set.pop();
    set.pop();
    assertEquals(Integer.valueOf(2), set.pop());
  }
}

class SetOfStacks {
  public List<Stack> stacks;
  public Stack currentStack;
  public int stackIndex;

  class Stack {
    /*
      This stack is supposed to have only 3 nodes.
    */
    public static final int CAPACITY = 3;
    public Node head;
    public Node tail;

    public Stack(){
      this.head = new Node();
      this.tail = new Node();
      this.head.next = this.tail;
    }

    public void push(Integer v){
      Node node = new Node();
      node.value = v;
      Node tmp = this.head.next;
      this.head.next = node;
      node.next = tmp;
    }

    public Integer pop() throws Exception {
      if(this.head.next == this.tail){
        throw new Exception("No node to be popped!");
      }
      Node node = this.head.next;
      Node tmp = node.next;
      this.head.next = tmp;
      return node.value;
    }

    public boolean isFull(){
      if(this.length() > CAPACITY){
        return true;
      }
      return false;
    }

    public boolean isEmpty(){
      if(this.head.next == this.tail){
        return true;
      }
      return false;
    }

    public int length(){
      int count = 0;
      Node node = this.head;
      while(node.next != this.tail){
        node = node.next;
        count++;
      }
      return count;
    }
  }

  class Node{
    public Node next = null;
    public Integer value = null;
  }

  public SetOfStacks(){
    this.stacks = new ArrayList<>();
    this.currentStack = new Stack();
    stacks.add(currentStack);
    stackIndex = 0;
  }

  public void push(Integer v){
    if(currentStack.isFull()){
      Stack stack = new Stack();
      stacks.add(stack);
      currentStack = stack;
      stackIndex++;
    }
    currentStack.push(v);
  }

  public Integer pop(){
    Integer value;
    if(currentStack.isEmpty()){
      stackIndex--;
      currentStack = stacks.get(stackIndex);
    }
    try {
      value = currentStack.pop();
    } catch (Exception e){
      value = null;
    }
    return value;
  }
}