Created
May 4, 2014 20:54
-
-
Save flexelem/4a6d31420e38d7d44a7b to your computer and use it in GitHub Desktop.
Queue implementation with using two stacks
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; | |
import java.util.Stack; | |
/** | |
* CLRS - Introduction to Algorithms Ex.10.1-6 | |
* | |
* Show how to implement a queue using two stacks. Analyze the running time of the queue operations | |
* | |
* */ | |
public class QueueWithTwoStack { | |
private Stack<Integer> enqueueStack; | |
private Stack<Integer> dequeueStack; | |
public QueueWithTwoStack() { | |
this.enqueueStack = new Stack<Integer>(); | |
this.dequeueStack = new Stack<Integer>(); | |
} | |
public void enqueue(int item) { | |
enqueueStack.push(item); | |
} | |
public int dequeue() { | |
// right stack is not empty then return the next element | |
if (!dequeueStack.isEmpty()) { | |
return dequeueStack.pop(); | |
} | |
// if right stack is empty then transfer all elements from | |
// the left stack to the right stack. This will take O(n) time. | |
if (!enqueueStack.isEmpty()) { | |
while (!enqueueStack.isEmpty()) { | |
dequeueStack.push(enqueueStack.pop()); | |
} | |
return dequeueStack.pop(); | |
} | |
// if both of stacks are empty means that our queue is empty | |
throw new NoSuchElementException("Queue is empty"); | |
} | |
public int size() { | |
return enqueueStack.size() + dequeueStack.size(); | |
} | |
public boolean isEmpty() { | |
return enqueueStack.isEmpty() && dequeueStack.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 QueueWithTwoStackTest { | |
private QueueWithTwoStack queue; | |
@Before | |
public void setUp() { | |
queue = new QueueWithTwoStack(); | |
} | |
@Test(expected = NoSuchElementException.class) | |
public void dequeueFromEmptyQueue() { | |
queue.dequeue(); | |
} | |
@Test | |
public void sizeTest() { | |
for (int i = 0; i < 10; i++) { | |
queue.enqueue(i); | |
} | |
assertEquals(10, queue.size()); | |
queue.dequeue(); | |
queue.dequeue(); | |
queue.dequeue(); | |
queue.enqueue(1); | |
assertEquals(8, queue.size()); | |
} | |
@Test | |
public void testEnqueueAndDequeue() { | |
for (int i = 0; i < 10; i++) { | |
queue.enqueue(i); | |
} | |
int counter = 0; | |
while (!queue.isEmpty()) { | |
assertEquals(counter, queue.dequeue()); | |
counter++; | |
} | |
} | |
@Test | |
public void testIsEmpty() { | |
assertTrue(queue.isEmpty()); | |
} | |
@Test | |
public void testNotEmpty() { | |
queue.enqueue(5); | |
assertFalse(queue.isEmpty()); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment