单一链接的列表队列在一定尺寸时抛出如此例外

Question

因此，在学习.NET CORE Queue类型之后，内部使用数组而不是节点，我认为我会写自己的作品。

MyQueue的奇怪之处在于，当它的大小为9200时，其Length属性返回其正确的大小，但是当它具有9300个节点时，它会抛出StackOverflowException。

我一生都不能弄清楚为什么是这种情况。

queuenode

namespace MyQ.Core
{
    public class MyQueueNode<T> : IMyQueueNode<T>
    {
        private MyQueueNode<T> _nextNode;
        private T _value;
        //..
        public MyQueueNode(T value)
        {
            _value = value;
        }
        public void SetNextNode(ref MyQueueNode<T> nextNode)
        {
            _nextNode = nextNode;
        }
        public MyQueueNode<T> GetNextNode()
        {
            return _nextNode;
        }
        public T GetValue()
        {
            return _value;
        }
    }
}

myqueue

namespace MyQ.Core
{
    public class MyQueue<T> : IMyQueue<T> where T : class
    {
        private volatile MyQueueNode<T> _headNode, _tailNode;
        //..
        public void Enqueue(T item)
        {
            MyQueueNode<T> newNode = new MyQueueNode<T>(item);
            if (_headNode == null)
            {
                _headNode = newNode;
                _tailNode = _headNode;
            }
            else
            {
                _tailNode.SetNextNode(ref newNode);
                _tailNode = newNode;
            } 
        }
        public T Dequeue()
        {
            if(_headNode == null)
            {
                throw new QueueEmptyException();
            }
            T value = _headNode.GetValue();
            _headNode = _headNode.GetNextNode();
            return value;
        }
        public T Peek()
        {
            if(_headNode == null)
            {
                return null;
            }
            return _headNode.GetValue();
        }
        public long Length => GetLength(_headNode);
        //..
        private long GetLength(MyQueueNode<T> node = null, long level = 0)
        {
            if(node == null)
            {
                return 0;
            }
            level++;
            if (node.GetNextNode() == null)
            {
                return level;
            }
            node = node.GetNextNode();
            return GetLength(node, level);
        }
    }
}

测试程序

using System;
using MyQ.Core;
using System.Diagnostics;
namespace MyQ
{
    class Program
    {
        static void Main(string[] args)
        {
            IMyQueue<string> myQ = new MyQueue<string>();
            //..
            myQ.Enqueue("test 1");
            myQ.Enqueue("test 2");
            myQ.Enqueue("test 3");
            //..
            Console.WriteLine($"The length of the queue is: {myQ.Length}");
            //..
            Console.WriteLine("Peek: " + myQ.Peek()); // 1
            //..
            Console.WriteLine("Dequeue: " + myQ.Dequeue()); // 1
            Console.WriteLine("Dequeue: " + myQ.Dequeue()); // 2
            Console.WriteLine($"The length of the queue is: {myQ.Length}");
            Console.WriteLine("Dequeue: " + myQ.Dequeue()); // 3
            //..
            Console.WriteLine("About to test seed a queue. Press a key to start...");
            Console.ReadKey();
            TestSize(9200); // This works fine...
            TestSize(9300); // This one falls over...
            Console.ReadKey();
        }
        static void TestSize(long seedSize)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            IMyQueue<string> queue = new MyQueue<string>();
            for (int i = 0; i < seedSize; i++)
            {
                Console.WriteLine($"Queue {i}");
                queue.Enqueue(i.ToString());
            }
            sw.Stop();
            Console.WriteLine($"Done. Took {sw.Elapsed.TotalSeconds} seconds.");
            Console.WriteLine($"Queue length is: {queue.Length}");
        }
    }
}

Answer 1

Windows程序中的默认堆栈大小非常有限：

• 1MB用于32位过程。
• 4MB用于64位过程。

这是多年前决定的，并且影响了所有过程，而不仅仅是C＃。

这就是为什么您的流程如此之快地从堆栈空间中耗尽的原因。

也请参见此处以获取更多详细信息。

请注意，可以通过使用editbin.exe更改用于过程的堆栈大小 - 但不建议这样做。

您还可以更改新的Thread的堆栈大小，但不建议这样做。(这并不总是适用于部分信任的代码 - 如果超过默认的堆栈大小，则堆栈大小参数将被部分信任的代码忽略。(

Microsoft注意：

避免使用此构造函数过载。线程(螺纹Start(构造函数超载的默认堆栈大小是线程的建议堆栈大小。如果线程有内存问题，最有可能的原因是编程错误，例如无限递归。

还要注意，您无法轻易更改Task的堆栈大小。

Answer 2

实际上您可以简化(并优化(GetLength方法。只需在Enqueue和Dequeue上跟踪项目即可。尝试以下操作：

public int Length { get; private set; }
public void Enqueue(T item)
{
  ++Length;
  // ...
}
public T Dequeue()
{
  --Length;
  // ...
}