[자료구조] Queue란? (+Circular Queue, Priority Queue, Deque)

🚦 이번 포스팅에서는 〰️

▶️ 큐(Queue)란?
▶️ 큐(Queue) functions - C++
▶️ 큐(Queue) 구현 방법
▶️ 원형 큐(Circular Queue)에 대해서
▶️ 우선순위 큐(Priority Queue)에 대해서
▶️ 덱(Deque)에 대해서
▶️ 큐(Queue) 사용 사례
▶️ 스택(Stack) vs 리스트(List) vs 큐(Queue)

 

📎 큐(Queue) 란?

---

먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로)구조로 저장하는 형식을 말한다.

영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.

이는 나중에 집어넣은 데이터가 먼저 나오는 스택(Stack)과는 반대되는 개념이다.

이외에도 프린터의 출력 처리나 윈도우 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.

스택과 큐의 차이

 

📎 큐(Queue) functions - C++

---

큐는 FIFO(First In First Out) 형태로, 가장 먼저 추가된 큐 항목이 가장 먼저 나오는 형식이다.

입력은 Enqueue, 출력은 Dequeue라고 표현하며, front에 위치한 데이터 조회는 Peek이라고 한다.

• push : 큐의 맨 뒤에 항목을 추가한다.
• pop : 큐의 가장 먼저 들어온 항목을 제거한다.
• empty : 큐가 비어있을 때 true 반환한다.
• front : 큐의 첫 번째 항목을 접근한다.
• back : 큐의 마지막 항목에 접근한다.
• size : 큐의 사이즈를 반환한다.
• emplace : 큐에 별다른 변수 선언 없이 바로 추가한다.
• swap : 큐끼리 바꾼다.

 

 

📎 큐(Queue) 구현 방법

---

스택(Stack)처럼 배열을 사용해서 구현한다면 입력(Enqueue) 및 출력(Dequeue)을 할 때마다 데이터가 앞으로 밀려나가는 문제가 생긴다.

⏩️ 연결리스트를 사용하면 배열에 비해 쉽게 구현이 가능하다.

⏩️ 이를 선형 큐의 문제점이라고 할 수 있는데, 삽입 및 삭제를 반복하다 보면 rear가 마지막 인덱스를 가리켜 앞에는 비어있을 수 있지만 rear가 마지막 인덱스이기 때문에 꽉 찼다고 인식할 수 있다.

선형 큐

❕이것을 해결하기 위해 시작 부분과 끝 부분을 포인터로 지정한 뒤 입, 출력을 하는 형태의 원형 큐(원형 버퍼)를 이용한다.

 

 

📎 원형 큐(Circular Queue)에 대해서

---

⏩️ 배열로 큐를 사용할 때, Dequeue(pop) 시 배열의 앞부분이 비는 것을 활용하기 위해 배열의 맨 마지막 부분을 채우면 다시 처음부터 큐를 채우기 시작하는 형태를 가진 큐이다.

⏩️ 기존 큐와 동일하지만 마지막 위치가 시작 위치와 연결되는 원형 구조를 띤다.

⏩️ Enqueue를 하게 되면 rear포인터가 앞으로 이동하고, Dequeue를 하게 되면 front 포인터가 앞으로 이동한다.

⏩️ front와 rear의 값이 같다면 원형 큐는 다 채워졌다고 본다. (다 비워진 상태도 front와 rear값이 같은데, 이를 구분하기 위해 front=rear=-1이라면 비워진 상태로 본다.)

 

 

📌 원형 큐의 구현코드

class Queue {
	int rear, front;
    
    //Circular Queue
    int size;
    int *arr;

public:
	Queue(int s) {
    	front = rear = -1;
        size = s;
        arr = new int[s];
    }
    void enQueue(int value);
    int deQueue();
    void printQueue();
};

void Queue::enQueue(int value) {
	//Queue가 다 찼을 때
	if((front==0 && rear==size-1) || ((rear+1)%size == front)) {
    	cout << "Queue is Full" << "\n";
        return;
    }
    else if (front == -1) { //Queue가 비워져있음->첫번째 값을 넣는다.
    	front = rear = 0;
        arr[rear] = value; //rear가 돌아가면서 값 채워준다.
    }
    else if (rear==size-1 && front!=0) { //Queue가 pop되었을때
    	rear = 0;
        arr[rear] = value;
    }
    else { //나머지는 rear가 옮겨가면서 버퍼에 데이터를 채움.
    	rear++;
        arr[rear] = value;
    }
}

int Queue::deQueue() {
	if(front==-1) {
    	cout << "Queue is Empty" << "\n";
        return INT_MIN;
    }
    int data = arr[front];
    arr[front] = -1; //데이터 초기화.
    if(front==rear) { //데이터가 1개. pop하고 초기상태로 돌아가기.
    	front = -1;
        rear = -1;
    }
    else if(front==size-1) //front==size-1이라는건 이전의 모든 데이터가 pop되었고, 마지막 데이터라는뜻
    	front = 0; //버퍼 마지막이므로 0으로 이동해줌.
    else
    	front++; //front 옮겨가면서 pop처리
    
    return data;
}

void Queue::printQueue() {
	if(front==-1) {
    	cout << "Queue is Empty" << "\n";
        return;
    }
    if(rear>=front) {
    	for(int i=front; i<=rear; i++) cout << arr[i] << " ";
    }
    else {
    	for(int i=front; i<size; i++) cout << arr[i] << " ";
        for(int i=0; i<=rear; i++) cout << arr[i] << " ";
    }
}

 

 

 

📎 우선순위 큐(Priority Queue)에 대해서

---

우선순위 큐는 각각의 데이터에 우선순위를 매겨서 본래 큐의 성질인 선입선출과 관계없이 우선순위가 높은 원소부터 Dequeue 하는 큐이다.

우선순위 큐를 이용하는 대표적인 예시는 자료구조 Heap이 있다.

자세한 내용은 [자료구조] Heap이란? 에서 다룬다.

 

 

 

📎 덱(Deque)에 대해서

---

덱(Deque)이란 Double Ended Queue의 준말로, 앞뒤에서 모두 입력과 출력이 가능한 형태이다.

스택과 큐는 상황에 맞는 목적에 사용되는 자료구조라는 느낌이 들었던 반면, 자유도가 매우 높아진 덱은 여러가지 용도에 부합될 수 있다.

그러나, 실제로 양쪽의 입력과 출력을 모두 사용하는 경우는 거의 없다고 한다.

 

보통, 두가지 타입 중 하나로 사용하게 되는데, 입력을 제한 덱 또는 출력 제한 덱 방식으로 많이 사용한다.

즉, 큐를 구현했지만 양쪽에서 출력을 하고싶거나 / 스택을 구현했지만 양쪽에서 입력하고 싶은 경우 많이 사용한다.

 

덱의 구조

 

덱(Deque)의 연산들

• push_back
• push_front
• pop_back
• pop_front
• insert
• erase... 등등

 

📎 큐(Queue) 사용 사례

---

🔅 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다. (선입선출)

 

⏩️ BFS(너비 우선 탐색) 구현

• 처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용한다.
• 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
• 접근한 노드 순서대로 처리할 수 있다.

⏩️ Cache(캐시) 구현

⏩️ 우선순위가 같은 작업 예약 (인쇄 대기열)

⏩️ 선입선출이 필요한 대기열 (창구, 티켓 카운터)

⏩️ 콜센터 고객 대기시간

⏩️ 프린터의 출력 처리

⏩️ 윈도우 시스템의 메세지 처리기

⏩️ 프로세스 관리

 

 

📎 스택(Stack) vs 리스트(List) vs 큐(Queue)

---

	공통점	차이점
리스트 (List)	- 선형 자료구조    - 순서가 존재한다	read, insert, delete를 리스트의 어느 곳에서나 행한다.
스택 (Stack)		insert, delete를 리스트의 한쪽(top)에서 행한다.
큐 (Queue)		insert는 리스트의 한쪽(rear)에서 행하고, delete는 반대쪽(front)에서 행한다.

 

 

🔆 [자료구조] 다른 Posting 보러 가기 🔆

✅ 스택(Stack)이란?

✅ 힙(Heap)이란?

 

 

[참고]

https://cplusplus.com/reference/queue/queue/?kw=queue 

https://www.geeksforgeeks.org/introduction-to-circular-queue/

https://gmlwjd9405.github.io/2018/08/02/data-structure-queue.html

https://min-nine.tistory.com/206