Last active
February 20, 2020 01:07
-
-
Save flexelem/401ecdf250551d5c45fc to your computer and use it in GitHub Desktop.
Two stacks in one array
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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