0. Introduction to the minimum stack

Minimum stack: The minimum stack is a stack. In addition to the same functions as push(), pop(), top(), etc., there is also a main method, the get_min function, which is used to obtain the minimum element in the current stack.

get_min() function: The minimum value of the current stack can be obtained in O(1) time.

1. Algorithm problem

Question: Implement a stack with three methods: pop(), push(), and get_min() for the smallest element. The time complexity of the three methods is guaranteed to be O(1).

2. Explanation of ideas

detailed steps:

1. Assuming the original stack A, an additional stack B is established at this time to store the minimum value currently pushed into the stack, which is used to assist stack A to obtain the minimum value.

Stack A:

stack B:

1. When the first element enters stack A, let the first element also enter stack B, because the smallest element of stack A at this time is the first element pushed onto the stack.

Stack A:

5

stack B:

5

1. Next, when each element enters stack A, compare the size of the new element with the smallest element of stack A (that is, compare the top element of stack B), if it is less than the minimum value of stack A, let the new element enter stack B, this The top element of stack B is the smallest element of stack A.

Before pushing stack A:

5	6	7

Before pushing stack B:

5

After pushing stack A:

5	6	7	4

After pushing stack B:

5	4

1. When the element is popped from the stack, if the popped element is the current smallest element of stack A, the top element of stack B is also popped from the stack. At this point, the top of stack B points to the next smallest element of stack A.

Pop A:

5	6	7

Pop B:

5

1. • When calling get_min(), return the value at the top of the stack;

   • When push() is called, continue to step 3;

   • When calling pop(), proceed to step 4;

   • When calling top(), return the top value of stack A

3. Complete code

Code Compiler: VS2019

It uses the STL stack operation that comes with the system. For details on this part, please see: Basic operations of stack and queue (including STL) from function implementation to STL application

//Main code: Create a MinimumStack class to encapsulate MinimumStack.h   
#pragma once
#include <iostream>
#include <stack>

using namespace std;

class MinimumStack{
public:
	void push(int value);
	void pop();
	int top();
	int get_min();
private:
	stack<int>  A, B;
};

// Class concrete implementation MinimumStack.cpp 
#include "MinimumStack.h"

void MinimumStack::push(int value) {
	if (A.empty()) {     //Determine whether stack A is empty, if it is empty, the minimum value is not compared, and it is directly pushed into the stack
		A.push(value);
		B.push(value);
	}
	else {
		if (value > B.top()) {
			A.push(value);
		}
		else {
			A.push(value);
			B.push(value);
		}
	}

}

void MinimumStack::pop() {
	if (A.top() == B.top()) {    //If the popped element is the smallest element of the current stack A, then stack B will also pop the stack
		A.pop();
		B.pop();
	}
	else {
		A.pop();
	}
}

int MinimumStack::top() {
	return A.top();
}

int MinimumStack::get_min() {
	return B.top();
}

//Example demo main.cpp
#include<iostream>
#include "MinimumStack.h"

using namespace std;

int main() {
	MinimumStack minimumStack;
	minimumStack.push(5);
	minimumStack.push(6);
	minimumStack.push(7);
	minimumStack.push(4);
	cout << " get_man() = " << minimumStack.get_min() << endl;
	minimumStack.push(3);
	cout << " get_man() = " << minimumStack.get_min() << endl;
	minimumStack.pop();
	cout << " get_man() = " << minimumStack.get_min() << endl;
	cout << " top() = " << minimumStack.top() << endl;
	minimumStack.pop();
	cout << " get_man() = " << minimumStack.get_min() << endl;
	cout << " top() =  " << minimumStack.top() << endl;
	minimumStack.pop();
	cout << " get_man() = " << minimumStack.get_min() << endl;
	cout << " top() = " << minimumStack.top() << endl;
	minimumStack.pop();
	minimumStack.pop();
	minimumStack.push(10);
	cout << " get_man() = " << minimumStack.get_min() << endl;
	system("pause");
}

Run the screenshot: