J & J - 정성태의 닷넷 이야기

사용자

메뉴

최근 덧글

[정성태] VT sequences to "CONOUT$" vs. STD_O...[정성태] NetCoreDbg is a managed code debugg...[정성태] Evaluating tail call elimination in...[정성태] What’s new in System.Text.Json in ....[정성태] What's new in .NET 9: Cryptography ...[정성태] 아... 제시해 주신 "https://akrzemi1.wordp...[정성태] 다시 질문을 정리할 필요가 있을 것 같습니다. 제가 본문에...[이승준] 완전히 잘못 짚었습니다. 댓글 지우고 싶네요. 검색을 해보...[정성태] 우선 답글 감사합니다. ^^ 그런데, 사실 저 예제는 (g...[이승준] 수정이 안되어서... byteArray는 BYTE* 타입입니다...

글쓰기

제목

이름

암호

전자우편

HTML

홈페이지

유형

내용

<div style='display: inline'>
<h1 style='font-family: Malgun Gothic, Consolas; font-size: 20pt; color: #006699; text-align: center; font-weight: bold'>C# - 덮어쓰기 가능한 환형 큐 (Circular queue)</h1>

간혹, 환형 큐인데 최대 크기를 채운 경우 마지막에 추가했던 값을 덮어쓰는 식의 동작이 필요한 경우가 있습니다. 
 
이를 위해, List&lt;T&gt; 등을 기반으로 구현하면 편리하긴 한데 내부적으로 Append, Delete(0)을 하는 과정에 자꾸만 배열 복사가 발생할 수 있기 때문에 GC를 괴롭히게 된다는 단점이 있습니다. 
 
따라서, 어차피 환형 큐이고 덮어쓰기를 허용한다면 연속적인 배열로 처리하는 것이 좋은데요, 여기서 유의할 점은 적절한 head/tail의 index 위치에 대한 연산입니다. 물론, 이미 그런 연산을 잘 해주는 코드는 검색만 하면 나오기 때문에, ^^ 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
C# program to implement circular queue using array
; <a target='tab' href='https://www.includehelp.com/dot-net/implement-circular-queue-using-array-using-c-sharp-program.aspx'>https://www.includehelp.com/dot-net/implement-circular-queue-using-array-using-c-sharp-program.aspx</a>
</pre>
 
이를 기반으로 몇 가지 기능을 추가해 다음과 같은 식으로 만들 수 있습니다. 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
public class CircularQueue&lt;T&gt;
{
 private T[] _elements;
 private int _front;
 private int _rear;
 private int _max;
 private int _count;

public int Count =&gt; _count;
    public int Size =&gt; _max;

public CircularQueue(int size)
    {
        _elements = new T[size];
        _front = 0;
        _rear = -1;
        _max = size;
        _count = 0;
    }

public T PeekHead()
    {
        if (_count == 0)
        {
            return default(T);
        }

return _elements[_rear];
    }

public T PeekTail()
    {
        if (_count == 0)
        {
            return default(T);
        }

return _elements[_front];
    }

public void Enqueue(T item)
    {
        if (_count == _max)
        {
            Dequeue();
        }

_rear = (_rear + 1) % _max;
        _elements[_rear] = item;

_count++;
    }

public T Dequeue()
    {
        if (_count == 0)
        {
            return default(T);
        }
        else
        {
            T elem = _elements[_front];

_front = (_front + 1) % _max;
            _count--;

return elem;
        }
    }

public T[] GetElements(bool reverse = false)
    {
        T[] values = new T[_count];
        CopyTo(values, reverse);
        return values;
    }

public void CopyTo(T[] targetArray, bool reverse = false)
    {
        int targetPos = 0;

int j = 0;
        for (int i = _front; j &lt; _count;)
        {
            targetArray[targetPos++] = _elements[i];
            i = (i + 1) % _max;
            j++;
        }

if (reverse)
        {
            Array.Reverse(targetArray);
        }
    }

public override string ToString()
    {
        if (_count == 0)
        {
            return string.Empty;
        }

T[] values = GetElements();
 return string.Join(",", values);
 }
}
</pre>
 
아울러, 단위 테스트 등으로 다음과 같은 식의 코드를 추가하면 안정성도 높일 수 있습니다. ^^ 
 
<pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' >
using System.Diagnostics;
using System.Linq;

namespace ConsoleApp2
{
    internal class Program
    {
        static void Main(string[] args)
        {
            CircularQueue&lt;int?&gt; cq = new CircularQueue&lt;int?&gt;(3);

{
                Debug.Assert(cq.Capacity == 3);
                Debug.Assert(cq.PeekHead() == null);
                Debug.Assert(cq.PeekTail() == null);
                Debug.Assert(cq.Count == 0);
                Debug.Assert(Enumerable.SequenceEqual(cq.GetElements(), []));
                Debug.Assert(cq.Dequeue() == null);
            }

{
                cq.Enqueue(0);
                Debug.Assert(cq.PeekHead() == 0);
                Debug.Assert(cq.PeekTail() == 0);
                Debug.Assert(cq.ToString() == "0");
            }

{
                cq.Enqueue(1);
                cq.Enqueue(2);
                cq.Enqueue(3);
                cq.Enqueue(4);
                Debug.Assert(cq.PeekHead() == 4);
                Debug.Assert(cq.PeekTail() == 2);
                Debug.Assert(cq.ToString() == "2,3,4");
            }

{
                int? elem = cq.Dequeue();
                Debug.Assert(elem == 2);
            }

{
                cq.Enqueue(5);

int?[] values = new int?[cq.Count];
                cq.CopyTo(values, reverse: true);
                Debug.Assert(Enumerable.SequenceEqual(values, [5, 4, 3]));
            }

{
 cq.Enqueue(6);
 int?[] values = cq.GetElements();
 Debug.Assert(Enumerable.SequenceEqual(values, [4, 5, 6]));
 }
 }
 }
}
</pre>
 
(첨부 파일은 이 글의 예제 코드를 포함합니다.)

<hr />[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]

</div>

첨부파일

스팸 방지용 인증 번호

1187 (왼쪽의 숫자를 입력해야 합니다.)