Created
May 4, 2014 22:34
-
-
Save flexelem/ed7365a664840c1a8cbe to your computer and use it in GitHub Desktop.
Implement a stack using two queues
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.LinkedList; | |
import java.util.NoSuchElementException; | |
import java.util.Queue; | |
/** | |
* Show how to implement a stack using two queues. Analyze the running time of the queue operations. | |
* | |
*/ | |
public class StackWithTwoQueue { | |
private Queue<Integer> queue1; | |
private Queue<Integer> queue2; | |
public StackWithTwoQueue() { | |
this.queue1 = new LinkedList<Integer>(); | |
this.queue2 = new LinkedList<Integer>(); | |
} | |
public void push(int item) { | |
if (queue1.isEmpty()) { | |
queue1.add(item); | |
while (!queue2.isEmpty()) { | |
queue1.add(queue2.remove()); | |
} | |
} else { | |
queue2.add(item); | |
while (!queue1.isEmpty()) { | |
queue2.add(queue1.remove()); | |
} | |
} | |
} | |
public int pop() { | |
if (queue1.isEmpty() && queue2.isEmpty()) { | |
throw new NoSuchElementException("Stack is empty"); | |
} | |
if (!queue1.isEmpty()) { | |
return queue1.remove(); | |
} else { | |
return queue2.remove(); | |
} | |
} | |
public int size() { | |
return queue1.size() + queue2.size(); | |
} | |
public boolean isEmpty() { | |
return queue1.isEmpty() && queue2.isEmpty(); | |
} | |
} |
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 static org.junit.Assert.assertFalse; | |
import static org.junit.Assert.assertTrue; | |
import java.util.NoSuchElementException; | |
import org.junit.Before; | |
import org.junit.Test; | |
public class StackWithTwoQueueTest { | |
private StackWithTwoQueue stack; | |
@Before | |
public void setUp() { | |
stack = new StackWithTwoQueue(); | |
} | |
@Test(expected = NoSuchElementException.class) | |
public void popFromEmptyStack() { | |
stack.pop(); | |
} | |
@Test | |
public void testName() { | |
for (int i = 0; i < 10; i++) { | |
stack.push(i); | |
} | |
int counter = 9; | |
while (!stack.isEmpty()) { | |
assertEquals(counter, stack.pop()); | |
counter--; | |
} | |
} | |
@Test | |
public void testIsNotEmpty() { | |
stack.push(1); | |
assertFalse(stack.isEmpty()); | |
} | |
@Test | |
public void testIsEmpty() { | |
assertTrue(stack.isEmpty()); | |
} | |
@Test | |
public void testSize() { | |
for (int i = 0; i < 10; i++) { | |
stack.push(i); | |
} | |
assertEquals(10, stack.size()); | |
stack.pop(); | |
stack.pop(); | |
stack.pop(); | |
assertEquals(7, stack.size()); | |
stack.push(1); | |
assertEquals(8, stack.size()); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment