Created
June 28, 2014 08:56
-
-
Save chouclee/9fb80a96222d8b8f9d53 to your computer and use it in GitHub Desktop.
[CC150][3.5] Implement a MyQueue class which implements a queue 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.Stack; | |
public class MyQueue<T> { | |
private Stack<T> pushStack; | |
private Stack<T> popStack; | |
public MyQueue() { | |
pushStack = new Stack<T>(); | |
popStack = new Stack<T>(); | |
} | |
public void enqueue(T item) { // push element into pushStack | |
pushStack.push(item); // push() : O(1) | |
} | |
public T dequeue() { // if popStack is not empty, pop() from popStack | |
if (popStack.isEmpty()) { // else, push all elements in pushStack into popStack, then pop one item | |
if (pushStack.isEmpty()) // pop() : average O(1) | |
return null; | |
else { | |
while (!pushStack.isEmpty()) | |
popStack.add(pushStack.pop()); | |
} | |
} | |
return popStack.pop(); | |
} | |
public static void main(String[] args) { | |
// TODO Auto-generated method stub | |
MyQueue<Integer> test = new MyQueue<Integer>(); | |
for (int i = 0; i < 10; i++) | |
test.enqueue(i); | |
for (int i = 0; i < 5; i++) | |
System.out.println(test.dequeue()); | |
for (int i = 10; i < 15; i++) | |
test.enqueue(i); | |
for (int i = 0; i < 10; i++) | |
System.out.println(test.dequeue()); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment