所以在学习了 .NET 核心 Queue
类型在内部使用数组而不是节点后,我想我可以尝试自己编写它。
MyQueue
的奇怪之处在于,当它有 9200 个节点时,它的 Length
属性返回正确的大小,但是当它有 9300 个节点时,它会抛出一个 StackOverflowException
。
我一辈子都弄不明白为什么会这样。
队列节点
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;
}
}
}
我的队列
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}");
}
}
}
最佳答案
Windows 程序中的默认堆栈大小非常有限:
- 32 位进程 1MB。
- 64 位进程 4MB。
这是多年前决定的,影响所有进程,而不仅仅是 C# 进程。
这就是为什么您的进程如此快地耗尽堆栈空间的原因。
Also see here for more details .
请注意,可以更改用于进程的堆栈大小 - 通过使用 EDITBIN.EXE - 但不建议这样做。
您还可以更改新线程
的堆栈大小,但同样不推荐这样做。 (这并不总是适用于部分受信任的代码 - 如果部分受信任的代码超过默认堆栈大小,堆栈大小参数将被忽略。)
Microsoft 注意到以下内容:
Avoid using this constructor overload. The default stack size used by the Thread(ThreadStart) constructor overload is the recommended stack size for threads. If a thread has memory problems, the most likely cause is programming error, such as infinite recursion.
另请注意,您无法轻易更改 Task
的堆栈大小。
关于c# - 单链表队列在一定大小时抛出SO异常,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49572822/