[자료구조] 큐(Queue)

큐(Queue)

queue는 대표적인 선형 자료구조 중에 하나다. queue는 FIFO(First In First Out)성질을 가지고 있다. 먼저 들어온 데이터가 가장 먼저 나간다는 의미다.

대표적으로 비유하는 것이 대기순서표이다. 먼저 온사람이 먼저 접수를 하고, 나중에 온 사람은 가장 뒤에서 기다려야 하는 것처럼 큐도 그렇다.

그림과 같이 새로운 데이터는 꼬리에 들어오고 기존의 데이터는 머리 쪽부터 차곡차곡 쌓인다. 그리고 데이터를 뺄 때는 가장 먼저 들어왔던 데이터가 나가는 구조다.

나는 주로 queue는 bfs탐색을 할 때 주로 사용한다. 직접 구현보다는 STL을 사용하기 간편하기 때문에 사용하지만 직접 구현해서 쓰는 것도 해봐야할 것 같다. 배열을 이용하지 않고, 리스트를 이용해 구현을 했다.

<소스코드>

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	template <typename T>
	class _queue {
	public:
	class Node {
	public:
	T data;
	Node *next;
	Node() {}
	Node(T data) :data(data),next(NULL){}
	};
	Node *Front = NULL;
	Node *Rear = NULL;
	int _size = 0;
	void push(T data) {
	Node *newNode = new Node(data);
	_size++;
	if (Front == 0) {
	Front = Rear = newNode;
	}
	else {
	Rear->next = newNode;
	Rear = newNode;
	}
	}
	void pop() {
	if (_size == 0)return;//오류
	_size--;
	Node *temp = Front;
	Front = temp->next;
	delete temp;
	}
	bool empty() {
	return size == 0;
	}
	T front() {
	return Front->data;
	}
	int size() {
	return _size;
	}
	};

view rawqueue_STL.cpp hosted with ❤ by GitHub

[push()]

데이터를 넣는 함수의 기능을 한다. queue는 데이터 가장 마지막 Rear에 넣는 것이기 때문에 queue의 Front가 비어있지 않다면 Rear->next에 새로운 노드를 연결해준다. 그리고 Rear포인터는 이제 새로운 노드를 가리키게 된다.

 

[pop()]

지울 때는 가장 먼저 들어왔던 데이터가 지워진다. Front 포인터가 Front->next에 있는 노드를 가리키게 된다. 그 뒤에 이전의 Front 포인터가 가리키던 노드를 delete시켜주면 된다.

[front()]

가장 먼저들어온 데이터를 반환하는 함수이다. 큐의 특징은 가장 먼저 들어온 데이터만 확인할 수있다. 하지만 본 구현에서는 Rear포인터도 존재하기 때문에 rear()를 임의로 만들어 마지막 데이터를 확인할 수는 있다.

[size()]

queue 사이즈를 반환해주는 함수이다. queue안에 몇 개의 데이터가 있는 지 알 수 있다.

[empty()]

empty는 bool반환형 함수다. queue가 비었는지 알려주고, 비었으면 true를 반환한다. 이러한 함수는 보통 조건문에 자주 쓰여진다.  

<소스코드>

	template <typename T>
	class queue {
	public:
	int capacity, Head, Tail;
	T *arr;
	queue() {
	capacity = 4;
	Head = Tail = 0;
	arr = new T[capacity] ;
	}
	~queue() { delete[] arr; }
	void resize(int n) {
	T *temp = new T[n * 2];
	int idx=0;
	while (Head != Tail) {
	temp[idx++] = arr[Head];
	Head = (Head + 1) % capacity;
	}
	Head = 0; Tail = idx; capacity *= 2;
	delete[] arr;
	arr = temp;
	}
	int size() { return (Tail - Head + capacity) % capacity; }
	void push(T data) {
	if (size() == capacity - 1) resize(capacity);
	arr[Tail] = data;
	Tail = (Tail + 1) % capacity;
	}
	void pop() { Head = (Head + 1) % capacity; }
	T front() { return arr[Head]; }
	bool empty() { return size() == 0; }
	void clear() { return Head = Tail = 0; }
	};

view rawqueue_STL2.cpp hosted with ❤ by GitHub

이번 소스는 배열을 이용해서 큐를 구현했다. 리스트로 구현한 것보다는 배열이 훨씬 빠른편이며, 동적으로 배열을 생성해서 만들었을 때 편하다. 

왜 리스트로 구현한 것보다 배열로 구현했을 때 더 빠를까 궁금했다. 

그 이유는 리스트에서 노드를 하나 생성하면 포인터를 통해서 이어준다. 

그래서 곧바로 옆 데이터를 확인이 가능하다고 생각할 수 있지만, 실상 배열 자체는 메모리가 자료형 사이즈만큼 구성되어있기 때문에 더 빠르게 참조가 가능하다. 

리스트는 포인터가 가리키는 메모리를 찾는 과정이 매번 필요하기 때문에 결과적으로 배열이 더 빠르다.

[resize()]

가변 배열이기 때문에 사이즈가 다 차면, 배열크기를 재조정해주는 기능을 한다. 현재 사이즈에서 2배로 늘려서 임시배열을 선언하고,원래의 배열안에 있는 데이터를 임시 배열에 옮겨준다. 가변배열로 하는 이유는 훨씬 더 메모리 절약이 가능하기 때문이다.

[push()]

데이터를 넣는 함수의 기능을 한다. Tail이 가리키고 있는 위치의 데이터가 마지막에 들어온 데이터다. 그 뒤에 새로들어온 함수를 넣어준다. Tail =(Tail+1)%capacity를 해주는 이유는 Tail위치에 새로운 데이터를 넣어준 뒤 커서를 옮긴다. 환형큐이기 때문에 항상 배열 용량만큼 %을 해줘야 다음 칸을 넘어간다.

 

[pop()]

지울 때는 가장 먼저 들어왔던 데이터가 지워진다. 지워질 때 Head가 그 다음 데이터가 되므로 인데스만 이동해주면 된다.

[front()]

가장 먼저들어온 데이터를 반환하는 함수이다. Head가 가리키는 배열을 곧 바로 반환해준다.

[size()]

queue 사이즈를 반환해주는 함수이다. queue안에 몇 개의 데이터가 있는 지 알 수 있다. 환형큐이기 때문에 Tail과 Head의 인덱스 차 + capacity에서 capacity만큼 모듈러 연산을 해줘야 한다.  

[empty()]

empty는 bool반환형 함수다. Tail 인덱스가 0이라면 현재 큐 안이 비었다는 이미기 때문에 Tail이 0이라면 반환시켜준다.