Queue ADT

Queue는 FIFO(First-In First-Out)의 특성을 같는 저장 공간을 의미합니다.

이것은 Stack과 다르게 양쪽이 뚫려있는 프링글스 통으로 생각해보면 되겠습니다. 이때 양쪽의 역할은 입력과 출력으로 각각 정해져 있다고 생각합시다.

아, 예를들어 왕복 1차선 터널을 생각해보면 되겠네요! 먼저 들어간 차가 먼저 나와야하죠

Main Operation

위의 정의로부터 다음의 함수는 Queue에 반드시 존재해야 함을 알 수 있습니다.

• push()
  Queue의 rear에 값을 추가하는 함수입니다.

이 push()의 과정을 enqueue()라고도 합니다.

• pop()
  Queue의 front에 값을 삭제하는 함수입니다.

이 pop()의 과정을 dequeue()라고도 함

Auxiliary Operation

위의 함수 외에도 다음과 같은 함수가 존재할 수 있을 것입니다.

• size()
  Queue가 얼마나 차 있는지 알 수 있는 함수입니다.

• isEmpty()
  Queue가 비어있는지 확인하는 함수입니다.

• first()
  Queue의 첫번째 값을 return 하는 함수입니다.

Pros & Cons

장점

• 공간 복잡도함수는 O(n)이다

• Queue의 기능을 수 행하는 각 함수의 시간 복잡도는 O(1)이다.

단점(한계)

• a Priori: 우리가 사용할 Queue의 크기를 미리 아는것이 불가능하다. 즉 쓸데 없는 공간의 낭비가 생길 수 있다.

해결방법

• Full Exception을 일으키면 크기를 doubling해준다.

• linked list를 이용하여 해결한다.

구현

ArrayVector로 구현하기

Stack과는 다르게 Queue는 양쪽에서 추가와 삭제가 일어나기 때문에 원소들의 위치가 수시로 변하겠죠?

즉, 만약 배열로 Queue를 구현하기위해서는 우선 다음을 결정해 줍시다.

Linear Queue

배열의 enqueue()와 dequeue()가 실행되는 방향이 일정한 Queue를 말한다.

• 장점: 구현이 쉽다.

• 단점: 저장공간을 효율적으로 활용할 수 없다.

Circular Queue

여러번 사용하여 enqueue()와 dequeue를 통해 주어진 배열의 크기를 벗어나면 처음부터 다시 채우는 Queue를 말한다.

List로 구현하기

Singly Linked List

void enqueue(const Object& e) {
    Node* v = new Node(e, NULL);
    if(size==0)
        head = v;
    else
        tail->next = v;
    tail = v;
    size++;
}
// tail에 enqueue를 해줘야함!

void dequeue() {
    if(!empty()){
        Node* temp = head;
        head = head->next;
        if(--size==0)
            tail = NULL;
        delete temp;
    }
}

Doubly Linked List