4

有没有人有关于如何/什么是在 C# 中实现 Stack 类的最佳方法的任何示例或想法？我知道已经有一个 Stack 类，但我需要了解如何实际实现一个 Stack 类。

我还需要有关如何在 C# 中使用 Contracts 为此类指定前置条件、后置条件和不变量的建议。我想我之前在 ASP.NET MVC 架构中创建模型时使用过类似的东西，但我不完全确定它是否是相同的东西并且以相同的方式工作。（如果你还不能告诉我，我对先决条件/后置条件/不变量有点迷茫 - 所以请多多包涵。）

我的主要问题- 有人可以给我关于正确使用合同的建议，例如堆栈。

是的，我已经付出了努力：

public interface IStack
{
        void Push(Object e);
        Object Pop();
        Object Top();
        void EnsureCapacity();
    }
}

   public class Stack : IStack
{
    private Object[] elements;
    private int size = 0;

    public Stack()
    {
        elements = new Object[0];
    }

    public void Push(Object e)
    {
        // check if this array capacity has been reached and increase if needed
        EnsureCapacity();
        elements[size++] = e;
    }

    public Object Pop()
    {
        // check if the method call is invalid for the object's current state
        if (size == 0) throw new InvalidOperationException("Stack.Pop");

        Object result = elements[--size];
        elements[size] = null;

        return result;
    }

    public Object Top()
    {
        // check if the method call is invalid for the object's current state
        if (size == 0) throw new InvalidOperationException("Stack.top");
        return elements[(size - 1)];
    }

    private void EnsureCapacity()
    {
        if (elements.Length == size)
        {
            Object[] oldElements = elements;
            elements = new Object[(2 * size + 1)];
        }
    }
}
4

2 回答 2

1

在 c# 中实现的许多集合都是基于数组的。您可以使用数组并将元素添加到末尾，保留顶部元素的索引并在推送新元素时增加它，当然当新对象出现并且存在时，数组将“必须动态扩展”（替换为新元素）当前数组中没有它们的位置。

代码合同在http://research.microsoft.com/en-us/projects/contracts/userdoc.pdf上有很好的文档

于 2011-10-05T22:03:13.387 回答
1

如果您愿意，为了开始使用 Microsoft 代码合同，我曾经发表过一篇关于它的博客文章。那篇文章涵盖了前置条件、后置条件和不变量的基础知识。

作为概念的总结，您可以将它们视为如下：

  • 前提条件是在执行方法之前必须为真的——客户向您的方法承诺的内容。
  • 就您班级的客户而言，不变是必须始终保持公开真实的内容。
  • 后置条件是在方法执行之后必须为真的——你的方法向客户承诺的。

所以，在我的脑海中，对于一个堆栈，一个容易想到的事情可能是一个不变量。如果您使用数组对堆栈进行建模，您可能会在类上声明一个数组永远不会设置为 null 的不变量，例如，您将定义 invariant 方法：

[ContractInvariantMethod]
private void ObjectInvariant()
{
   Contract.Invariant(elements != null);
}

看起来您已经对 pop 方法设置了先决条件 - 您想说用户有责任确保在执行 pop 时堆栈不为空。因此，在 pop 方法的开头，您将拥有：

Contract.Requires(size > 0);

最后，您可以在 pop 上指定一个后置条件，该大小将始终小于 pop 操作之前的大小（如果您愿意，可以更具体）：

Contract.Ensures(Contract.OldValue<int>(size) > size);

祝你好运——合同很酷而且很有用。这是一种非常简洁的编码方式。

于 2011-10-05T22:57:34.353 回答