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