#Why doesn't my method for reversing a stack using a queue work?

86 messages · Page 1 of 1 (latest)

grave lantern
#

My idea (which theoretically should work is:

  1. Pop the stack into the queue (this will lead to queue)
    2.Push the queue back into the stack after the stack is empty

with the LIFO nature of the stack and FIFO nature of the queue this should work. But I'm having issues with the implementation.

The error given is that my queue is full on line 19 (when it's attempting to enqueue), however I have set the capacity as the same size of the stack that I'm trying to reverse so I don't see where the issue lies, the loop should stop when the stack is empty, and therefore there's no real reason for this to not work as far as I can see.

The implementation of stack/queue is done from a template so that cannot be the issue.

I am just looking for tips, if it's possible and not a full solution.

image.png
dense spruceBOT
#

⌛ This post has been reserved for your question.

Hey @grave lantern! Please use /close or the Close Post button above when your problem is solved. Please remember to follow the help guidelines. This post will be automatically closed after 300 minutes of inactivity.

TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.

hallow beacon
#

Can you show the error?

#

Are you using raw types?

grave lantern
#

it's not an error it's a waraning for not parameterizing a generic type

#

but I figured out that the error is with the size

#

of my queue

#

if i set the size to 10 it works

hallow beacon
grave lantern
hallow beacon
grave lantern
#

since I don't think it is necessary for it to work

hallow beacon
grave lantern
#

the queue is full

#

when i try to enqueue

#

because i put the capacity of the queue the same as the size of the stack

#

but I think that breaks down when I pop

#

but idk tbh

#

cause I set the capacity before the while loop

hallow beacon
#

Can you show your implementation?

grave lantern
#

it's in the post

hallow beacon
#

I meant the Qzeue and Stack classes

#

Did you create them?

grave lantern
#

yea, i took that off of a template

#

so it should work

#

either way, it's not the issue

#

but what specifically did u want to see from it

hallow beacon
#

How they work

#

maybe there's some weirdness with it

#

you could also use classes from Java's collection API

#

then you'd be sure it works

grave lantern
# 
 * Queue implementation with an array.
 */
public class Queue implements QueueADT {
    private int f; // front of queue
    private int r; // rear of queue
    private int capacity;
    private Object[] Q;
    private static int MAX = 100; 

    public Queue(int capacity){
       this.capacity = capacity;
       Q =  new Object[capacity];
       f = 0;
       r = 0;
    } 

    public Queue(){
       this(MAX);
    }

    public int size(){
        return (Q.length - f + r) % capacity;
    }
    public boolean isEmpty(){
        return (f==r);
    }

    public Object front() throws QueueException {
        if (isEmpty())
           throw new QueueException("Queue is empty.");
        return Q[f];
     }

    public Object dequeue() throws QueueException {
        if (isEmpty())
          throw new QueueException("Queue is empty.");
        Object tmp = Q[f];
        Q[f] = null;
        f = (f+1) % capacity;
        return tmp;
    }
    
    public void enqueue(Object e) throws QueueException {
        if (size() == Q.length - 1)
          throw new QueueException("Queue is full.");
        Q[r] = e;
        r = (r+1) % Q.length;
    }

    public String toString(){
        StringBuffer buf = new StringBuffer("[");
        if(size() > 0)
            buf.append(Q[f]);
        for(int i = 1; i < size();i++){
            buf.append(", " + Q[f + i % capacity]);
        }
        buf.append("]");
        return buf.toString();
    }
}
#

didnt know how to ss it

#

this is the queue

#

hm

#

my stack doesn't seem to want to send

#

well the issue will be with the size I suppose

#

but the size is added after each push, starting at 0 (for the stack)

#

and the test pushes 3 times

#

then checks if each pop is the reverse order

#

so the stack that is put into the method has (A,B,C) then it pops to see if the result of each pop is (C,B,A) consecurively

#

I'm just unsure of why the size doesn't work as I'd think it does

hallow beacon
#

what if you use st.size()+1 in the Queue constructor?

grave lantern
#

I'll try that

#

huh

#

that seems to work haha

#

still I'd wish to know why

#

perhaps the size starts at 1?

#

either way, thank you

dense spruceBOT
# grave lantern either way, thank you

If you are finished with your post, please close it.
If you are not, please ignore this message.
Note that you will not be able to send further messages here after this post have been closed but you will be able to create new posts.

grave lantern
#

I'll see if I can figure out why it does this

hallow beacon
#

it's because of the Queue implementation

#

I think

#

it doesn't make use of the whole array

grave lantern
#

how do you mean exactly?

hallow beacon
#

check the enqueue method

#

if(size() == Q.length-1)

grave lantern
#

ah yes I see

#

so it has to have a capacity of one more than needed?

hallow beacon
#

yes

grave lantern
#

is that needed for some reason?

#

or is it just a quirk by whoever wrote it

hallow beacon
#

with your implementation yes

hallow beacon
#

because if it would be full, I think f and r would be the same

#

hence it would think it's empty

grave lantern
#

ah yes I see

#

thanks very much

hallow beacon
#

but you can also use JDK classes

grave lantern
#

for the queue?

#

I might look into that

hallow beacon
#

Java provides an interface Queue and multiple implementations of it

#

e.g. LinkedList

#

or ArrayDeque

grave lantern
#

right, I suppose that would make less issues

#

I'll close the thread now, but thank you for explaining everything

dense spruceBOT
hallow beacon
#

With Java 21, Deque even allows reversing

#

out of the box

grave lantern
hallow beacon
#

or actually getting a reversed view

grave lantern
#

but that is good to know

#

but yeah, ty