Two Stacks

November 4, 2016

Different programs manage memory in different ways. One common pattern uses two stacks of variable sizes; memory is arranged so that one stack starts at the bottom of memory and grows up, the other stack starts at the top of memory and grows down.

Your task is to write a program that simulates memory management in an array, using two stacks. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

One Response to “Two Stacks”

  1. Daniel said

    > “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]
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: