자료구조: 큐(Queue)

큐 (Queue)

이 정리는 위키백과를 참고하였습니다.

• FIFO: 선입선출(First In First Out), 제일 먼저 들어간 것이 제일 먼저 나간다는 뜻입니다.
  • 예시: 카페 주문, 선입선출 물건 판매 (유통기한)
• 큐는 양 쪽 끝에서 자료를 넣거나 뺄 수 있는 선형의 자료 구조입니다.
  • 하지만 한 쪽(rear)에서는 삽입만, 반대쪽(front)에서는 삭제만 일어납니다.
• 맨 처음에 들어온 데이터의 위치를 front (혹은 first)이라고 합니다.
• 큐는 그래프 자료구조 탐색방법 중 BFS(Breath First Search, 깊이우선 탐색)에 쓰입니다.
• 그 외에 CPU 스케쥴링 등의 프로세스, 자원을 공유하는 대부분의 경우에 큐가 사용됩니다.
• 기본적으로 추상 자료형(Abstract Data Type, ADT)이지만 여기서는 자료 구조의 영역까지 다룰 것입니다. (구현까지)

 

구현 방법 - Stack과 동일

1. 1차원 배열: 구현하기 쉽지만 input의 개수를 알아야 합니다.
2. 연결 리스트: 구현이 배열보다 어렵고 메모리를 좀 더 사용하지만, 유동적으로 input에 대처할 수 있습니다.

 

함수

가장 보편적으로 사용되는 함수를 골라보았습니다. 이외에 size()등의 함수들도 사용자가 정의하여 쓸 수 있습니다.

• Q.front(): 큐의 가장 앞 데이터(front)를 반환합니다.
• Q.deque(): first을 반환하고 스택에서 삭제합니다.
• Q.enque(): 큐의 끝에(rear) 새로운 데이터를 삽입합니다.
• Q.isEmpty(): 큐가 비었으면 True, 아니면 False을 반환합니다.

 

큐 구현 코드 (Python, C++)

• Python: 큐 라이브러리가 따로 존재하지만 list를 이용하여 구현해 보았습니다.
  • 파이썬에서는 리스트에서 remove를 할 때마다 자동으로 인덱스가 조정되기 때문에 항상 0 위치의 원소를 deque하거나 front할 때 사용했습니다.

class queue:
    def __init__(self):
        self.items = []
    def enque(self, item):
        self.items.append(item)
    def deque(self):
        tmp = self.items[0]                        # 첫 번째 원소 tmp에 저장
        self.items.remove(tmp)                    # item에서 삭제
        return tmp                                # tmp 반환
    def isEmpty(self):
        return not self.items
    def front(self):
        return self.items[0]                    # 첫 번째 원소 반환

q = queue()
print(q.isEmpty())                                # True 출력
q.enque(1)
q.enque(2)
print(q.deque())                                # 1 출력
q.enque(3)
print(q.front())                                # 2 출력
print(q.isEmpty())                                # False 출력

• C++: 노드를 이용한 연결리스트로 스택을 구현해 보았습니다.

#include <iostream>

using namespace std;

struct Node {
    int data;
    Node* next;
    Node() {
        next = NULL;
        data = 0;
    }

    Node(int i, Node* ptr) {
        data = i;
        next = ptr->next;
        ptr->next = this;
    }
};

struct Queue {
    Node* first;
    Node* rear;                                // 큐에는 맨 뒤를 가리키는 포인터 필요
    int count;
    Queue() {
        first = new Node();
        rear = new Node();                    // 둘 다 next값을 NULL로 초기화
        count = 0;
    }

    int deque() {
        if (count != 0) {
            int res = first->data;
            first = first->next;
            count--;
            return res;
        }
    }

    int front() {
        if (count != 0) {
            return first->data;
        }
    }

    bool isEmpty() {
        if (count == 0) {
            return true;
        }
        else return false;
    }

    void enque(int data) {                    // 스택과 다른 삽입과정
        Node* node = new Node();
        node->data = data;
        node->next = NULL;                    // 삽입될 노드의 next값을 NULL로 설정
        if (count == 0) {                    // 첫 숫자일 때 첫 번째 노드로 설정
            first = node;
        }
        else {                                // 기존 rear의 next값을 현 node로 갱신
            rear->next = node;
        }
        rear = node;                        // 맨 마지막을 node로 갱신(공통)
        count++;
    }
};

int main() {
    Queue* q = new Queue();
    cout << q->isEmpty() << '\n';            // 1 출력
    q->enque(1);
    q->enque(2);
    cout << q->deque() << '\n';                // 1 출력
    q->enque(3);
    cout << q->front() << '\n';                // 2 출력
    cout << q->isEmpty() << '\n';            // 0 출력
}

 

사담

오랜만에 자료구조를 보는데 C++로 노드랑 링크드 리스트 구현을 하는 게 너무 새롭네요..

그 때는 주먹구구 암기식으로 외웠던 것 같은데 포스팅의 장점은 정말 이해하려고 노력하게 만든다는 점 같아요🙌🙌

직접 구현해보는 게 중요하다는 말이 뭔지 이제야 알 것 같습니다!!