큐 (Queue)

강성원·2024년 1월 12일

자료구조

기본기(알고리즘, 자료구조)

목록 보기

2/8

원형 큐에 대해 작성하며 큐에 대해 설명하다보니 길어져서 그냥 따로 빼놓기로 했다.

큐(Queue)란?

큐는 먼저 들어온 원소가 먼저 나가는 '선입선출' 구조를 가지고 있다.
놀이기구 대기줄을 생각하면 된다.

삽입(Enqueue) / 추출(Dequeue)

큐에는 원소를 넣고 빼는 것을 Enqueue, Dequeue라고 한다.

Enqueue 과정

Enqueue를 진행하면 Rear가 1 증가하고, 그 Rear를 인덱스로 삼아 원소를 추가하게된다.
ex) arr[++Rear] = 10;

Enqueue (삽입) 과정
Rear가 한 칸 증가하며 마지막 원소를 가리킨다.

Enqueue 조건

Enqueue를 하기 위해서는 큐가 꽉 찼는지 확인해야 한다.

큐의 포화상태는 (Rear + 1) == 배열 길이 가 참인 경우이다.

길이 5의 배열이 있다고 할 때 Rear가 맨 끝 인덱스인 4를 가리키는 상황이다.

이 상황에서 배열 길이 5와 Rear + 1 (4 + 1) 는 값이 같으므로 포화 상태이다.

Dequeue 과정

Enqueue를 진행하면 Front를 인덱스 삼아 원소를 빼오고, Front의 값을 증가시킨다.

Dequeue (추출) 과정
Front가 한 칸 증가하며 가장 앞 원소를 가리킨다.

Dequeue 조건

Dequeue가 되는 조건에는 여러 방법이 있겠지만
나는 Rear가 Front 이상일 때 Dequeue가 가능하도록 한다.

아래에 두 예시를 들겠다.

우선 배열의 초기 상태와 원소가 존재하지 않을 때 이다. Dequeue가 불가능하다.첫 사진과 두 번째 사진 모두 원소가 없어 Dequeue가 불가능하다.
Front와 Raer의 관계는 Front > Rear이다.

Front와 Rear가 같은 상황이다.이 경우에는 원소가 존재하므로 Dequeue가 가능하다.

구현

public class Queue<T>
{
    private T[] values;
    private int front = 0;
    private int rear = -1;

    public Queue(int length) 
    { 
        values = new T[length];
    }

    public void Enqueue(T data)// 뒤로 축적
    {
        if(IsFull())
        {
            Console.WriteLine("꽉 참");
            return;
        }
        //rear 증가
        values[++rear] = data;
    }

    public T Dequeue()// 앞 요소 추출
    {
        if(IsEmpty())
            throw new InvalidOperationException("큐가 비어있음");
        //front 증가
        return values[front++];
    }

    public bool IsFull()
    { return values.Length == rear + 1; }

    public bool IsEmpty()
    { return rear >= front; }

    public void Print()
    {
        for (int i = front; i <= rear; ++i)
        {
            Console.Write(values[i] + " ");
        }
    }
}