## 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]
```