Programming Praxis

One Response to “Two Stacks”

1. Daniel said

   November 5, 2016 at 3:16 AM

   > “One common pattern uses two stacks of variable sizes…”

   What are some examples that use this pattern?

   Here’s a solution in Java.

   import java.util.Arrays;
   import java.util.EmptyStackException;
   
   public class DoubleStack<T> {
     T[] stack;
     int idx1;
     int idx2;
     
     @SuppressWarnings("unchecked")
     public DoubleStack(int size) {
       stack = (T[]) new Object[size];
       idx1 = -1;
       idx2 = size;
     }
     
     boolean push1(T object) {
       int nextIdx = idx1 + 1;
       if (nextIdx >= idx2 || nextIdx >= stack.length) return false;
       stack[++idx1] = object;
       return true;
     }
     
     T pop1() {
       if (idx1 < 0) throw new EmptyStackException();
       T popped = stack[idx1];
       stack[idx1--] = null; // prevent memory leak
       return popped;
     }
     
     boolean push2(T object) {
       int nextIdx = idx2 - 1;
       if (nextIdx <= idx1 || nextIdx < 0) return false;
       stack[--idx2] = object;
       return true;
     }
     
     T pop2() {
       if (idx2 >= stack.length) throw new EmptyStackException();
       T popped = stack[idx2];
       stack[idx2++] = null;
       return popped;
     }
     
     @Override
     public String toString() {
       return Arrays.toString(stack);
     }
     
     public static void main(String[] args) {
       System.out.println("init:");
       DoubleStack<Integer> doubleStack = new DoubleStack<>(5);
       System.out.println("  " + doubleStack);
       System.out.println();
       System.out.println("push 3 ints to stack 1:");
       for (int i = 0; i < 3; ++i) {
         doubleStack.push1(i); 
       }
       System.out.println("  " + doubleStack);
       System.out.println();
       System.out.println("push 5 ints to stack 2:");
       for (int i = 0; i < 5; ++i) {
         doubleStack.push2(i); 
       }
       System.out.println("  " + doubleStack);
       System.out.println("(some elements didn't fit)");
       System.out.println();
       
       System.out.println("pop 7 elements from stack 1:");
       for (int i = 0; i < 7; ++i) {
         try {
           int popped = doubleStack.pop1();
           System.out.println("popped: " + popped);
         } catch (EmptyStackException e) {
           System.out.println("couldn't pop anymore");
           break;
         }
       }
       System.out.println("  " + doubleStack);
       System.out.println();
       
       System.out.println("pop 1 element from stack 2:");
       int popped = doubleStack.pop2();
       System.out.println("popped: " + popped);
       System.out.println("  " + doubleStack);
       System.out.println();
     }
   }
   

   Output:

   init:
     [null, null, null, null, null]
   
   push 3 ints to stack 1:
     [0, 1, 2, null, null]
   
   push 5 ints to stack 2:
     [0, 1, 2, 1, 0]
   (some elements didn't fit)
   
   pop 7 elements from stack 1:
   popped: 2
   popped: 1
   popped: 0
   couldn't pop anymore
     [null, null, null, 1, 0]
   
   pop 1 element from stack 2:
   popped: 1
     [null, null, null, null, 0]