미국유학/CS 545 Data Structure and Algorithm
QueueWithTwoStacks
kwohyuno
2025. 2. 9. 12:49
package queue;
import stack.ArrayStack;
import stack.Stack;
/** The class that implements the functionality of the queue
* (enqueue, dequeue, empty) with two stacks.
*/
public class QueueWithTwoStacks {
private Stack s1 = new ArrayStack();
private Stack s2 = new ArrayStack();
// You may NOT use any other memory, no array and no linked list,
// only the two stacks, s1, s2. You may call methods push, pop, empty() on s1, s2
/** Adds an element to the queue
* @param elem Element to add to the queue
*/
public void enqueue(int elem) {
// FILL IN CODE:
s1.push(elem);
}
/**
* Removes the element from the queue
* @return the element in front of the queue that was removed
*/
public Object dequeue() {
// FILL IN CODE
if(!s1.empty()){
while(!s1.empty()){
Object tmp = s1.pop();
s2.push(tmp);
}
Object val = s2.pop();
while(!s2.empty()){
s1.push(s2.pop());
}
return val;
}else{
System.out.println("Queue is empty");
return null;
}
}
/**
* Check if the queue is empty
* @return True if the queue is empty, and false otherwise.
*/
public boolean isEmpty() {
// FILL IN CODE
if(s1.empty()) return true;
else return false;
}
}