[자료구조] 큐(Queue)

큐(Queue)

-먼저 추가된 데이터가 먼저 출력되는 FIFO(First In First Out) 자료 구조로서 입력된 순서대로 처리해야 하는 상황에 이용된다.

-Queue는 맨 뒤(tail)에 데이터를 계속 추가하고, 맨 앞(head)에서만 데이터를 읽기 때문에 순차적으로 데이터 처리한다.

 

Queue 클래스

-.NET에는 큐를 Non-Generic인 Queue 클래스와 Generic 형태인 Queue<T> 클래스가 있다.

-두 Queue 클래스는 내부적으로 순환 배열로 구현되어 있는데, 배열의 마지막 요소에 다다른 경우 다시 배열 처음 요소로 순환하는 구조 (next % array_size)를 가지고 있다.

-Queue는 내부적으로 head와 tail 포인터를 가지고 있는데, tail에 데이터를 추가(Enqueue)하고 head에서 데이터를 읽고 제거(Dequeue)한다.

-데이터 양이 많아 순환 배열이 모두 찰 경우, Queue는 capacity를 2배로(default growth factor가 2이기 때문) 증가 시키고, 모든 배열 요소를 새 순환 배열에 자동으로 복사하여 Queue를 확장한다.

 

사용 예제

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;

class Program
{
    static void Main(string[] args)
    {
        Queue<string> q = new Queue<string>();
        q.Enqueue("입니다");
        q.Enqueue("안녕하세요");
        q.Enqueue("저는");
        string temp = q.Dequeue(); //"입니다"가 temp에 쓰여짐
        q.Enqueue("Dev_Hugh");
        q.Enqueue(temp);
        foreach(string str in q)
        {
            Console.WriteLine(str + " "); //output: 안녕하세요 저는 Dev_Hugh 입니다
        }
    }
}