-1
\$\begingroup\$

I have implemented the Stack using two Queues q1 and q2 respectively as shown below in the code. I would like to get you reviews on whether it's an efficient way of implementing it or now.

For Pop operation : I will keep on removing elements from the Queue q1 and adding it to Queue 2 until only one element remains in Queue q1, then I will be removing that particular element from the Queue q1 to accomplish the Stack Pop operation

For Push Operation:

It's simple, I am just checking if Queue q1 is empty then I will start adding the elements in Queue q2 otherwise in queue q1.

import java.util.LinkedList;
import java.util.Queue;

public class StackUsingQueues {

    Queue<Integer> q1 = new LinkedList<>();
    Queue<Integer> q2 = new LinkedList<>();

    public  void push(int data){

        if(q1.isEmpty()){
            q2.add(data);
        }
        else{

            q1.add(data);
        }



    }

    public int pop(){
        int x;
        if(q1.isEmpty()){
                    if(q2.isEmpty()){

                        System.out.println("Stack Underflow");
                        System.exit(0);

                    } else {
                            /* I will keep on removing elements from the Queue q1 and adding
                               it to Queue 2 until only one element remains in Queue q1, then 
                               I will be removing that particular element from the Queue q1 to
                                accomplish the Stack Pop operation */ 

                                    while(q1.size()!=1){

                                    x = q1.remove();
                                    q2.add(x);

                                    }
                                 return q1.remove();
                          }}
                        else {

                                while(q2.size()!=1){

                                    x = q2.remove();
                                    q1.add(x);

                                    }
                                    return q2.remove();


                            }

        return 0;

        }



    public static void main(String[] args) {


        StackUsingQueues st = new StackUsingQueues();

        st.push(1);
        st.push(2);





    }

}
\$\endgroup\$
  • \$\begingroup\$ This isn't going to work. In pop, if q1 is empty and q2 is not, you start removing elements of q1 anyway. Even if that didn't cause an exception, it would be an infinite loop. \$\endgroup\$ – sqykly Oct 10 '15 at 15:38
  • \$\begingroup\$ Also formatting has messed up your indents. \$\endgroup\$ – sqykly Oct 10 '15 at 15:40
  • \$\begingroup\$ What is the purpose of this code? Is it an academic exercise? Because this is a terrible way to implement a stack. \$\endgroup\$ – JS1 Oct 11 '15 at 5:06
  • \$\begingroup\$ No academic exercise. I was implementing it on my own for my learning purpose. \$\endgroup\$ – John Oct 11 '15 at 5:07
  • \$\begingroup\$ @holroy can you implement stack using one queue? \$\endgroup\$ – John Oct 11 '15 at 10:45
5
\$\begingroup\$

Broken

Your implementation doesn't actually work. (The question should have been closed, but it already has an answer, so... too late.)

  1. The two st.push calls will append to q2
  2. If you call pop after that, the algorithm tries to remove elements from q1 until its size becomes 1, but its size is 0 now, to that will throw a NoSuchElementException

=> You cannot pop from this stack, it's broken

Missing methods

A sorely missing method is isEmpty (or empty). Without such method, there's no really easy way to explore the elements of a stack. Basically keep popping until the program crashes? Not very ergonomic.

Avoid System.exit

System.exit doesn't belong in the middle of an algorithm. In fact it's best to avoid it altogether. It's extremely rare when using this is the right way to go in Java.

Popping an empty stack

Java has an exception dedicated to popping an empty stack, called EmptyStackException. How could you know that? When reinventing the wheel, it's good to look at the SDK (Stack in particular, in this case), to learn from what exists.

Implementation

Suggested implementation, using your algorithm idea:

import java.util.EmptyStackException;
import java.util.LinkedList;
import java.util.Queue;

public class StackUsingQueues<T> {

    private Queue<T> q1 = new LinkedList<>();
    private Queue<T> q2 = new LinkedList<>();

    public void push(T data) {
        q1.add(data);
    }

    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        while (q1.size() > 1) {
            q2.add(q1.poll());
        }
        T top = q1.poll();
        Queue<T> temp = q1;
        q1 = q2;
        q2 = temp;
        return top;
    }

    public boolean isEmpty() {
        return q1.isEmpty();
    }
}

Note that this algorithm is fast for pushes but slow for pops. The opposite is also possible: fast for pops but slow for pushes. For that alternative approach, see this answer on Stack Overflow.

\$\endgroup\$
  • \$\begingroup\$ My bad. I'll try to remember to partially answer a broken question in a comment instead. Also, +1, better review. \$\endgroup\$ – sqykly Oct 12 '15 at 5:53
1
\$\begingroup\$

No, this is not efficient, if indeed it can be made to work. The pop operation has a loop that can iterate over N - 1 elements of an N deep stack. Typically both push and pop are expected to be constant time, as they are in the standard Stack implementation. An additional disadvantage to this implementation is that it can only hold int.

\$\endgroup\$
  • \$\begingroup\$ So I can use <T> instead of <Integer>, right? \$\endgroup\$ – John Oct 10 '15 at 18:49
  • \$\begingroup\$ For the record, I don't think that push and pop can be efficient at the same time when using queues to implement. You have to pick one of them. I think the question is from a programming exercise, not a serious approach to implementing a stack. \$\endgroup\$ – janos Oct 12 '15 at 5:58
  • \$\begingroup\$ @john your class would have a type parameter itself which it would use as a type argument to the queue; as of now, changing the queues to <T> will be an error since T is undefined. \$\endgroup\$ – sqykly Oct 12 '15 at 5:59
  • \$\begingroup\$ @janos right, just wanted to make sure someone answered OP's "is this an efficient implementation" before the question got closed - which apparently ironically prevented that from happening anyway =/. \$\endgroup\$ – sqykly Oct 12 '15 at 6:07
  • \$\begingroup\$ It didn't prevent, questions with answers can be closed. I answered anyway because I was more than halfway through my review... \$\endgroup\$ – janos Oct 12 '15 at 7:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.