Skip to content

Instantly share code, notes, and snippets.

@ericoporto
Last active November 9, 2019 17:13
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ericoporto/57c03cd007bff7915ba71d70c509a839 to your computer and use it in GitHub Desktop.
Save ericoporto/57c03cd007bff7915ba71d70c509a839 to your computer and use it in GitHub Desktop.
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