Microsoft MVP성태의 닷넷 이야기
닷넷: 2230. C# - 덮어쓰기 가능한 환형 큐 (Circular queue) [링크 복사], [링크+제목 복사],
조회: 13622
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일

C# - 덮어쓰기 가능한 환형 큐 (Circular queue)

간혹, 환형 큐인데 최대 크기를 채운 경우 마지막에 추가했던 값을 덮어쓰는 식의 동작이 필요한 경우가 있습니다.

이를 위해, List<T> 등을 기반으로 구현하면 편리하긴 한데 내부적으로 Append, Delete(0)을 하는 과정에 자꾸만 배열 복사가 발생할 수 있기 때문에 GC를 괴롭히게 된다는 단점이 있습니다.

따라서, 어차피 환형 큐이고 덮어쓰기를 허용한다면 연속적인 배열로 처리하는 것이 좋은데요, 여기서 유의할 점은 적절한 head/tail의 index 위치에 대한 연산입니다. 물론, 이미 그런 연산을 잘 해주는 코드는 검색만 하면 나오기 때문에, ^^

C# program to implement circular queue using array
; https://www.includehelp.com/dot-net/implement-circular-queue-using-array-using-c-sharp-program.aspx

이를 기반으로 몇 가지 기능을 추가해 다음과 같은 식으로 만들 수 있습니다.

public class CircularQueue<T>
{
    private T[] _elements;
    private int _front;
    private int _rear;
    private int _max;
    private int _count;

    public int Count => _count;
    public int Size => _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 < _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);
    }
}

아울러, 단위 테스트 등으로 다음과 같은 식의 코드를 추가하면 안정성도 높일 수 있습니다. ^^

using System.Diagnostics;
using System.Linq;

namespace ConsoleApp2
{
    internal class Program
    {
        static void Main(string[] args)
        {
            CircularQueue<int?> cq = new CircularQueue<int?>(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]));
            }
        }
    }
}

(첨부 파일은 이 글의 예제 코드를 포함합니다.)




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







[최초 등록일: ]
[최종 수정일: 3/11/2024]

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 작성자
 




... 91  92  [93]  94  95  96  97  98  99  100  101  102  103  104  105  ...
NoWriterDateCnt.TitleFile(s)
11653정성태8/14/201821592사물인터넷: 26. 입력 전압에 따른 LED의 전압/저항 변화 [1]파일 다운로드1
11652정성태8/14/201819019사물인터넷: 25. 컬렉터 9V, 베이스에 5V와 3.3V 전압으로 테스트하는 C1815 트랜지스터파일 다운로드1
11651정성태8/14/201825050사물인터넷: 24. 9V 전압에서 테스트하는 C1815 트랜지스터 [1]파일 다운로드3
11650정성태8/14/201819022사물인터넷: 23. 가변저항으로 분압파일 다운로드1
11649정성태8/12/201820731사물인터넷: 22. 저항에 따른 전류 테스트파일 다운로드1
11648정성태8/12/201822035사물인터넷: 21. 퓨즈를 이용한 회로 보호파일 다운로드3
11647정성태8/8/201823475오류 유형: 476. 음수의 음수는 여전히 음수가 되는 수(절대값이 음수인 수)
11646정성태8/8/201818178오류 유형: 475. gacutil.exe 실행 시 "Failure initializing gacutil" 오류 발생
11645정성태8/8/201821126오류 유형: 474. 닷넷 COM+ - Failed to load the runtime. [1]
11644정성태8/6/201824105디버깅 기술: 118. windbg - 닷넷 개발자를 위한 MEX Debugging Extension 소개
11643정성태8/6/201823952사물인터넷: 20. 아두이노 레오나르도 R3 호환 보드의 3.3v 핀의 LED 전압/전류 테스트 [1]파일 다운로드1
11642정성태8/3/201822024Graphics: 20. Unity - LightMode의 ForwardBase에 따른 _WorldSpaceLightPos0 값 변화
11641정성태8/3/201827443Graphics: 19. Unity로 실습하는 Shader (10) - 빌보드 구현 [1]파일 다운로드1
11640정성태8/3/201824156Graphics: 18. Unity - World matrix(unity_ObjectToWorld)로부터 Position, Rotation, Scale 값을 복원하는 방법파일 다운로드1
11639정성태8/2/201822177디버깅 기술: 117. windbg - 덤프 파일로부터 추출한 DLL을 참조하는 방법
11638정성태8/2/201820578오류 유형: 473. windbg - 덤프 파일로부터 추출한 DLL 참조 시 "Resolved file has a bad image, no metadata, or is otherwise inaccessible." 빌드 오류
11637정성태8/1/201825080Graphics: 17. Unity - World matrix(unity_ObjectToWorld)로부터 TRS(이동/회전/크기) 행렬로 복원하는 방법파일 다운로드1
11636정성태8/1/201831921Graphics: 16. 3D 공간에서 두 점이 이루는 각도 구하기파일 다운로드1
11635정성태8/1/201821036오류 유형: 472. C# 컴파일 오류 - Your project is not referencing the ".NETFramework,Version=v3.5" framework.
11634정성태8/1/201824190.NET Framework: 790. .NET Thread 상태가 Cooperative일 때 GC hang 현상 재현 방법파일 다운로드1
11633정성태7/29/201826975Graphics: 15. Unity - shader의 World matrix(unity_ObjectToWorld)를 수작업으로 구성 [2]파일 다운로드1
11632정성태7/28/201830409Graphics: 14. C# - Unity에서 캐릭터가 바라보는 방향을 기준으로 카메라의 위치 이동 및 회전하는 방법
11631정성태7/27/201831702Graphics: 13. Unity로 실습하는 Shader (9) - 투명 배경이 있는 텍스처 입히기 [1]
11630정성태7/27/201826936개발 환경 구성: 391. (GitHub 등과 직접 연동해) 소스 코드 디버깅을 쉽게 해 주는 SourceLink [3]
11629정성태7/26/201826340.NET Framework: 789. C# 컴파일 옵션 - Check for arithmetic overflow/underflow [2]
11628정성태7/25/201827630Graphics: 12. Unity로 실습하는 Shader (8) - 다중 패스(Multi-Pass Shader)
... 91  92  [93]  94  95  96  97  98  99  100  101  102  103  104  105  ...