-1

我想检索堆栈中输入的最小值（通过 push(int)）。

这是我迄今为止编写的示例代码Push，Pop但我未能获得最小值

class Program
{

    private int StackSize;

    public int StackSizeSet
    {
        get { return StackSize; }
        set { StackSize = value; }
    }

    public int top;
    Object[] item;

    public Program()
    {

        StackSizeSet = 10;
        item = new Object[StackSizeSet];
        top = -1;
    }

    public void isMinimum()
    {

        for (int i = 0; i <StackSizeSet; i++)
        {
            Console.WriteLine("Mianimum value is" + item[top]);
            Console.ReadKey();
        }
    }

    public bool isEmpty()
    {

        if (top == -1) return true;
        return false;
    }

    public void Push(int value)
    {

        if (top == (StackSize - 1))
        {
            Console.WriteLine("Stack is full!");
        }
        else
        {
            item[++top] = value;
            Console.WriteLine("Item pushed successfully!");
            Console.WriteLine(item[top]);
        }
    }

    public object Pop()
    {

        if (isEmpty())
        {
            Console.WriteLine("Stack is empty!");
            Console.ReadLine();
            return "No elements";
        }
        else
        {
            Console.WriteLine("Items popped successfully");
            return item[top--];
        }
    }

    static void Main(string[] args)
    {

        Program p = new Program();
        p.Push(10);
        p.Pop();
        p.isMinimum();
        //Console.WriteLine(p);
        Console.ReadKey();
    }
}
4

2 回答 2

2

除了项目本身，您还应该存储子堆栈的最小值。所以你将拥有：

int[] items;
int[] minima; //initialize in constructor

在Push您可以将最小值添加到堆栈中：

public void Push(int value)
{
    if (top == (StackSize - 1))
    {
        Console.WriteLine("Stack is full!");
    }
    else
    {          
        item[++top] = value;
        if(top == 0)
            minima[top] = value;
        else
            minima[top] = Math.Min(value, minima[top - 1]);
        Console.WriteLine("Item pushed successfully!");
        Console.WriteLine(item[top]);
    }
}

为了计算最小值，您只需查看最小值堆栈中最顶部的元素，这将为您提供O(1)时间复杂度而不是O(n).

这是一个示例（从下到上堆叠）：

items  minima
-------------
  1    1
  7    2
  5    2
  2    2
  3    3
于 2013-06-30T07:04:17.860 回答
1

您的所有Minimum方法都会遍历堆栈中的项目。您可以使用 LINQ 很容易地获得最小值，但是如果您想在没有集合的情况下进行，那么您可以做很长的路 - 遍历堆栈并继续存储最小值；一旦你浏览了堆栈，你就会得到答案。

假设您使用int[]而不是Object[]（所以我们不必处理演员表）：

int minValue = item[0];

for (int i = 1; i <StackSizeSet; i++)
{

    if (minValue > item[i])
    {
        minValue = item[i];
    }        
}

基本上，上面的代码会将最小值设置为数组中的第一个元素（堆栈中最旧的元素）。

然后它将遍历剩余元素，将当前元素与当前最小值进行比较 - 如果当前元素较低，则将最小值更新为当前值。

循环完成后，您将获得堆栈的最小值。

于 2013-06-30T06:52:43.917 回答