[C# / Collection] Queue<T> 분석

C# Collection에 속한 Queue<T>에 관한 글입니다.

특별히 List처럼 안의 값을 바꾸거나, 정렬 등등을 하는 데 사용하지는 않습니다만,

여러 알고리즘에 사용하고 있는 중요한 자료구조중 하나입니다.

알고리즘뿐만 아니라 개발에도 사용할 수 있을 것 같습니다.

 

이 글은 완벽한 성능 분석글이 아닙니다. 단순히 C#의 MSDN에서 중요하다고 생각하는 부분이나, 평소 C++을 사용하면서 STL의 Queue에서 사용했던 것 중 유용하고 자주 사용했던 부분을 설명할 예정입니다.

참고하는 부분은 MSDN의 C# Collection Queue내용입니다. 틀린 부분은 댓글을 달아주시면 확인 후 수정하도록 하겠습니다. ^^

---

 

1. Queue<T>의 특성

C++의 Queue와 같은 역할을 합니다. FIFO 이런 거는 다 알고 계시겠죠?! (넘어가고 그 부분은), 자유롭게 enque, deque를 할 수 있고 메모리 관리도 해줍니다. BFS, 또 BFS를 응용한 알고리즘 등에 대표적으로 사용됩니다. 그냥 구현, 시뮬레이션 문제에서도 사용될 수 있습니다. 특~~별히 어려운 조작은 없기 때문에 간단하게 배울 수 있으니 꼭 알아두시면 좋습니다.

 

역할이 정확히 C++의 Queue와 같은 역할을 하고 사용처도 같기 때문에, 조작에 대해서 같은 부분은 간단히 한 번 사용해보면서, 또 다른 부분은 집중적으로 파보도록 하겠습니다.

 

 

 

2. Queue<T>의 구성

주로 사용하는 부분을 위주로 설명하겠습니다.

 

2.1) 생성자

List처럼, 처음부터 Capacity를 지정해주거나, dafault로 초기화해주거나, 배열에 담긴 데이터를 그대로 Queue에 넣어 초기화할 수 있습니다.

참고로, IEnumerable<T>을 구현하고 있어서 foreach사용이 가능합니다.

신기하게 Capacity개념은 존재하고, 새 원소를 넣을 때 동적으로 메모리를 확보할 때 Capacity를 사용하는데 멤버 변수는 없었습니다..(접근 못하는 것일 수도 있습니다.)

 

using System;
using System.Collections.Generic;

namespace ConsoleApp1
{
    class Data
    {
        public Data(int a_, int b_) { a = a_; b = b_; }
        public int a { get; set; }
        public int b { get; set; }
    }

    class cstest
    {
        static void Main(string[] args)
        {
            Data[] arr = new Data []{ new Data(1, 2), new Data(3, 4), new Data(5, 6) };


            Queue<Data> q1 = new Queue<Data>(); //default
            Queue<Data> q2 = new Queue<Data>(10);   //Capacity (int)
            Queue<Data> q3 = new Queue<Data>(arr); //array

            Console.WriteLine("----------q1----------");
            Console.WriteLine($"q1.Count = {q1.Count}");    //C++의 Size와 같음.
            Console.Write("Data : ");
            foreach (Data item in q1)
                Console.Write($"({item.a},{item.b}) ");

            Console.WriteLine("\n\n----------q2----------");
            Console.WriteLine($"q2.Count = {q2.Count}");    
            Console.Write("Data : ");
            foreach (Data item in q2)
                Console.Write($"({item.a},{item.b}) ");

            Console.WriteLine("\n\n----------q3----------");
            Console.WriteLine($"q3.Count = {q3.Count}");
            Console.Write("Data : ");
            foreach (Data item in q3)
                Console.Write($"({item.a},{item.b}) ");

            return;
        }
    }
}

 

실행결과

사용해야 할 Capacity를 사전에 알고 있다면 미리 확보하는 것이 성능 향상에 도움이 됩니다. 아무래도 Queue 같은 경우는 Default 생성자를 많이 사용하기 때문에 기본 생성자만 알아도 사용에는 지장이 없을 것으로 생각됩니다.

 

2.2) Count 

중요 멤버 변수인 Count는 C++ Queue의 Size와 같습니다. 

 

 

2.3) Method

Queue 하면 C++에서의 Push, pop, front이 정도만 알아도 불편함 없이 큐를 다 조작할 수 있었습니다. 거기에 대응하는 C#의 Method는 Enqueue = push, Dequeue = pop, Peek = front가 있습니다. 그 외 Contain이나, Clear 같은 것은 넘어가겠습니다. 

 

using System;
using System.Collections.Generic;

namespace ConsoleApp1
{
    class Data
    {
        public Data(int a_, int b_) { a = a_; b = b_; }
        public int a { get; set; }
        public int b { get; set; }
    }

    class cstest
    {
        static void Main(string[] args)
        {
            Queue<Data> q = new Queue<Data>(); //default

            Console.WriteLine("----------q----------");
            Console.WriteLine($"q.Count = {q.Count}");    
            Console.Write("Data : ");
            foreach (Data item in q)
                Console.Write($"({item.a},{item.b}) ");

            q.Enqueue(new Data(1, 2));
            q.Enqueue(new Data(3, 4));
            q.Enqueue(new Data(5, 6));
            q.Enqueue(new Data(7, 8));
            q.Enqueue(new Data(9, 10));

            Console.WriteLine("\n\n---(Enqueue x5 완료)---");
            Console.WriteLine($"q.Count = {q.Count}");    
            Console.Write("Data : ");
            foreach (Data item in q)
                Console.Write($"({item.a},{item.b}) ");

            Console.WriteLine("\n\n---(Dequeue 1회 실행)---");
            Data dat; // Data의 참조변수 
            dat = q.Dequeue();
            Console.WriteLine($"dat : ({dat.a},{dat.b}) ");
            Console.WriteLine($"q.Count = {q.Count}");
            Console.Write("Data : ");
            foreach (Data item in q)
                Console.Write($"({item.a},{item.b}) ");

            Console.WriteLine($"\nq.Peek() : ({q.Peek().a},{q.Peek().b})");

            return;
        }
    }
}

실행결과

Enqueue의 매개변수에 new로 Data변수를 생성하여 넘겨줍니다.

그럼 Queue에 객체들이 차곡차곡 들어갑니다. C++과 다르게 Queue의 내용을 순차적으로 읽을 수 있습니다.

 

Dequeue를 실행하면 가장 먼저 들어간 객체를 꺼내고 삭제합니다. C++에 비유하자면 front()와 pop()을 동시에 한 효과를 냅니다.

 

Peek은 C++에서 front()와 똑같이 작동합니다.

 

---

마치며...

Queue는 정말 어렵지 않습니다. 생성자도 여러 개 중에 Default생성자를 주로 많이 쓰고, 삽입, 삭제, 가장 앞에 있는 원소 참조. 이 3가지 동작을 주로 사용하기 때문에 정말정말정말x100 간단하게 사용할 수 있습니다. 단순한 개발에서는 사용 안 할지 몰라도 언젠간 꼭 필요하게 될 것이니 이런 것도 있구나~라고 생각하시면 될 것 같습니다. 평소 알고리즘 문제 풀이를 즐겨하시는 분이라면 필수로 알고 계셔야 합니다. 대부분 C++이나 자바, python을 쓰시겠지만.. ㅠ

 

 

댓글, 지적 환영입니다. :)