A simple C++ solution


  • 152
    S
    class Stack {
    public:
    	queue<int> que;
    	// Push element x onto stack.
    	void push(int x) {
    		que.push(x);
    		for(int i=0;i<que.size()-1;++i){
    			que.push(que.front());
    			que.pop();
    		}
    	}
    
    	// Removes the element on top of the stack.
    	void pop() {
    		que.pop();
    	}
    
    	// Get the top element.
    	int top() {
    		return que.front();
    	}
    
    	// Return whether the stack is empty.
    	bool empty() {
    		return que.empty();
    	}
    };

  • 0
    B

    I think this is a brilliant idea


  • 17
    L

    I think this is the best solution. Also shows why simulating stack with queue is simply a dumb idea.


  • 0
    S

    Smartest solution of all comments


  • 0
    A

    The most smart solution i've ever seen, thanks!


  • 0
    C

    it's very nice


  • 0
    M

    The problem is stupid.
    But your code looks clean and smart.


  • 0
    D

    can someone explain the 'push()' part? it wud be useful for number of ppls like me


  • 1
    D

    can someone explain the 'push()' part? it wud be useful for number of ppls like me


  • 0
    A

    You need to understand how a stack and a queue works. For a stack, it's last-in-first-out, while for a queue, it's first-in-first-out. So if you want to implement a stack using queues, you have to save all elements into an 'auxiliary' queue before pushing new element into the stack. In such way, the newly pushed element will be at the head of queue functioning the same as the top of a stack.


  • 0
    S

    nice idea. I think it would be also nice to keep queue<int> que; as private


  • 0
    S

    why top() is que.front()? I think it should be something like que.back()


  • 0
    F

    because we can see the front of queue as the top of the stack, then, the only different operation between queue and stack is pushing,


  • 3
    T

    alanwhc, that doesn't explain it; there's no extra queue here, just a storage area which takes up O(n) space, the auxiliary space complexity is O(1) I think.

    Here's a try on explaining what's inside push: when you push a new element it'll be at the end of the queue, but you'll want it to be at the front. To achieve this you need to rotate the queue, the push(front); pop; part. Here's an example (rotate operation = pop front, then push into back):

    push 1 -> [1]       and no rotate
    push 2 -> [2,1]     and rotate 1 time : -> [1,2]
    push 3 -> [2,1,3]   and rotate 2 times: -> [1,3,2] -> [3,2,1]
    push 4 -> [3,2,1,4] and rotate 3 times: -> [2,1,4,3] -> [1,4,3,2] -> [4,3,2,1]
    pop    -> [3,2,1]   and return 4
    pop    -> [2,1]     and return 3
    push 5 -> [2,1,5]   and rotate 2 times: -> [1,5,2] -> [5,2,1]
    pop    -> [2,1]     and return 5

  • 0
    Y

    better than my solution using two queues


  • 0
    T

    I found a weird thing.
    if I use void push(int x) {
    que.push(x);
    for(int i=0;i<=que.size()-2;i++){
    que.push(que.front());
    que.pop();
    }
    if says time limitation exceeded. Last executed input:
    push(1),empty
    but if I use void push(int x) {
    que.push(x);
    for(int i=0;i<que.size()-1;i++){
    que.push(que.front());
    que.pop();
    }
    it is accepted!!
    Who can tell me why is that??? Thanks a lot!!


  • 0
    A

    your push function is very nice,re insert every element before the new element in to the queue !


  • 0
    M

    for(int i=0;i<=que.size()-2;i++) -> If que.size() returns 1, then infinite loop....


  • 0
    B

    Hey shouldn't we avoid using ".size( )" function?! Since it is not standard?!

    And you can indeed write solution without using ".size( )"!

    UPDATE: My bad, we can use ".size( )". However, we can implement stack using TWO queues, and without using ".size( )".


  • 0
    C

    you're kidding me?How it make infinite loop when que.size = 1?It can't enter the for loop,because initial i value is 0 and que.size-2 = -1,so it break for loop~


Log in to reply
 

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