Initial commit.HEADmain

1 files changed, 56 insertions, 0 deletions

diff --git a/top-interview-questions/easy/design/02_min_stack.cc b/top-interview-questions/easy/design/02_min_stack.cc
new file mode 100644
index 0000000..1bcb36a
--- /dev/null
+++ b/top-interview-questions/easy/design/02_min_stack.cc
@@ -0,0 +1,56 @@
+class MinStack {
+public:
+    MinStack() {}
+
+    void push(int val) {
+        const int minVal = (m_minStack != nullptr) ? std::min(m_minStack->val, val) : val;
+        Node* top    = new Node{m_stack,    val};
+        Node* minTop = new Node{m_minStack, minVal};
+        m_stack      = top;
+        m_minStack   = minTop;
+    }
+
+    void pop() {
+        assertNonEmpty();
+        Node* top    = m_stack;
+        Node* minTop = m_minStack;
+        m_stack      = m_stack->next;
+        m_minStack   = m_minStack->next;
+        delete top;
+        delete minTop;
+    }
+
+    int top() {
+        assertNonEmpty();
+        return m_stack->val;
+    }
+
+    int getMin() {
+        assertNonEmpty();
+        return m_minStack->val;
+    }
+
+private:
+    struct Node {
+        Node* next;
+        int   val;
+    };
+
+    void assertNonEmpty() const {
+        if (m_stack == nullptr) {
+            throw "empty stack";
+        }
+    }
+
+    Node* m_stack    = nullptr; // The actual stack.
+    Node* m_minStack = nullptr; // Stack of mins.
+};
+
+/**
+ * Your MinStack object will be instantiated and called as such:
+ * MinStack* obj = new MinStack();
+ * obj->push(val);
+ * obj->pop();
+ * int param_3 = obj->top();
+ * int param_4 = obj->getMin();
+ */