Microsoft MVP성태의 닷넷 이야기
닷넷: 2230. C# - 덮어쓰기 가능한 환형 큐 (Circular queue) [링크 복사], [링크+제목 복사],
조회: 13336
글쓴 사람
정성태 (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

비밀번호

댓글 작성자
 




1  2  3  4  [5]  6  7  8  9  10  11  12  13  14  15  ...
NoWriterDateCnt.TitleFile(s)
13862정성태1/13/20255100Linux: 112. Linux - 데몬을 위한 SELinux 보안 정책 설정
13861정성태1/11/20255326Windows: 276. 명령행에서 원격 서비스를 동기/비동기로 시작/중지
13860정성태1/10/20254788디버깅 기술: 216. WinDbg - 2가지 유형의 식 평가 방법(MASM, C++)
13859정성태1/9/20255701디버깅 기술: 215. Windbg - syscall 이후 실행되는 KiSystemCall64 함수 및 SSDT 디버깅
13858정성태1/8/20255867개발 환경 구성: 738. PowerShell - 원격 호출 시 "powershell.exe"가 아닌 "pwsh.exe" 환경으로 명령어를 실행하는 방법
13857정성태1/7/20256088C/C++: 187. Golang - 콘솔 응용 프로그램을 Linux 데몬 서비스를 지원하도록 변경파일 다운로드1
13856정성태1/6/20254747디버깅 기술: 214. Windbg - syscall 단계까지의 Win32 API 호출 (예: Sleep)
13855정성태12/28/20246563오류 유형: 941. Golang - os.StartProcess() 사용 시 오류 정리
13854정성태12/27/20246469C/C++: 186. Golang - 콘솔 응용 프로그램을 NT 서비스를 지원하도록 변경파일 다운로드1
13853정성태12/26/20245187디버깅 기술: 213. Windbg - swapgs 명령어와 (Ring 0 커널 모드의) FS, GS Segment 레지스터
13852정성태12/25/20246542디버깅 기술: 212. Windbg - (Ring 3 사용자 모드의) FS, GS Segment 레지스터파일 다운로드1
13851정성태12/23/20245501디버깅 기술: 211. Windbg - 커널 모드 디버깅 상태에서 사용자 프로그램을 디버깅하는 방법
13850정성태12/23/20246903오류 유형: 940. "Application Information" 서비스를 중지한 경우, "This file does not have an app associated with it for performing this action."
13849정성태12/20/20246915디버깅 기술: 210. Windbg - 논리(가상) 주소를 Segmentation을 거쳐 선형 주소로 변경
13848정성태12/18/20246302디버깅 기술: 209. Windbg로 알아보는 Prototype PTE파일 다운로드2
13847정성태12/18/20246226오류 유형: 939. golang - 빌드 시 "unknown directive: toolchain" 오류 빌드 시 이런 오류가 발생한다면?
13846정성태12/17/20246946디버깅 기술: 208. Windbg로 알아보는 Trans/Soft PTE와 2가지 Page Fault 유형파일 다운로드1
13845정성태12/16/20245522디버깅 기술: 207. Windbg로 알아보는 PTE (_MMPTE)
13844정성태12/14/20247531디버깅 기술: 206. Windbg로 알아보는 PFN (_MMPFN)파일 다운로드1
13843정성태12/13/20245595오류 유형: 938. Docker container 내에서 빌드 시 error MSB3021: Unable to copy file "..." to "...". Access to the path '...' is denied.
13842정성태12/12/20245785디버깅 기술: 205. Windbg - KPCR, KPRCB
13841정성태12/11/20246509오류 유형: 937. error MSB4044: The "ValidateValidArchitecture" task was not given a value for the required parameter "RemoteTarget"
13840정성태12/11/20245713오류 유형: 936. msbuild - Your project file doesn't list 'win' as a "RuntimeIdentifier"
13839정성태12/11/20246813오류 유형: 936. msbuild - error CS1617: Invalid option '12.0' for /langversion. Use '/langversion:?' to list supported values.
13838정성태12/4/20246417오류 유형: 935. Windbg - Breakpoint 0's offset expression evaluation failed.
13837정성태12/3/20247272디버깅 기술: 204. Windbg - 윈도우 핸들 테이블 (3) - Windows 10 이상인 경우
1  2  3  4  [5]  6  7  8  9  10  11  12  13  14  15  ...