큐 C++

 먼저 들어온 데이터가 먼저 나오는 선입선출 구조

---

 물건을 구매한다고 가정하면, 먼저 계산대에 줄을 선 사람이 물건 계산을 하는 것이 지당한 이야기다. 이렇게 먼저 들어온 데이터가 먼저 나가도록 하는 구조를 프로그램에서도 적용이 가능한데, 이 기능을 위해 Queue를 이용할 수 있다.

 

큐

 데이터 구조를 말하라고 하면 스택과 함께 먼저 거론되는 자료형이 아닐까 싶다. 큐는 스택과 같이 두 가지 필수 함수가 구성되어야 한다.

• push
• pop

 

구현

 큐는 크게 두 가지 방법으로 구현을 할 수 있다. 배열을 이용하는 방법과 연결리스트를 이용하는 방법이 있는데, 둘 모두 장단점이 있다.

 

배열을 활용한 구현

 배열 구현은 구현 자체가 간단하다는 장점이 있다. 다만 이는 재사용성을 생각하지 않을 때의 경우이고, 이미 사용한 공간을 재사용하는 방식의 구현은 연산을 추가해야한다.

 배열 구현을 할 때는 입력과 출력을 담당할 iterator 구현을 위한 멤버가 추가로 필요하다.

# 배열을 통한 큐 구현

#include <iostream>
#include <iomanip>

// 배열 기반 큐
class Queue {
	int* data;
	size_t capacity;
	size_t out;
	size_t in;

public:

	void print() {
		using namespace std;

		cout << "--출력--" << endl;

		for (size_t i = 0; i < capacity; ++i) {
			cout << setw(2) << i << ":" << setw(3) << data[i] << ", ";
		}

		cout << endl;
	}

	bool push(int value) {
		using namespace std;
		if (in - out >= capacity) {
			// 입력 위치 - 출력 위치가 capacity와 같거나 크다.
			// 입력이 크기를 벗어났다.
			cout << setw(7) << "push: " << "failed" << endl;
			return true;
		}
		cout << setw(7) << "push: " << "data in - " << setw(3) << value << endl;
		data[in++ % capacity] = value;
		return false;
	}

	bool pop(int* ref) {
		using namespace std;
		if (out < in) {
			*ref = data[out++];
			cout << setw(7) << "pop: " << "data out - " << setw(3) << *ref << endl;
			return false;
		}
		cout << setw(7) << "pop: " << "failed" << endl;
		return true;
	}

public:
	Queue() : Queue{10} {};

	Queue(size_t capacity) : capacity{capacity}, out{}, in{} {
		using namespace std;
		cout << "Queue Created" << endl;

		data = new int[capacity] {};
	}
	~Queue() {
		if (data) {
			delete[] data;
			data = nullptr;
			out = in = 0;
		}
	}
};

int main() {
	Queue q{10};
	int temp;
	for (int i = 0; i < 15; ++i) {
		std::cout << i << " ";
		q.push(i * 2 + 4);
	}
	q.print();
	q.pop(&temp);
	q.push(237);
	q.push(238);
	q.print();

	return 0;
}

 

노드를 활용한 구현

 노드를 이용하는 방식은 단방향 연결리스트를 통한 큐의 구현이기 때문에 배열에서와는 달리 길이의 제한이나 이터레이터를 위한 멤버 구성이 필요하지 않다. 그러나 기본적으로 단방향 연결리스트를 통한 구현이기 때문에 각 데이터를 구성하기 위한 오버헤드가 <배열을 활용한 구현>보다는 높을 수밖에 없다.

 또한, 노드를 구현해야하므로 구조체 선언도 함께 작성해야한다.

# 노드를 활용한 구현

#include <iostream>
#include <iomanip>

class Queue {
	struct node {
		struct node* next;
		int data;
	};
	struct node* head;
	struct node* tail;

public:
	void print() {
		using namespace std;
		cout << "--출력 시작--" << endl;
		struct node* p = head;
		int i = 0;
		while (p) {
			cout << setw(3) << i << ": " << p->data << endl;
			p = p->next;
		}
		cout << "--출력 끝--" << endl;
	}

	bool push(int value) {
		using namespace std;
		struct node* p = new (struct node){nullptr, value};
		// head가 없는 경우에는 tail도 존재하지 않는 것으로 판단.
		// pop에서 처리
		cout << setw(7) << "push: " << "data in - " << value << endl;
		if (!head) {
			head = p;
			tail = p;
			return false;
		}

		tail->next = p;
		tail = p;
		return false;
		
	}

	bool pop(int* ret) {
		using namespace std;
		if (!head) {
			cout << setw(7) << "pop: " << "failed" << endl;
			return true;
		}
		struct node* temp = head;
		*ret = temp->data;


		if (head == tail) {
			head = nullptr;
			tail = nullptr;
		}
		else {
			head = head->next;
		}

		cout << setw(7) << "pop:" << "data out - " << *ret << endl;

		delete temp;
		return false;
	}

public:
	Queue() :head{}, tail{}{}

	~Queue() {
		struct node* p = head;
		while (head) {
			p = head->next;
			delete head;
			head = p;
		}
	}
};

int main() {
	Queue q{};
	int temp;
	for (int i = 0; i < 10; ++i) {
		q.push(i * 11);
	}
	q.print();
	for (int i = 0; i < 11; ++i) {
		q.pop(&temp);
	}
	q.print();
	
	for (int i = 0; i < 3; ++i) {
		q.push(i * 11);
	}
	q.print();
	
	return 0;

}

 

---

 

 코드를 작성하면서 보면, (1)<배열을 활용한 구현>은 길이 제한이 있지만 메모리 사용 및 오버헤드 면에서[# 노드를 이용하면 매번 메모리를 할당받으면서 속도를 잡아먹는다] 이득을 보는 반면 (2)<노드를 활용한 구현>에선 이와 반대로 메모리는 조금 더 쓰더라도[# 매 요소가 추가될 때마다 포인터 크기가 추가로 필요하다] 길이 제한이 없다. 때문에 최대 길이가 정해진 경우에는 (1)안을 이용하고, 길이를 예측할 수 없을 때는 (2)안을 이용하는 것도 방법일 듯 하다.

 만일 속도와 메모리 모두 잡아야 하는 경우라면 내부 데이터는 배열처럼 구현을 하되 노드를 각 배열을 노드로 연결하는 방식을 이용하면 타협점을 찾을 수 있으리라 생각한다.

 

# index