【栈与队列_1】设计一个有getMin功能的栈

﹏ヽ暗。殇╰゛Y 2022-12-22 06:26 144阅读 0赞

> 实现自己梦想的最好方式就是学习~

### 目录 ###

*  【题目】
 *  【要求】
 *  【难度】
 *  【解答】
 *   *  1. 压入数据规则
     *  2. 弹出数据规则
     *  3. 查询最小值操作
 *  【代码】
 *  【点评】

# 【题目】 #

实现一个特殊功能的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

# 【要求】 #

1.  pop、push、getMin操作的时间复杂度都是O(1)
2.  设计的栈类型可以使用现成的栈结构

# 【难度】 #

士 一星

# 【解答】 #

## 1. 压入数据规则 ##

*  假设当前数据为 newNumber，先将其压入 stackData。然后判断 stackMin 是否为空
 *  如果为空，则 newNumber 也压入 stackMin；如果不为空，则比较 newNumber 和 stackMin 的栈顶元素，哪个元素比较小，stackMin 就压入哪个元素

## 2. 弹出数据规则 ##

*  先判断当前的 stackData 是否为空，再进行弹出

## 3. 查询最小值操作 ##

*  直接进行查询，返回 stackMin 的栈顶即可

# 【代码】 #

class MyStack
        {
        
            private Stack<int> stackData;  // 存放着数据
            private Stack<int> stackMin;  // 作为获取最小值
            public MyStack()
            {
        
                stackData = new Stack<int>();
                stackMin = new Stack<int>();
            }
    
            // push:
            public void push(int number)
            {
        
                stackData.Push(number);
                if (stackMin.Count == 0)
                {
        
                    stackMin.Push(number);
                }
                else
                {
        
                    if (stackMin.Peek() < number)
                    {
        
                        stackMin.Push(stackMin.Peek());
                    }
                    else
                    {
        
                        stackMin.Push(number);
                    }
                }
            }
    
            public int pop()
            {
        
                if (stackData.Count == 0)
                {
        
                    throw new Exception("Your stack is empty");
                }
                stackMin.Pop();
                return stackData.Pop();
            }
    
            public int getMin()
            {
        
                if (stackMin.Count == 0)
                {
        
                    throw new Exception("Your stack is empty");
                }
                return stackMin.Peek();
            }
        }

# 【点评】 #

*  时间复杂度O(1) 、空间复杂度O(n)
 *  栈和队列的基础题目