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.
> “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: