[자료구조] 큐

큐(queue)의 개념

컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식. 즉 한쪽 끝에서 삽입이 일어나고 그 반대쪽 끝에서 삭제가 일어나는 순서 리스트이다.

• 새로운 원소가 삽입되는 끝 - 리어(rear)
• 원소가 삭제되는 끝 - 프런트(front)

큐(Queue)의 연산

큐는 FIFO(선입선출)을 따른다.

• add(item) : item을 리스트의 끝 부분에 추가한다
• remove() : 리스트의 첫 번째 항목을 제거한다
• top() : 큐에서 가장 위에 있는 항목을 반환한다.
• isEmpty() : 큐가 비어있을 때에 true를 반환한다.

큐(queue)의 사용 사례

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

• 너비 우선 탐색 (BFS, Breadth-First-Search 구현)
  * 처리해야 할 노드의 리스트를 저장하는 용도로 큐를 사용한다.
  • 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
  • 노드를 접근한 순서대로 처리할 수 이싿.
• 캐시 구현
• 우선순위가 같은 작업 예약 (인쇄 대기열)
• 선입선출이 필요한 대기열 (티켓 카운터)
• 콜센터 고객 대기시간
• 프린터의 출력 처리
• 윈도우 시스템의 메세지 처리기
• 프로세스 관리

큐(queue)의 구현

c++에서는 표준 템플릿 라이브러리 STL로 큐를 제공해준다.
하지만 STL을 쓰지 않고 큐를 구현하도록 해보자

1차원 배열 queue[] 이용

1. 큐의 첫번째 원소(front)원소를 queue[0]로 표현한 큐

• 삭제(pop) : queue[0]에 있는 앞 원소를 제거
  -> 삭제할 때마다 나머지 원소들을 왼쪽으로 이동해야 함
  -> 큐가 n개의 원소를 가질 때, 삭제 시 O(n)의 시간이 걸림.
• 삽입(push) : 배열크기 조절 시간을 제외하면 O(1) 시간이 걸림

2. 큐의 첫번째 원소를 queue[front]로 표현한 큐

• 변수 front를 사용하여 큐의 첫번째 위치를 항상 유지
• 원소의 삭제를 O(1) 시간에 수행하기 위한 방법
• 큐의 원소 : queue[front], ... , queue[rear]

• 배열 queue의 크기가 capacity일 경우, rear가 capacity-1과 같고, front>0일때 문제 발생
• 배열의 크기를 확장하지 않고 어떻게 원소를 삽입할까?
  - 큐의 모든 원소를 왼쪽 끝으로 이동시켜 오른쪽 끝에 공간을 만드는 방법
  - 배열 이동에 많은 시간 소요 : 큐의 원소 수에 비례
  • 원형 큐를 사용하는 방법
    • 큐가 배열의 끝에서 되돌아오게 하여 최악의 경우 삽입, 삭제 시간을 O(10)로 한다.

원형 큐 (Circular queue)

• 큐에 저장되는 원소들은 시계방향으로 저장된다.
• 변수 front는 큐에서 첫 원소가 저장된 위치의 직전 위치를 가리킨다.
• 변수 rear는 큐에서 마지막 원소를 가리킨다.

• 배열의 모든 위치는 직전 위치와 다음 위치를 가진다
  * capacity-1의 다음 위치 = 0
  • 0의 직전 위치 = capacity - 1
• 원형 큐의 동작 시 front와 rear가 시계 방향으로 이동
• 큐의 공백 조건 : front == rear
• 큐의 포화와 공백을 구분하기 위해 만원이 되기 전에 큐의 크기를 증가시킨다.
  - 즉, front == rear가 공백인지 포화인지 구분하기 위해 최대 원소 수를 capacity가 아니라 capacity-1로 한다.

#include <iostream>
using namespace std;

template <class T> class Queue{
public:
	T* queue; //큐 원소들을 저장한 배열(heap 영역에 위치)
	int front; // 첫번째 원소의 직전 위치
    int rear; //마지막 원소의 위치
    int capacity; //현재 확보된 큐 배열의 크기
    
    Queue(int queueCapacitye): capacity(queueCapacity){
    	if(capacity < 1) throw "Queue capacity must be > 0";
        queue = new T[capacity];
        front=rear=0;
    }
    ~Queue(){
		delete[] queue;
    }
    
    inline bool IsEmpty(){
    	return front == rear;
    }
    
    bool IsFull(){
    	if((rear + 1) % size == front) return true;
        else return false;
    }
    
    inline T& Front(){
    	if(IsEmpty()) throw "Queue is empty. No front element";
        return queue[(front+1)%capacity];
    }
    
    inline T& Rear(){
    	if(IsEmpty()) throw "Queue is empty. no rear element";
        return queue[rear];
    }
    
    void Push(T value)[
    	is(!isFull()){
        	queue[rear] = value;
            rear = (rear+1) % capacity;
        }
        else 	
        	cout << "Queue is full" << endl;
    }
    
    void pop(){
    	if(isEmpty()) throw "queue is empty. cannot delete";
        front = (front+1) % capacity;
        queue[front].~T();
    }