O(1) purely with queues


  • 31

    Note that I truly only use the allowed queue operations. While I use LinkedList, I'm not using it as such. I only use it because in Java, Queue is only an interface and there is no class Queue (see All Known Implementing Classes).

    What I do is I that I simulate a linked list stack purely with queues. Each queue only has two elements: an integer at the front and another queue at the back (that's where the remaining integers/queues live).

    Yes, I know this is silly :-)
    Then again, forbidding to use stacks/vectors/etc is silly to begin with. Also, it's not actually silly if you consider that it's O(1) and thus much better than the usual O(n) solutions (and btw I did also write some of those).

    class MyStack {
    
        private Queue queue;
    
        public void push(int x) {
            Queue q = new LinkedList();     // could be any queue type, see note above
            q.add(x);
            q.add(queue);
            queue = q;
        }
    
        public void pop() {
            queue.remove();
            queue = (Queue) queue.peek();
        }
    
        public int top() {
            return (int) queue.peek();
        }
    
        public boolean empty() {
            return queue == null;
        }
    }

  • 0
    R

    First, yes, good solution.
    But
    queue = (Queue) queue.peek();
    this casting is not good


  • 1
    C

    q.add(queue); is this an O(1) operation? If I have to push many values a a same time, it is not efficient.


  • 1
    R

    and, each time you push new element, you create a new object


  • 0
    R

    i assume that, you mean the size of 'queue' in q.add(queue) is big ?


  • 0

    @CodingKing Yes, that's O(1). I'm only pushing a single object there, namely the queue object.


  • 0

    Why is that casting not good? How else would I do it?

    And yes, I'm of course aware that I'm creating new objects. Is that a problem? Btw, I think due to autoboxing, pushing just ints onto a queue also creates objects. Integer objects, that is. So whether I create two objects or only one... meh, I don't care. Like I said, this is a silly problem to begin with.


  • 0
    Z

    the solution is good, but it just implement a linkedlist and make it act as a stack. each queue the first element is value and the second element is pointer.


  • 0

    @zsc347 Um... yeah... I said that myself in the description already.


  • 0
    C

    I'm wrong. It only adds a reference of the new object. This solution is brilliant.


  • 0
    K

    using LinkedList like this, it is effectively a stack


  • 0
    Z

    Good solution indeed. The problem lies in the question itself, which use a seemingly "smart" way only to make things worse. I think a good problem is supposed to teach us to make things nice and easy.


  • 0
    X

    I think we should look into the casting. If (Queue) queue.peek() actually creates a copy, your solution takes O(n) for pop().


  • 0

    It doesn't copy the queue. And even if it did, it would still only be O(1) because the queue only has two elements.


  • 0
    D

    Wooow. Nice solution. The only down side I see is that it would require the creation of many needless Queues. I would suggest some sort of Queue Pool class to manage this so many Queues are not just created and thrown away. But thumbs up. I doubt I could have come up with a pure O(1) solution.


  • 0
    Z

    Appreciate your creativity!
    I like this solution.


  • 0

    @karldwang "using LinkedList like this, it is effectively a stack" Why? OP didn't use any stack operations, and LinkedList could be replaced with any other class, which supports Queue interface.


  • 0
    L

    This is smart, but not elegant as you can have several nested queues. It's like the only purpose of the queue is to hold an int and another queue.


  • -3

    UPDATE:

    Notice : I was wrong. See the discussion followed.


    Disappointed.
    It's not O(1).

    If you use Linked structure to put the new element directly in the front of a queue, it's exactly the operation of a stack instead of "only standard operations of a queue".

    If you said you just add the whole queue at the after the new element, the push operation is O(n) because you need to copy all elements to add them into queue by "standard operations of a queue". In standard operation of a queue, add N elements always need O(n) time, even if you just write 1 line code.

    Always remembered that copy or create an O(n) object need O(n) time.
    If you just use the pointer to the memory address to add a Linked queue without any copy operation, OK, it's O(1). But it's not a standard operation, so it's does not follow the problem requirement at all.


  • 0

    @haiwei624 Well you're wrong. It is O(1) and it does only use the allowed operations. You seem to be confused about my "push". But as you can clearly see, I only use Queue.add, which obviously is allowed. And I just add two objects, into an empty queue even, so it's obviously O(1). Not sure what your problem is, but it sounds like you didn't really read my code and just describe how you can't imagine it being done in O(1).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.