Two Stacks

November 4, 2016

We provide push and pop functions for each of two stacks, each with two pointers, lo and hi; when they are the same, the stack is empty. The memory arena is an array of size mem-size, so lo-one is zero and hi-two is mem-size. Here is our implementation:

(define mem-size 10) ; small for testing
(define arena (make-vector mem-size))

(define lo-one 0) (define hi-one 0)
(define lo-two (- mem-size 1)) (define hi-two (- mem-size 1))

(define (push-one x)
  (cond ((< lo-two hi-one) (error 'push-one "arena overflow"))
  (else (vector-set! arena hi-one x) (set! hi-one (+ hi-one 1)))))

(define (push-two x)
  (cond ((< lo-two hi-one) (error 'push-two "arena overflow"))
  (else (vector-set! arena lo-two x) (set! lo-two (- lo-two 1)))))

(define (pop-one)
  (cond ((= lo-one hi-one) (error 'pop-one "empty stack"))
  (else (set! hi-one (- hi-one 1)) (vector-ref arena hi-one))))

(define (pop-two)
  (cond ((= lo-two hi-two) (error 'pop-two "empty stack"))
  (else (set! lo-two (+ lo-two 1)) (vector-ref arena lo-two))))

Note that lo and hi refer to physical array addresses, not logical array addresses; thus, the logical top of stack one is hi-one and the logical top of staco two is lo-two (not hi-two, as you might expect). You can name things the other way around if you prefer. Here are some examples:

> (push-one 1)
> (push-one 2)
> (push-one 3)
> (push-one 4)
> (push-one 5)
> (push-one 6)
> (push-two #\a)
> (push-two #\b)
> (push-two #\c)
> (push-two #\d)
> (push-two #\e)
Error in push-two: arena overflow
> (pop-one)
6
> (pop-one)
5
> (pop-one)
4
> (pop-one)
3
> (pop-one)
2
> (pop-one)
1
> (pop-one)
Error in pop-one: empty stack
> (pop-two)
#\d
> (pop-two)
#\c
> (pop-two)
#\b
> (pop-two)
#\a
> (pop-two)
Error in pop-two: empty stack

You can run the program at http://ideone.com/4It6cB.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: