[DATA STRUCTURE] 06. 큐(Queue)

아래의 코드는 C++로 구현된 큐(Queue)다.

가변 배열과 연결 리스트로 각각 구현되어 있으며 큐는 FIFO(First-In-First-Out) 원칙을 따르는 컨테이너 어댑터이기에

내부에서 사용하는 자료구조는 C++ STL에서 제공하는 std::vector와 std::list 컨테이너를 사용해 구현했다.

 

std::vector(가변 배열)로 구현된 큐

 

#pragma once
#include <vector>

template <class T>
class queue {
private:

	std::vector<T> vecQueue;

public:

	void push(const T& data) {

		vecQueue.push_back(data);
	}

	void pop() {

		vecQueue.pop_back();
	}

	bool isEmpty() const {

		return vecQueue.empty();
	}

	unsigned int size() const {

		return vecQueue.size();
	}

	const T& front() {

		return vecQueue.front();
	}
};

 

 

연결 리스트로 구현된 큐

 

#pragma once
#include <list>

template <class T>
class queue {
private :

	std::list<T> lQueue;

public : 

	void push(const T& data) {

		lQueue.push_back(data);
	}

	void pop() {

		lQueue.pop_front();
	}

	T& front() const{

		return lQueue.front();
	}

	unsigned int size() const {

		return lQueue.size();
	}

	bool isEmpty() const {

		return lQueue.empty();
	}
};

 

 

주요 특징

 

1. 선입선출(FIFO) : 큐는 "선입선출" 원칙을 따른다.

(가장 먼저 추가된 요소가 먼저 제거된다.)

 

2. 삽입과 삭제 : 큐는 데이터를 삽입하는(Enqueue) 연산과 데이터를 삭제하는(Dequeue) 연산을 지원한다.

(Enqueue는 큐의 뒤쪽에서 데이터를 추가, Dequeue는 큐의 앞쪽에서 데이터를 제거)

 

3. 대기열 및 작업 스케줄링 : 큐는 대기열 및 작업 스케줄링과 같은 여러 응용 프로그램에서 활용할 수 있다.

 

4. 배열 또는 연결 리스트로 구현 : 큐는 배열 또는 연결 리스트를 사용해 구현할 수 있다.

 

5. 성능 : 큐의 삽입과 삭제 연산은 보통 O(1)의 시간 복잡도를 갖는다.

(데이터의 끝에서 삽입과 삭제를 하므로 효율적이다.)

 

 

장점

 

1. 데이터 정렬 : 큐는 입력받은 순서대로 데이터를 관리하므로 데이터를 정렬하는 데 유용하다.

먼저 들어온 데이터가 먼저 처리되는 특징 덕에 작업을 순서대로 처리해야 하는 경우에 적합하다.

 

2. 작업 관리 : 큐는 작업 스케줄링 및 병렬 처리에 적합한 자료구조다.

다수의 작업을 대기열에 추가하고 차례대로 처리할 수 있다.

 

3. 데이터 버퍼 : 큐는 데이터를 버퍼링하는 데 유용하다.

데이터를 생성 및 소비하는 속도가 다를 때, 데이터를 일시적으로 버퍼에 저장하여 데이터 손실을 방지할 수 있다.

 

4. 메모리 관리 : 큐는 메모리를 효율적으로 활용하며, 메모리 할당 및 해제에 대한 부담을 줄일 수 있다.

 

 

단점

 

1. 느린 중간 요소 접근 : 큐에서 중간에 위치한 항목에 접근하기 어려우며, 특정 항목을 검색하려면

큐의 시작 부분부터 차례대로 확인해야 하며 이에 따라 검색 연산이 느릴 수 있다.

 

2. 크기 제한 : 큐는 고정된 크기를 가지며, 크기를 동적으로 조절하기 어려운 경우가 많으며

이에 따라 큰 데이터를 저장하거나 동적으로 크기가 변하는 상황에서는 적합하지 않을 수 있다.

 

3. 데이터가 넘치는 경우 : 큐가 계속 데이터로 채워지면 메모리 부족 문제가 발생할 수 있으며

이러한 경우에는 데이터가 제대로 처리되지 못할 수 있다.