c# - 如何确定堆栈中是否有重复项实例？

Question

我需要检查堆栈中是否有重复项（仅在基本方法 pop、push、top、isempty 中使用）如果堆栈没有重复则返回 true，如果堆栈为空则返回 true，如果堆栈有重复则返回 false

public static bool CheckStack(Stack<int> s, int x)
{
    Stack<int> s1 = new Stack<int>();
    bool flag = false;
    if (s.IsEmpty())
        return false;
    while (!s.IsEmpty() && ! flag)
    {
        int temp = s.Pop();
        s1.Push(temp);
        if (temp == x)
            flag = true;
    }
    s = s1;
    return flag;
}

public static bool SpecialStack(Stack<int> s)
{
    int temp = s.Pop();
    while(!s.IsEmpty() && !CheckStack(s,temp))
    {
        temp = s.Pop();
    }
    if (s.IsEmpty())
        return true;
    return false;
}


public static void Main()
{
    Stack<int> st3 = new Stack<int>();
    st3.Push(7);
    st3.Push(2);
    st3.Push(1);
    st3.Push(8);
    st3.Push(7);
    Console.WriteLine(SpecialStack(st3));
}

在不使用其他函数的情况下如何做到这一点，以及解决方案需要使用基本方法的最短方法，而不使用 c# 的内置函数

标签： c#duplicatesstack

Answer 1

问题 #1：堆栈被清除

关于代码本身，乍一看我们需要：

bool CheckStack (ref Stack<int> s, int x)

要恢复堆栈，否则需要重新考虑设计，因为原始在方法结束时为空，返回后也是如此。

在 C# 中通过引用或值传递对象

按引用传递引用类型（C# 编程指南）

问题 #2：堆栈被还原

也可以通过 pop 和 push 将原始堆栈恢复为浅拷贝。

后进先出

问题 #3：SpecialStack

我对此方法有疑问，除非目标是一次清空堆栈一项并在每次迭代时调用 CheckStack 直到没有更多项。

简单的 Linq 解决方案

我们可以使用 Linq Distinct并比较每个Count：

Console.WriteLine(st3.Distinct().Count() != st3.Count);

因此，如果计数匹配，则没有重复，否则有一些。

通用扩展方法改进

static public class StackHelper
{
  static public bool HasDuplicates<T>(this Stack<T> stack)
  {
    return stack.Distinct().Count() != stack.Count;
  }
}

Console.WriteLine(st3.HasDuplicates()); // True

不使用除 Pop、Push、Contains 和 Count 之外的任何其他方法的解决方案

static public bool HasDuplicates<T>(this Stack<T> stack)
{
  // Check for duplicates
  bool nodup = true;
  var temp = new Stack<T>();
  while ( stack.Count != 0 )
  {
    var item = stack.Pop();
    if ( nodup && temp.Contains(item) ) nodup = false;
    temp.Push(item);
  }
  // Restore original stack
  while ( temp.Count != 0 )
  {
    stack.Push(temp.Pop());
  }
  return !nodup;
}

注意：T可以替换int为删除通用性，方法可以根据需要声明，扩展与否，静态或实例...