时间戳

首页 > 解决方案 > Add the function of finding the minimum element to the "Queue" structure

c# - Add the function of finding the minimum element to the "Queue" structure

问题描述

Welcome all.
I understand the principle of the queue, having implemented it myself.
I need to supplement the code with a function to find the minimum element among the currently existing ones. Some points in this code were not done by myself, and in principle, I just started working with object-oriented programming.
Give me an idea of how to refer to elements and which loop to use to find the minimum element.
Thanks.

class Program
    {
        public static void Main()
        {
            var watch = new Stopwatch();
            watch.Start(); // начало замера времени
            long before = GC.GetTotalMemory(false);
            int min = int.MaxValue;
            Queue queue = new Queue(); // Структура очередь
            File.WriteAllText(@"output.txt", string.Empty);
            using (StreamReader sr = new StreamReader(@"input.txt", System.Text.Encoding.Default)) // Считывание файла input.txt
            {
                string line;
                while ((line = sr.ReadLine()) != null) // пока строки в файле не null
                {
                    if (line[0] == '+') // если "+", добавить элемент со значением, стоящим после "+"
                    {
                        var pattern = new Regex(@"\d+");
                        var numberStr = pattern.Match(line).Groups[0].Value;
                        queue.Enqueue(int.Parse(numberStr));
                    }
                    if (line[0] == '-') // если "-", выпустить элемент из очереди (first in - first out)
                    {
                        using (StreamWriter sw = new StreamWriter(@"output.txt", true, System.Text.Encoding.Default))
                        {
                            sw.WriteLine(queue.Dequeue());
                        }
                    }
                    if (line[0] == '?') // если "?", вывести наименьший элемент в очереди
                    {
                        using (StreamWriter sw = new StreamWriter(@"output.txt", true, System.Text.Encoding.Default))
                        {
                            sw.WriteLine(queue.Minimum());
                        }
                    }
                }
            }
            long after = GC.GetTotalMemory(false);
            long consumedInMegabytes = (after - before) / (1024); // замер памяти в КБ
            Console.WriteLine($"Затраты памяти (КБ): {consumedInMegabytes}");
            watch.Stop(); // конец замера времени
            Console.WriteLine($"Время выполнения (миллисекунд): {watch.ElapsedMilliseconds}");


        }
    }

    public class QueueItem
    {
        public int Value { get; set; }
        public QueueItem Next { get; set; }
    }

    public class Queue
    {
        QueueItem head;
        QueueItem tail;

        public void Enqueue(int value) // функция добавления элемента в очередь
        {
            if (head == null)
                tail = head = new QueueItem { Value = value, Next = null };
            else
            {
                var item = new QueueItem { Value = value, Next = null };
                tail.Next = item;
                tail = item;
            }
        }

        public int Dequeue() // функция удаления элемента из очереди
        {
            if (head == null) throw new InvalidOperationException();
            var result = head.Value;
            head = head.Next;
            if (head == null)
                tail = null;
            return result;
        }
        public int Minimum()
        {
            // WHAT I NEED DO
        }
    }

标签： c#algorithmfunctionmin

解决方案

假设我们将这些值排入队列：

index: 0 1 2 3 4 5 6 7 8 9
value: 5 3 8 4 2 1 6 3 7 2

第 3 项入队后的正确值Minimum是多少？这得看情况。它可以是3（如果项目 1 尚未出队），也可以是4. 但它永远不可能是5or 8，因为4 < 5and 4 < 8，无论哪个值已经出队。

所以我们可以构建一个数据结构Minimum，在每个入队之后有 的潜在答案：

index:     0   1      2      3   4   5      6      7         8      9
value:     5   3      8      4   2   1      6      3         7      2
minimum:  [5] [3] [3, 8] [3, 4] [2] [1] [1, 6] [1, 3] [1, 3, 7] [1, 2]

看到minimum列表总是排序的。如果我们遇到一个大于列表中最大项目的新值，我们会追加它。如果它更小，我们用新的值替换所有更大的值。

现在，出队会发生什么？让我们取minimum索引 8 之后的列表（因为它恰好是最长/最有趣的），看看出队会发生什么：

index:          0         1         2         3         4      5      6   7   8
dequeue:        5         3         8         4         2      1      6   3   7
minimum: [1, 3, 7] [1, 3, 7] [1, 3, 7] [1, 3, 7] [1, 3, 7] [3, 7] [3, 7] [7] []

请注意，当我们将相同的值出列时，我们只是从列表中删除了最小值。

现在我们需要的是一个数据结构，它允许我们检查第一个元素（O(1)及时），删除第一个元素（O(1)及时），并在末尾添加一个新值（这也需要O(n)从末尾删除摊销的元素） .

由于这是一个大学练习，我将把实际的实现留给你，但这应该希望能把你推向正确的方向。

推荐阅读