Line data    Source code

       1              : // Copyright (c) 2024 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              : 
      17              : #include <gtest/gtest.h>
      18              : 
      19              : #include <stack>
      20              : 
      21              : namespace {
      22              : class SortedStack {
      23              : public:
      24            1 :     SortedStack() = default;
      25            1 :     virtual ~SortedStack() = default;
      26              : 
      27            3 :     void push(int x) {
      28            3 :         if (st_.empty() || st_.top() >= x) {
      29            1 :             st_.push(x);
      30              :         } else {
      31            2 :             std::stack<int> temp;
      32            5 :             while (!st_.empty() && st_.top() < x) {
      33            3 :                 temp.push(st_.top());
      34            3 :                 st_.pop();
      35              :             }
      36            2 :             st_.push(x);
      37            5 :             while (!temp.empty()) {
      38            3 :                 st_.push(temp.top());
      39            3 :                 temp.pop();
      40              :             }
      41            2 :         }
      42            3 :     }
      43              : 
      44            3 :     void pop() {
      45            3 :         if (!st_.empty()) {
      46            3 :             st_.pop();
      47              :         }
      48            3 :     }
      49              : 
      50            3 :     int peek() { return st_.empty() ? -1 : st_.top(); }
      51              : 
      52            2 :     bool empty() { return st_.empty(); }
      53              : 
      54              : private:
      55              :     std::stack<int> st_;
      56              : };
      57              : } // namespace
      58              : 
      59            4 : TEST(Leetcode, sort_of_stack_lcci) {
      60            1 :     SortedStack stack;
      61            1 :     stack.push(1);
      62            1 :     stack.push(2);
      63            1 :     stack.push(3);
      64              : 
      65            1 :     EXPECT_EQ(1, stack.peek());
      66            1 :     stack.pop();
      67            1 :     EXPECT_EQ(2, stack.peek());
      68            1 :     stack.pop();
      69            1 :     EXPECT_EQ(3, stack.peek());
      70            1 :     EXPECT_FALSE(stack.empty());
      71            1 :     stack.pop();
      72            1 :     EXPECT_TRUE(stack.empty());
      73            2 : }