[자료구조] 큐(Queue)

 

큐

• 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조
• 먼저 들어간 원소가 먼저 나온다. (FIFO구조)

 

큐 성질

• 원소 추가 : O(1)
• 원소 제거 : O(1)
• 제일 앞, 뒤 원소 확인 : O(1)
• 제일 앞, 뒤가 아닌 나머지 원소들의 확인, 변경이 원칙적으로 불가능 (배열로 구현하면 나머지 원소 확인, 변경 가능함)

 

큐 구현

 

배열 구현

internal class 큐_구현
{
    public const int MX = 1000005;
    public static int[] dat = new int[MX];
    public static int head = 0;
    public static int tail = 0;

    public static void Push(int x)
    {
        dat[tail++] = x;
    }

    public static void Pop()
    {
        head++;
    }

    public static int Front()
    {
        return dat[head];
    }

    public static int Back()
    {
        return dat[tail - 1];
    }

    public static void Test()
    {

    }

    static void Main(string[] args)
    {

    }
}

 

 

배열로 스택을 구현하면 원소들을 추가할 때마다 사용하지 않지 않는 공간이 생긴다. 

삽입할 원소의 개수가 배열의 크기를 초과하면, 배열에 더이상 원소를 삽입할 수 없게된다. (선형 큐 단점)

 

선형 큐의 단점은 원형큐로 해결할 수 있다. 

원형큐는 큐 배열을 원형으로 만들면 된다. (원형큐 = 배열 길이를 벗어나려 할때 0번지로 다시 돌아오는 큐)

 

하지만 코딩테스트에서는 push 최대횟수 정해져 있다.

배열 크기를 push 최대횟수보다 크게 두면, 원형큐를 만들지 않아도 된다. (배열 크기를 충분히 크게 두면 굳이 원형큐를 사용하지 않아도 된다)