java - minStack 子类使用一个对象作为最小堆栈和常规堆栈

问题描述

我正在阅读 CTCI 的书，发现这个答案令人困惑。目标是创建一个堆栈数据结构，可以在 O(1) 中推送、弹出和 min（获取堆栈中的最小元素）。我编写了一个有两个堆栈的类，一个用于保存最小值，一个用作常规堆栈。代码如下。据我所知，这适用于测试。

   public static class StackWithMin extends Stack<Integer>{
      Stack<Integer> stack;
      Stack<Integer> minStack;

      public StackWithMin(){
         stack = new Stack<Integer>();
         minStack = new Stack<Integer>();
      }

      public void push(int value){
         if(value <= min()){
            minStack.push(value); 
         }
         stack.push(value);
      }

      public Integer pop(){
         int value = stack.pop();
         if(value == min()){
            minStack.pop();
         }
         return value;
      }
      public int min(){
         if(minStack.isEmpty()){
            return Integer.MAX_VALUE;
         }
         return minStack.peek();  
      }
   }

但是，书中给出的答案对我来说并不完全清楚。我学过两门 Java 课程，但最后两门学的是 C，所以我的 OOP 概念有点生疏。该类中只有一个堆栈字段，并使用 super 调用来更新“常规”堆栈，并使用 s2 调用来更新最小堆栈。在 Java 可视化器中查看此内容仅显示一个堆栈对象，该对象显然存储了两个不同的堆栈。这个实现有效，但我不确定为什么。澄清将不胜感激！

public class Q2 /* MinStack */ extends Stack<Integer> {
    private Stack<Integer> min = new Stack<Integer>();

    public void push(int item) {
        if (min.isEmpty() || item < min()) {
            min.push(item);
        }
        super.push(item);
    }

    public Integer pop() {
        int item = super.pop();
        if (item == min()) {
            min.pop();
        }
        return item;
    }

    public Integer min() {
        return min.peek();
    }

标签： javaoopinheritancedata-structurespolymorphism

该代码确实生成了两个堆栈。Q2类扩展类这一事实Stack<Integer>意味着父类中存在的所有内容也存在于类中Q2，包括“常规”堆栈，但只是要在 Java 中访问它，您需要使用super关键字。

这张图片可以解释这个包含父类的 OOP 概念（“Bird”中存在的所有内容都存在“AngryBird”中）：

现在，由于您的Q2类“包括”一个堆栈并像堆栈一样运行，因此您正在创建一个新的第二个堆栈，以作为您班级中的成员的最小值。

如果您想知道解决方案中的“错误”是什么，是您实际上没有使用基类，那么即使没有该extends Stack<Integer>语句，您的代码也可以工作。

java - minStack 子类使用一个对象作为最小堆栈和常规堆栈

问题描述

解决方案

推荐阅读