Last active
November 9, 2019 17:13
-
-
Save ericoporto/57c03cd007bff7915ba71d70c509a839 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
struct stackObj { | |
int num_; | |
int min_; // We track min in the stackObject. | |
stackObj* nextItem_; | |
stackObj(int num, stackObj* nextItem = nullptr) : num_(num), min_(num), nextItem_(nextItem) {}; | |
}; // The min of a stackObj is initially itself. Later it is compared to the item below it. | |
class MinStack { | |
private: | |
int size_; | |
stackObj* topElement_; | |
public: | |
/** initialize your data structure here. */ | |
MinStack() { | |
size_ = 0; | |
topElement = nullptr; | |
} | |
void push(int num) { | |
stackObj* newItem = new stackObj(num); | |
if (empty()) { // If we start empty, no need to set the min. The min is the first node. | |
newItem->nextItem_ = topElement_; | |
topElement_ = newItem; | |
} | |
newItem->nextItem_ = topElement_; // If not empty, set the new stackObj's min | |
newItem->min_ = newItem->nextItem_->min_ > num ? num : newItem->nextItem_->min_; | |
topElement_ = newItem; | |
size_++; | |
return; | |
} | |
void pop() { | |
if (empty()) return; | |
stackObj* pTemp = topElement_; | |
topElement_ = topElement_->nextItem_; | |
delete pTemp; // Delete item so no memory leak. | |
size_--; // Used to check if the stack is empty | |
return; | |
} | |
int top() { | |
if (empty()) { | |
return -1; // Return -1 if empty() | |
} | |
return topElement_->num_; | |
} | |
int getMin() { | |
if (empty()) return -1; // Return -1 if empty() | |
return topElement_->min_; | |
} | |
bool empty() const { | |
return size_ == 0; // Check whether stack is empty | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment