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

Posted by programmingpraxis
Filed in Exercises
1 Comment »

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]

Leave a comment