Skip to content

Instantly share code, notes, and snippets.

@flexelem
Last active February 20, 2020 01:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save flexelem/401ecdf250551d5c45fc to your computer and use it in GitHub Desktop.
Save flexelem/401ecdf250551d5c45fc to your computer and use it in GitHub Desktop.
Two stacks in one array
import java.util.NoSuchElementException;
/**
* CLRS - Introduction to Algorithms Ex.10.1-2
* Explain how to implement two stacks in one array A[1..n] in such a way that
* neither stack overflows unless the total number of elements in both stacks together is n.
* The PUSH and POP operations should run in O(1) time.
*
* There are two stacks in one array which the first one grows upwards ( A[1..N] ),
* and the second one grows downwards ( A[N..1] ).
*
* @author buraktas
*
*/
public class DoubleStack {
private int[] stack;
private int sTopLeft;
private int sTopRight;
public DoubleStack(int capacity) {
this.stack = new int[capacity];
this.sTopLeft = 0;
this.sTopRight = stack.length - 1;
}
public void push(int item, int choice) {
if (sTopLeft > sTopRight) {
throw new IllegalStateException("Both stacks are full");
} else if (choice == 0) { // add to the left stack
stack[sTopLeft++] = item;
} else { // add to the right stack
stack[sTopRight--] = item;
}
}
public int pop(int choice) {
int temp = peek(choice);
if (choice == 0) {
sTopLeft--;
} else {
sTopRight++;
}
return temp;
}
public int peek(int choice) {
if (sTopLeft == 0 && choice == 0) { // if choice is 0 then check emptiness of left stack
throw new NoSuchElementException("Left stack is empty");
} else if (sTopRight == stack.length - 1 && choice == 1) { // if choice is 1 then check emptiness of right stack
throw new NoSuchElementException("Right stack is empty");
}
if (choice == 0) {
return stack[sTopLeft - 1];
} else {
return stack[sTopRight + 1];
}
}
public int size(int choice) {
if (choice == 0) {
return sTopLeft;
} else {
return stack.length - sTopRight;
}
}
public boolean isEmpty(int choice) {
if (choice == 0) {
return sTopLeft == 0;
} else {
return sTopRight == stack.length - 1;
}
}
}
import static org.junit.Assert.assertEquals;
import java.util.NoSuchElementException;
import org.junit.Before;
import org.junit.Test;
public class DoubleStackTest {
private DoubleStack stack;
private final static int CAPACITY = 10;
@Before
public void setUp() {
stack = new DoubleStack(CAPACITY);
}
@Test(expected = NoSuchElementException.class)
public void popFromEmptyLeftStack() {
stack.pop(0);
}
@Test(expected = NoSuchElementException.class)
public void popFromEmptyRightStack() {
stack.pop(1);
}
@Test(expected = IllegalStateException.class)
public void leftStackOverflow() {
for (int i = 0; i <= CAPACITY; i++) {
stack.push(i, 0);
}
}
@Test(expected = IllegalStateException.class)
public void rightStackOverflow() {
for (int i = 0; i <= CAPACITY; i++) {
stack.push(i, 1);
}
}
@Test(expected = IllegalStateException.class)
public void pushToBothStacksAndBlowThem() {
stack.push(1, 0);
stack.push(2, 0);
stack.push(3, 0);
stack.push(12, 0);
stack.push(15, 0);
stack.push(17, 0);
stack.push(4, 1);
stack.push(5, 1);
stack.push(6, 1);
stack.push(7, 1);
stack.push(8, 1);
}
@Test
public void testName() throws Exception {
stack.push(1, 0);
stack.push(2, 0);
stack.push(3, 0);
stack.push(4, 1);
stack.push(5, 1);
stack.push(6, 1);
assertEquals(3, stack.pop(0));
assertEquals(6, stack.pop(1));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment