[자료구조] Queue - Array based vs Linked List

Queue

---

What is Queue?

큐(queue)는 스택과 달리 데이터를 줄 세우는 것이다. 즉 먼저 들어간 데이터가 먼저 나오는 형태의 선형자료구조를 말한다.

---

queue의 특징

• 먼저 들어간 데이터가 가장 먼저 나오게 된다 -> FIFO라고 함( First In First Out )

• 가장 앞에 위치한 데이터를 가리키는 front와 맨 뒤에 위치한 데이터를 가리키는 rear 두개의 변수가 필요하다.

---

queue class

Array Based vs Linked List

저번 stack의 내용과 비슷하게 배열과 LL 두가지 선형구조로 구현할 수 있다. queue 구현의 포인트는 데이터가 full인지 empty인지 구별하는 것이다. 그냥 구현을 하게 되면 rear+1=front  이 의미하는 바가 full인지 empty 인지 구별을 할 수 없다. 따라서 queue의 한 공간을 save storage로 두고 구현을 하는 방법으로 해결할 수 있다. 또한 데이터가 양쪽 방향에서 들어가고 나갈 수 있기 때문에 circular implement를 통해 공간을 활용할 수 있다.

 

---

Array based Queue implement

class queue {
public:
    queue(); // static 생성자
    queue(int n); // dynamic 생성자
    ~queue(); // dynamic 소멸자
    
    bool empty() const;
    bool full() const;
    void push(int item);
    void pop();
    
private:
    int front;
    int rear;
    int max; // queue의 크기
    
    int* items; // dynamic 구현
    int items[MAX]; // static 구현
};

 

• queue() -> static 생성자

  queue() {
      max = MAX; // 배열의 크기가 MAX일 때
      front = max - 1;
      rear = max - 1;
  }

배열의 사이즈를 MAX라고 하면, front와 rear는 MAX-1로 초기화 된다. 즉 가장 맨 마지막 노드를 가리킴

 

• queue(int n) -> dynamic 생성자

    queue(int n) {
        max = n;
        front = max - 1;
        rear = max - 1;
        items = new int(n);
    }

크기를 n으로 입력 받으면 new를 통해 items 할당해준다.

 

• ~queue

    ~queue() {
        delete[] items;
    }

마찬가지로 dynamic으로 heap영역에 할당을 해줬으니 소멸자를 통해 할당해제를 해준다.

 

여기까지는 stack과 비슷하게 진행되서 별로 어려운 내용이 없다. 이제 배울 empty와 full 함수를 이해하는 것이 queue 구현의 포인트이다.

 

 

• empty

    bool empty() const {
        return (rear == front);
    }

queue에 들어있는 데이터의 개수나, queue가 비어있는지 혹은 가득 차 있는지 확인하기 위해서는 front와 rear 변수의 관계를 잘 살펴야한다. 직관적으로 이해해보자. queue에 데이터가 없으면 rear와 front가 같을 것이다. 이 때 데이터가 하나인 경우도 front와 rear가 같지 않냐고 할 수 있는데 이 질문은 push 함수를 살펴보면서 해결하도록 하겠다.

 

• full

    bool full() const {
        return ((rear + 1) % max == front);
    }

여기서 주목할 점은 modulo연산과 rear+1 이다. 앞서 말했듯이 공간을 활용하기 위해 circular로 구현한 것이다. 예를 들어서 max=5 인 경우라면 배열의 인덱스 번호는 0~4이므로, 데이터가 4개가 있다고 하면 front=4 rear=3일 것이다. 이 상황에서 front는 save storage로 데이터를 저장을 할 수 없기 때문에 rear+1과 front의 값을 비교하는 것이다.

modulo 연산을 하게 되면 나머지만 구하는 것이므로 0~n-1의 값을 얻을 수 있다. 예를 들어서 modulo 5를 하면 0~4의 값을 얻는다. 4까지 진행하고 다시 0으로 돌아가기 때문에 circular 구현이다.

 

• push(int item)

    void push() {
        if (!full()) {
            rear = (rear + 1) % max;
            items[rear] = item;
        }
    }

push 함수에서 주목할 점은 save storage를 구현한 것이다. 데이터를 추가할 때 그냥 rear에 넣지 않고 rear+1 % max  값에 넣는 것으로 구현을 했다. 예를 들어 max=5 인 상황에서 들어있는 데이터의 개수가 0일 때, 맨 처음 rear와 front의 값은 4이다. 이 때 push를 하게 되면 items[4]는 건너 뛰고 items[0] 부터 데이터를 채운다. 따라서 front가 있는 items[4]는 save storage가 된다. 

따라서 empty 함수에서 생긴 '데이터가 하나일 때도 rear와 front는 같지 않냐' 는 질문은 save storage 구현으로 인해 답이 NO라고 할 수 있겠다. 그냥 queue만 보자면 그게 맞지만 구현에서는 달라야 한다.

 

• pop

    void pop() {
        if (!empty()) {
            front = (front + 1) % max;
        }
    }

push와 마찬가지로 circular 구현이고, save storage 구현이다. 데이터를 지울 때는 front의 값을 옮겨주기만 하면 된다. modulo연산을 통해 circular 구현을 했다. 이 때 주의할 점은 save storage는 고정되는 것이 아니라 front의 이동에 따라 위치가 바뀐다.

 

---

 

Linked List Queue implement

Linked List로 구현한 queue의 포인트는 front와 rear 두개의 포인터가 필요하다는 것이다.

class queue {
public:
    queue(); 
    ~queue(); 
    
    bool empty() const;
    bool full() const;
    void push(int item);
    void pop(int item);

private:
    Node* front; // front 노드의 주소를 가리킬 포인터
    Node* rear;	 // rear 노드의 주소를 가리킬 포인터
};

struct Node {
    int info;  // linked list로 구현한 데이터
    Node* next; // 데이터끼리 연결할 포인터
};

 

• queue 생성자

    queue() {
        front = NULL;
        rear = NULL;
    }

쉽다 쉬워 설명은 생략

 

• ~queue 소멸자

    ~queue() {
        while (front != NULL) {
            Node* node;
            node = front;
            front = front->next;
            delete node;
        }
        rear = NULL;
    }

queue 소멸자의 기본 아이디어도 stack과 같다. Node 객체를 하나 만들고 front를 넣어준다. front=front->next 를 통해 다음 front를 가리키도록 하고 Node 객체를 지워주면 맨 처음 front를 지운게 된다. 이 때 주의할 점은 rear = NULL 이다. 이 작업을 하지 않으면 rear는 댕글링 포인터가 된다. 댕글링 포인터란 해제된 영역을 가리키는 포인터를 말한다. 따라서 꼭 rear에 NULL 값을 넣어줘야 한다.

 

• empty

    bool empty() const {
        return (front == NULL);
    }

너무 쉽다 설명 생략

 

• full

    bool full() const {
        Node* node;
        try {
            node = new Node;
            delete node;
            return true;
        }
        catch (std::bad_alloc) {
            return false;
        }
    }

LL stack의 full 함수와 같은 구현이다. upper limit이 없기 때문에 heap 영역에 할당이 잘 되면 false, 문제가 생기면 bad_alloc 예외 처리를 한다.

 

• push

    void push(int item) {
        if (!full()) {
            Node* node = new Node;
            node->info = item;
            node->next = NULL;

            if (front == NULL)
                front = node;
            else
                rear->next = node;
            rear = node;
        }
    }

push 함수의 포인트는 맨 처음 데이터를 넣는 순간의 처리이다. queue에 들어있는 데이터의 개수가 0개이면 front도 NULL이므로 front를 이동시키는 과정이 필요하다. 따라서 if문을 통해서 맨 처음 데이터를 추가할 때를 고려해서 구현을 했다. 그 다음 push를 사용할 때에는 rear만 이동시키면 되기 때문에 현재 가리키고 있는 rear의 next에 새 node의 주소를 넣고 rear를 node로 바꿔준다. 항상 그렇지만 포인터를 사용할 때에는 코드의 순서와 사용하는 주소를 잘 생각해야한다.

 

• pop

    void pop() {
        if (!empty()) {
            Node* node;
            node = front;
            front = front->next;
            if (front == NULL) {
                rear = NULL;
            }
            delete node;
        }
    }

pop 함수에서도 포인트는 마지막 데이터를 삭제해서 empty가 되는 순간을 구현하는 것이다. Node 객체인 node를 하나 만들고 front 주소를 넣는다. 그 다음 front = front->next 를 통해서 front의 주소값을 옮겨준다. 이 때 데이터가 하나 밖에 없는 경우 front=NULL이 된다. 이 경우 데이터가 모두 삭제 되었다는 뜻이 되므로 (empty) rear=NULL 구문을 통해서댕글링 포인터가 되지 않도록 해야한다.

 

 

번외) Array Based queue에서 front와 rear 관계를 통한 데이터 길이 구하기

queue를 배열으로 구현을 한 경우 front와 rear의 관계를 잘 살펴보면 queue에 들어있는 데이터의 길이를 구할 수 있다.

이를 위해서는 먼저 두가지 경우로 나누어서 생각해야한다.

1. front < rear 이 경우 데이터가 들어왔다가 1번 이상은 삭제된 경우이다. 이럴 때는  rear - front 가 데이터의 길이가 된다.

2. front > rear 이 경우에는 인덱스 0에도 데이터가 있기 때문에 쉽게 maxQue-front+rear 을 해준다. 

---

stack과 queue모두 알아봤는데 queue가 좀 더 고려해야할 부분이 많기는 하다. 둘 다 모두 중요한 자료구조이므로 잘 알아두는 것이 좋다. 다음에는 진짜로 stack과 queue를 활용한 백준 문제 풀이를 들고오겠다