[자료구조] 큐 (Queue) C/C++ 구현 - 알고리즘

저번 글은 스택 구현에 대해 알아봤습니다.

2020/10/30 - [알고리즘] - [자료구조] 스택 (Stack) C/C++ 구현 - 알고리즘

[자료구조] 스택 (Stack) C/C++ 구현 - 알고리즘

큐란

큐는 톨게이트 (고속도로 요금 정산소)와 같습니다. 각 게이트에 먼저 도착한 차가 요금을 정산하고 먼저나가는 것과 같이, 먼저 들어온 데이터가 먼저 큐에서 빠져나가게 됩니다.

출처 https://moneys.mt.co.kr/news/mwView.php?no=2017081817158067212

---

큐 기능

큐에는 자주 사용되는 6가지 메소드 (method)가 존재합니다.

push(data)

스택에 데이터를 넣습니다. 들어간 데이터는 큐의 맨 뒤 (back)에 위치합니다.

front()

큐의 맨 앞에 위치한 데이터에 접근합니다. 만약 큐가 비어있는 경우 런타임 에러를 발생시킵니다.

back()

큐의 맨 뒤에 위치한 데이터에 접근합니다. 만약 큐가 비어있는 경우 런타임 에러를 발생시킵니다.

pop()

큐의 맨 앞에 위치한 데이터를 빼냅니다. front()나 back()과 마찬가지로 큐가 빈 경우 런타임 에러를 발생시킵니다.

size()

큐에 현재 저장되어있는 데이터의 개수를 반환합니다. 

empty()

큐가 비어있는지 확인합니다. 비어있다면 true를 반환하고, 데이터가 있다면 false를 반환합니다.

---

큐 구현

www.acmicpc.net/problem/10845

10845번: 큐

위의 백준 10845번: 큐 문제에 맞춰서 구현한 버전입니다.

런타임 에러가 발생할 수 있는 조건에서 -1을 대신 반환하도록 수정했습니다.

이전에 스택을 구현한것과 비슷하게 배열을 잡고 front와 back에 해당하는 인덱스를 저장하여 구현하면

pop() 호출 시 배열의 앞 공간이 낭비됩니다. 

이러한 이유로 큐는 연결리스트와 비슷하게 구현해야합니다. (또는 인덱스 모듈로 연산을 통한 원형 큐 구현)

아래는 큐 구조체 선언한 코드입니다. 각각의 queue 구조체가 더블 링크드 리스트의 노드처럼 연결됩니다.

struct queue {
	queue* prev;
	queue* next;
	int __size;
	int _data;
	queue* init(queue* head) {
		head = new queue();
		head->prev = head;
		head->next = head;
		head->__size = 0;
		head->_data = -1;
		return head;
	}
	void _push(queue* head, int data) {
		queue* tmp;
		tmp = new queue();
		tmp->_data = data;

		if (head->__size == 0) { // 빔
			tmp->prev = head;
			head->next = tmp;
		}
		else { // 이전에 들어왔어서 비어있지 않음
			queue* last = head->prev;
			tmp->prev = head->prev;
			last->next = tmp;
		}
		tmp->next = head;
		head->prev = tmp;
		head->__size += 1;
	}
	int _pop(queue* head) {
		if (head->__size == 0) {
			return -1;
		}
		int result = head->next->_data;
		queue* erase = head->next;
		head->next = head->next->next;
		head->next->prev = head;
		free(erase);
		head->__size -= 1;
		return result;
	}
	int _size(queue* head) {
		return head->__size;
	}
	int _empty(queue* head) {
		return (head->__size == 0);
	}
	int _front(queue* head) {
		if (_empty(head)) {
			return -1;
		}
		int result = head->next->_data;
		return result;
	}
	int _back(queue* head) {
		if (_empty(head)) {
			return -1;
		}
		int result = head->prev->_data;
		return result;
	}
};

 

아래는 백준 10845번: 큐 문제에 대한 풀이입니다.

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

struct queue {
	queue* prev;
	queue* next;
	int __size;
	int _data;
	queue* init(queue* head) {
		head = new queue();
		head->prev = head;
		head->next = head;
		head->__size = 0;
		head->_data = -1;
		return head;
	}
	void _push(queue* head, int data) {
		queue* tmp;
		tmp = new queue();
		tmp->_data = data;

		if (head->__size == 0) { // 빔
			tmp->prev = head;
			head->next = tmp;
		}
		else { // 이전에 들어왔어서 비어있지 않음
			queue* last = head->prev;
			tmp->prev = head->prev;
			last->next = tmp;
		}
		tmp->next = head;
		head->prev = tmp;
		head->__size += 1;
	}
	int _pop(queue* head) {
		if (head->__size == 0) {
			return -1;
		}
		int result = head->next->_data;
		queue* erase = head->next;
		head->next = head->next->next;
		head->next->prev = head;
		free(erase);
		head->__size -= 1;
		return result;
	}
	int _size(queue* head) {
		return head->__size;
	}
	int _empty(queue* head) {
		return (head->__size == 0);
	}
	int _front(queue* head) {
		if (_empty(head)) {
			return -1;
		}
		int result = head->next->_data;
		return result;
	}
	int _back(queue* head) {
		if (_empty(head)) {
			return -1;
		}
		int result = head->prev->_data;
		return result;
	}
};
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n;
	cin >> n;
	queue* q;
	q = q->init(q);
	for (; n--;) {
		string str;
		int num;
		cin >> str;
		if (str == "push") {
			cin >> num;
			q->_push(q, num);
		}
		else if (str == "pop") {
			cout << q->_pop(q) << "\n";
		}
		else if (str == "size") {
			cout << q->_size(q) << "\n";
		}
		else if (str == "empty") {
			cout << q->_empty(q) << "\n";
		}
		else if (str == "front") {
			cout << q->_front(q) << "\n";
		}
		else {
			cout << q->_back(q) << "\n";
		}
	}
}

템플릿을 이용한 큐 구현

#include <iostream>
#include <string>

#define MAX_SIZE (10000)
using namespace std;

template <typename T>
class queue {

private:
	T data[MAX_SIZE];
	int _front; // 큐의 데이터가 저장된 맨 앞 인덱스
	int _back; // 큐의 데이터가 저장된 맨 뒤 인덱스 // end = back + 1

public:
	queue() {
		_front = -1;
		_back = -1;
	}
	~queue() {

	}
	void push(T inputdata) {
		this->data[this->_back + 1] = inputdata;
		this->_back += 1;
		return;
	}
	T pop() {
		T res = this->data[this->_front + 1];
		this->_front += 1;
		return res;
	}
	int size() {
		return this->_back - this->_front;
	}
	bool empty() {
		return this->size() == 0 ? true : false;
	}
	T front() {
		T res = this->data[this->_front + 1];
		return res;
	}
	T back() {
		T res = this->data[this->_back];
		return res;
	}
};


int main() {
	
	ios_base::sync_with_stdio(false);
	cout.tie(0); cin.tie(0);

	queue<int> q;

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		string com;
		cin >> com;
		if (com == "push") {
			int data;
			cin >> data;
			q.push(data);
		}
		else if (com == "pop") {
			if (q.empty()) {
				cout << "-1\n";
			}
			else {
				cout << q.pop() << "\n";
			}
		}
		else if (com == "size") {
			cout << q.size() << "\n";
		}
		else if (com == "empty") {
			cout << q.empty() << "\n";
		}
		else if (com == "front") {
			if (q.empty()) {
				cout << "-1\n";
			}
			else {
				cout << q.front() << "\n";
			}
		}
		else { // back
			if (q.empty()) {
				cout << "-1\n";
			}
			else {
				cout << q.back() << "\n";
			}
		}
	}
}