Simple C++ solution


  • 0
    H
    class Stack {
      typedef shared_ptr<queue<int>> QuePtr;
    public:
      // Push element x onto stack.
      void push(int x) {
        if (old_que->empty()) old_que->push(x);
        else {
          if (status || new_que->size() == old_que->size()) {
            update();
          }
          new_que->push(x);
          status = false;
        }
      }
    
      // Removes the element on top of the stack.
      void pop() {
        reorder(new_que, true);
        new_que->empty() ? old_que->pop() : new_que->pop();
      }
    
      // Get the top element.
      int top() {
        reorder(new_que, true);
        return new_que->empty() ? old_que->front() : new_que->front();
      }
    
      // Return whether the stack is empty.
      bool empty() {
        return new_que->empty() && old_que->empty();
      }
    
    private:
      QuePtr old_que = make_shared<queue<int>>();  // Always sorted.
      QuePtr new_que = make_shared<queue<int>>();  // Not sorted unless reordered.
      bool status = false;
    
    private:
      // Reorder only works on the new queue.
      void update() {
        reorder(new_que, true);
        // Combine old_que and new_que.
        while (!old_que->empty()) {
          new_que->push(old_que->front());
          old_que->pop();
        }
        swap(old_que, new_que);
      }
    
      void reorder(QuePtr que, bool flag = false) {
        if (status || que->size() == 0 || que->size() == 1) return;
        QuePtr temp = make_shared<queue<int>>();
        for (int i = 0; i < que->size() /2 ; ++i) {
          temp->push(que->front());
          que->pop();
        }
        reorder(temp);
        reorder(que);
        while (!temp->empty()) {
          que->push(temp->front());
          temp->pop();
        }
        if (flag) status = true;
      }
    };

Log in to reply
 

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