在不使用集合的情况下从堆栈中获取C#PUSH(int data)、pop()和getmin()值

本文关键字：data int pop getmin C#PUSH 获取 集合 情况下 堆栈 | 更新日期: 2023-09-27 18:20:31

我想检索（通过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();
    }
}

在不使用集合的情况下从堆栈中获取C#PUSH(int data)、pop()和getmin()值

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

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

所有Minimum方法都会遍历堆栈中的项。你可以很容易地使用LINQ来获得最小值，但如果你想在没有集合的情况下做到这一点，那么你可以做很长的路——遍历堆栈并保持存储最小值；一旦你看完了答案，你就会有答案了。

假设您使用int[]而不是Object[]（因此我们不必处理强制转换）：

int minValue = item[0];
for (int i = 1; i <StackSizeSet; i++)
{
    if (minValue > item[i])
    {
        minValue = item[i];
    }        
}

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

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

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

相关文章：