Implement Stack using 2 Queues help!!

March 11, 2011 at 13:22:41
Specs: Windows 7 Ultimate, i7-930/4GB
hello guys, I'm new to Java programming and i'm stuck on this project when I tried to implement the Stack using 2 Queues. Ok, So I implemented the Queue class using LinkedList, where when you called:
enqueue(int x): add at the end of list
dequeue(): remove the head element
front(): retrieve the head element, no remove.
isEmpty(): see if the Queue is empty.
Now I used this class to implement the Stack: this is my program:
public class QueuedStack {
private int topValue;
private Queue Queue1;
private Queue Queue2;

/**
* Creates new QueuedStack
*/
public QueuedStack() {
Queue1 = new Queue();
Queue2 = new Queue();
}

/**
* Test if the Stack is empty
* @return true if the Stack is empty
*/
public boolean isEmpty() {
return Queue1.isEmpty() && Queue2.isEmpty();
}

/**
* Removes the last inserted integer
*/
public void pop() {
if (isEmpty())
throw new NoSuchElementException();
else {
if (!Queue1.isEmpty()) {
Queue1.dequeue();
}
else if (!Queue2.isEmpty()) {
Queue2.dequeue();
}
}
}

/**
* Inserts a new integer
* @param x the integer to be added
*/
public void push(int x) {
if (isEmpty())
Queue1.enqueue(x);
else {
if (!Queue1.isEmpty() && Queue2.isEmpty()) {
while (!Queue1.isEmpty()) {
Queue2.enqueue(x);
Queue2.enqueue(Queue1.front());
Queue1.dequeue();
}
}
else if (!Queue2.isEmpty() && Queue1.isEmpty()) {
while (!Queue2.isEmpty()) {
Queue1.enqueue(x);
Queue1.enqueue(Queue1.front());
Queue2.dequeue();
}
}
}
}

/**
* Gets the last inserted integer
* @return the last integer
*/
public int top() {
int returnValue = 0;
if (isEmpty())
throw new NoSuchElementException();
if (!Queue1.isEmpty())
returnValue = Queue1.front();
else if (!Queue2.isEmpty())
returnValue = Queue2.front();
return returnValue;
}
}

So now I want to test it by first create a new QueuedStack object, then start pushing 10 integers. It prints out the top item fine. Then I start popping out 5 items. But it keeps saying the top item is 10. It either not popping or the printout is wrong. When I read my codes, I could'nt tell where I weng wrong? Please point out where i'm doing wrong. Thanks for your help.


See More: Implement Stack using 2 Queues help!!

Report •

#1
March 11, 2011 at 20:33:23
I'm not a Java man, but there doesn't seem to be nearly enough logic there. It appears you have two queues, but you're not sure what to do with them. Let me ask you this: What is the fundamental difference between a stack and a queue?

How To Ask Questions The Smart Way


Report •

#2
March 12, 2011 at 00:38:11
Stack is Last-In-First-Out. So when you want to return the top item, you return the last inserted item.
Queue is First-In-First-Out. The front() will return the first inserted item.
So to use the Queues to implement the Stack. I have 2 Queues, each time I add a new integer, I added into an empty Queue, then add the front() of the other Queue; dequeue it, then add again until that Queue is empty. This way, the last inserted integer is always at the front.

Report •

#3
March 13, 2011 at 07:13:33
while (!Queue1.isEmpty()) {
Queue2.enqueue(x);
Queue2.enqueue(Queue1.front());
Queue1.dequeue();
}

And what does this do?

How To Ask Questions The Smart Way


Report •
Related Solutions


Ask Question