Skip to content

Instantly share code, notes, and snippets.

@flexelem
Created May 4, 2014 22:34
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/ed7365a664840c1a8cbe to your computer and use it in GitHub Desktop.
Save flexelem/ed7365a664840c1a8cbe to your computer and use it in GitHub Desktop.
Implement a stack using two queues
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();
}
}
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