Skip to content

Instantly share code, notes, and snippets.

@flexelem
Created May 4, 2014 20:54
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/4a6d31420e38d7d44a7b to your computer and use it in GitHub Desktop.
Save flexelem/4a6d31420e38d7d44a7b to your computer and use it in GitHub Desktop.
Queue implementation with using two stacks
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();
}
}
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