Java: Implement stack with one queue, any problems?

Question

So I tried to implement a stack with just one queue and it appears to work, but I'm not sure if there's something wrong with it since most of the solutions I've seen online use two queues. Can anyone tell if me if there are problems with my implementation?

public class MyStack<T> {

/**
 * @param args
 */
private Queue<T> q = new LinkedList<T>();
public MyStack(){
}
public static void main(String[] args) {
    // TODO Auto-generated method stub
    MyStack<String> s = new MyStack<String>();
    s.push("1");
    s.push("2");
    s.push("3");
    s.push("4");
    System.out.println(s.pop());
    System.out.println(s.pop());
    System.out.println(s.pop());
    System.out.println(s.pop());
    System.out.println(s.pop());
}

public void push(T s){
    q.offer(s);         
}

public T pop(){
    int n = q.size();
    for(int i = 0; i < n-1; i++){
        q.offer(q.poll());              
    }
    return q.poll();
}
}

Output:
4
3
2
1
null

if you want code review this is not the site, do you have an unexpected behaviour? — nachokk, Aug 04 '13 at 21:19
No unexpected behaviours. I'm just wondering why most online solutions use two queues when one seems to work just fine. — user2017502, Aug 04 '13 at 21:22
Never seen a stack implemented with 2 queues, what are those solutions you've seen do with them? Also, why `Queue` since that is FIFO and Stack is LIFO. — zapl, Aug 04 '13 at 21:28
The two queue implementation I found was here: http://stackoverflow.com/questions/688276/implement-stack-using-two-queues — user2017502, Aug 04 '13 at 21:33
I was asked to do this during an interview. I didn't come up with this scenario... — user2017502, Aug 04 '13 at 21:41
Oh ok, interview question specifically demands `Queue` then I guess. Answer you linked perform better but that's it. It makes no sense to implement a stack that way in practice since at least one operation has to iterate needlessly. A simple implementation like http://ideone.com/bS3LD1 that uses a LIFO structure internally does not have that problem. — zapl, Aug 04 '13 at 21:57

OldCurmudgeon · Answer 1 · 2013-08-04T22:54:21.623

1

You should use either a Stack or a Deque or even a LinkedList.

Implementing your own is just ... pointless. Unless of course (as @bas suggests) you are doing a course on data structures in which case you should go Commando and implement your own structure from scratch. Using another structure because it is nearly like the one you are trying to make is like using a hammer with screws.

If you really need to implement something yourself something like this should work:

public class Stack<T> {
  private Entry top = null;

  private class Entry {
    final Entry up;
    final T it;

    public Entry(Entry up, T it) {
      this.up = up;
      this.it = it;
    }
  }

  public void push ( T it ) {
    top = new Entry(top, it);
  }

  public T pop () {
    if ( top == null ) {
      throw new EmptyStackException();
    }
    T it = top.it;
    top = top.up;
    return it;
  }
}

NB: This may not be thread safe.

edited Aug 04 '13 at 22:54

answered Aug 04 '13 at 21:23

OldCurmudgeon

64,482
16
119
213

not if you are doing a course on data structures in Java. I never considered it a bad thing to know how these structures work and how you can implement them efficiently. – bas Aug 04 '13 at 21:24
Thanks, I didn't know Deque existed. But anyway, I'm just trying to do this since I was asked during an interview. If I was doing it on my own I would just use Java's own implementation rather than trying to reinvent the wheel. – user2017502 Aug 04 '13 at 21:45
@user2017502 - I've added one simple possibility. – OldCurmudgeon Aug 04 '13 at 23:00

score 1 · Answer 2 · answered Aug 04 '13 at 21:28

1

Your solution is inefficient because you have to loop through the whole stack every time you pop something from it. (Effectively you have to traverse the whole linked list, before removing the element that was at the end.) Edit: Java's linked list is doubly linked anyway, so this is entirely pointless.

answered Aug 04 '13 at 21:28

user234461

1,133
12
29

If all you had was the basic queue. How would you implement it more efficiently? – user2017502 Aug 04 '13 at 21:37

score 0 · Answer 3 · answered Aug 04 '13 at 21:23

There is absolutely no reason a stack should use two queues. As a matter of fact, it only needs to keep track of one top-node that references the nodes below it.

The code seems to work, but as nachokk said, this is not the site for code review. This site is ment if you run into errors and require assistance.

score 0 · Answer 4 · answered Aug 04 '13 at 22:01

0

You must use two queues ONLY when you have basic queues operations, like enqueue and dequeue. When you can use other methods, especially iterating over queue, you can do it with only one queue, like you did.

answered Aug 04 '13 at 22:01

MGorgon

2,547
23
41

Java: Implement stack with one queue, any problems?

4 Answers4