数据结构算法面试题：请实现一个栈，在栈中支持取出最小值的操作。

た入场券 2024-03-16 17:03 29阅读 0赞

## 数据结构算法面试题：请实现一个栈，在栈中支持取出最小值的操作。 ##

题目：请实现一个栈，在栈中支持取出最小值的操作。

*  C++

#include <iostream>
    
    const int MAX_LEN = 1000;   // 定义一个最大长度常量，表示模拟栈的最大容量
    
    class MinStack {
        
    public:
        MinStack() : m_top(-1) {
        }    // 构造函数，初始化数据栈顶指针为 -1，表示当前栈为空栈
    
        void push(int x) {
          // 入栈操作
            if (m_top == MAX_LEN - 1) {
         // 如果数据栈满了，直接返回
                std::cout << "Stack overflow" << std::endl;
                return;
            }
    
            m_data[++m_top] = x;    // 在数据栈中插入元素
            if (m_minTop == -1 || x <= m_minData[m_minTop]) {
           // 如果最小值栈为空或者新插入的元素比最小值栈中的元素还要小
                m_minData[++m_minTop] = x;  // 将新元素加入到最小值栈的栈顶
            }
        }
    
        void pop() {
            // 出栈操作
            if (m_top == -1) {
          // 如果数据栈为空，直接返回
                std::cout << "Stack is empty" << std::endl;
                return;
            }
    
            if (m_data[m_top] == m_minData[m_minTop]) {
            // 如果数据栈的栈顶元素等于最小值栈的栈顶元素
                --m_minTop; // 最小值栈也出栈，维护最小值的状态
            }
            --m_top;    // 数据栈出栈
        }
    
        int top() {
         // 获取数据栈的栈顶元素，即最后入栈的元素
            if (m_top == -1) {
          // 如果数据栈为空，返回默认的 -1 值
                std::cout << "Stack is empty" << std::endl;
                return -1;  // 返回默认值
            }
    
            return m_data[m_top];
        }
    
        int getMin() {
          // 获取当前时刻的最小值（即最小值栈的栈顶元素）
            if (m_minTop == -1) {
           // 如果最小值栈为空，返回默认的 -1 值
                std::cout << "Stack is empty" << std::endl;
                return -1;  // 返回默认值
            }
    
            return m_minData[m_minTop];
        }
    
    private:
        int m_data[MAX_LEN];    // 模拟数据栈，用于存储所有元素
        int m_minData[MAX_LEN]; // 存储当前时刻的最小值
        int m_top;              // 数据栈顶指针，指向最后一个入栈的元素
        int m_minTop;           // 最小值栈顶指针，指向当前时刻的最小值
    };
    
    int main() {
        
        MinStack stack; // 声明并初始化了一个 MinStack 类的实例对象
       
        stack.push(5);  // 元素 5 入栈
        stack.push(2);  // 元素 2 入栈
        stack.push(7);  // 元素 7 入栈
    
        std::cout << "Min element: " << stack.getMin() << std::endl;    // 获取最小元素
        stack.pop();    // 出栈操作
        std::cout << "Top element: " << stack.top() << std::endl;    // 获取数据栈的栈顶元素（即最后入栈的元素）
        std::cout << "Min element: " << stack.getMin() << std::endl;    // 再次获取最小元素
    
        return 0;
    }

*  Java

import java.util.Arrays;
    
    class MinStack {
        
        private int[] m_data;       // 模拟数据栈，用于存储所有元素
        private int[] m_minData;    // 存储当前时刻的最小值
        private int m_top;          // 数据栈顶指针，指向最后一个入栈的元素
        private int m_minTop;       // 最小值栈顶指针，指向当前时刻的最小值
    
        public MinStack() {
        
            m_data = new int[1000];
            m_minData = new int[1000];
            Arrays.fill(m_minData, Integer.MAX_VALUE);  // 将最小值栈中的元素全部设置为最大值，确保新插入的元素一定比当前的最小值小
            m_top = -1;         // 构造函数，初始化数据栈顶指针为 -1，表示当前栈为空栈
            m_minTop = -1;      // 最小值栈顶指针置为 -1
        }
    
        public void push(int x) {
           // 入栈操作
            if (m_top == 999) {
             // 如果数据栈满了，直接返回
                System.out.println("Stack overflow");
                return;
            }
    
            m_data[++m_top] = x;    // 在数据栈中插入元素
            if (x <= m_minData[m_minTop]) {
         // 如果新插入的元素比最小值栈的栈顶元素还要小
                m_minData[++m_minTop] = x;  // 将新元素加入到最小值栈中
            }
        }
    
        public void pop() {
             // 出栈操作
            if (m_top == -1) {
          // 如果数据栈为空，直接返回
                System.out.println("Stack is empty");
                return;
            }
    
            if (m_data[m_top] == m_minData[m_minTop]) {
            // 如果数据栈的栈顶元素等于最小值栈的栈顶元素
                --m_minTop; // 最小值栈也出栈，维护最小值的状态
            }
            --m_top;    // 数据栈出栈
        }
    
        public int top() {
              // 获取数据栈的栈顶元素，即最后入栈的元素
            if (m_top == -1) {
          // 如果数据栈为空，返回默认的 -1 值
                System.out.println("Stack is empty");
                return -1;  // 返回默认值
            }
    
            return m_data[m_top];
        }
    
        public int getMin() {
           // 获取当前时刻的最小值（即最小值栈的栈顶元素）
            if (m_minTop == -1) {
           // 如果最小值栈为空，返回默认的 -1 值
                System.out.println("Stack is empty");
                return -1;  // 返回默认值
            }
    
            return m_minData[m_minTop];
        }
    
        public static void main(String[] args) {
        
            MinStack stack = new MinStack();    // 声明并初始化了一个 MinStack 类的实例对象
    
            stack.push(5);  // 元素 5 入栈
            stack.push(2);  // 元素 2 入栈
            stack.push(7);  // 元素 7 入栈
    
            System.out.println("Min element: " + stack.getMin()); // 获取最小元素
            stack.pop();    // 出栈操作
            System.out.println("Top element: " + stack.top());   // 获取数据栈的栈顶元素（即最后入栈的元素）
            System.out.println("Min element: " + stack.getMin()); // 再次获取最小元素
        }
    }