Line data    Source code

       1              : // Copyright (c) 2022 The Authors. All rights reserved.
       2              : //
       3              : // Licensed under the Apache License, Version 2.0 (the "License");
       4              : // you may not use this file except in compliance with the License.
       5              : // You may obtain a copy of the License at
       6              : //
       7              : //      https://www.apache.org/licenses/LICENSE-2.0
       8              : //
       9              : // Unless required by applicable law or agreed to in writing, software
      10              : // distributed under the License is distributed on an "AS IS" BASIS,
      11              : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12              : // See the License for the specific language governing permissions and
      13              : // limitations under the License.
      14              : 
      15              : // Authors: liubang (it.liubang@gmail.com)
      16              : // Created: 2022/01/17 14:50
      17              : 
      18              : #include <gtest/gtest.h>
      19              : 
      20              : #include <stack>
      21              : 
      22              : namespace {
      23              : class SortedStack {
      24              : public:
      25            1 :     SortedStack() = default;
      26            1 :     virtual ~SortedStack() = default;
      27              : 
      28            3 :     void push(int x) {
      29            3 :         if (st_.empty() || st_.top() >= x) {
      30            1 :             st_.push(x);
      31              :         } else {
      32            2 :             std::stack<int> temp;
      33            5 :             while (!st_.empty() && st_.top() < x) {
      34            3 :                 temp.push(st_.top());
      35            3 :                 st_.pop();
      36              :             }
      37            2 :             st_.push(x);
      38            5 :             while (!temp.empty()) {
      39            3 :                 st_.push(temp.top());
      40            3 :                 temp.pop();
      41              :             }
      42            2 :         }
      43            3 :     }
      44              : 
      45            3 :     void pop() {
      46            3 :         if (!st_.empty()) {
      47            3 :             st_.pop();
      48              :         }
      49            3 :     }
      50              : 
      51            3 :     int peek() { return st_.empty() ? -1 : st_.top(); }
      52              : 
      53            2 :     bool empty() { return st_.empty(); }
      54              : 
      55              : private:
      56              :     std::stack<int> st_;
      57              : };
      58              : } // namespace
      59              : 
      60            4 : TEST(Leetcode, sort_of_stack_lcci) {
      61            1 :     SortedStack stack;
      62            1 :     stack.push(1);
      63            1 :     stack.push(2);
      64            1 :     stack.push(3);
      65              : 
      66            1 :     EXPECT_EQ(1, stack.peek());
      67            1 :     stack.pop();
      68            1 :     EXPECT_EQ(2, stack.peek());
      69            1 :     stack.pop();
      70            1 :     EXPECT_EQ(3, stack.peek());
      71            1 :     EXPECT_FALSE(stack.empty());
      72            1 :     stack.pop();
      73            1 :     EXPECT_TRUE(stack.empty());
      74            2 : }