[자료구조] 큐( Queue )

Goal

Queue의 기본개념을 이해한다.
Queue의 구조를 확인한다.
Queue를 C/C++ 로 구현한다.

큐(Queue)의 개념

먼저 삽입한 데이터가 먼저나오는 FIFO(First In First Out) 형식의 자료구조이다.
Stack과는 정반대라고 생각하면 쉽다.

큐(Queue)의 종류

Queue는 일반적으로 연결 리스트 (Linked List)를 이용하며 구현 형태에 따라 선형 큐, 원형 큐 등으로 나뉜다.

1) 선형 큐

---

선형 큐는 배열을 선형으로 나타낸 형태이다. 자료의 삽입이나 삭제가 용이하나 큐에 빈 자리가 있어도 포화 상태로 인식하는 경우가 있어 빈 자리를 따로 정리 과정을 거쳐야 한다는 단점이 있다.

2) 원형 큐

---

배열을 원형의 모습으로 표현한 것으로 논리적으로 배열의 처음과 끝을 연결한 형태이다. 자리를 이동시킬 필요가 없어 실용적인 특징을 가지고 있다.

원형 큐에서는 초기 공백 상태에서 front와 rear의 값을 0으로 하고 공백 상태와 포화 상태를 구분하기 위해 자리를 비워둔다. 자료를 삽일할 경우 rear의 위치를 한 칸 앞으로 옮기고 그곳에 자료를 삽입한다. 따라서 front가 지정하는 위치는 항상 비워진 상태로 유지된다.

큐(Queue)의 STL 라이브러리

1) Queue 헤더파일과 선언

#include <queue>	// 헤더파일
queue <int> qu;		// queue < 데이터타입 > 이름;

2) Queue 기본 함수

▣ Queue에 데이터 추가하기

qu.push(element);

▣ Queue 데이터 삭제하기

qu.pop();

▣ Queue의 첫번째 데이터 반환

qu.front();

▣ Queue의 마지막 데이터 반환

qu.back();

▣ Queue 사이즈 반환

qu.size()

▣ Queue가 비어있는지 확인

qu.empty()

큐(Queue) 코드 구현 [ C++ / STL ]

“백준 10845번 : 큐”

#include <iostream>
#include <queue>

using namespace std;
using std::cout;
using std::cin;

int main() {

	int num;
	cin >> num;
	queue <int> qu;

	while (num--) {
		string str;
		cin >> str;
		int temp;
		if (str == "push") {
			cin >> temp;
			qu.push(temp);
		}
		else if (str == "front") {
			if (qu.empty()) {
				cout << "-1" << endl;
			}
			else cout << qu.front() << endl;
		}
		else if (str == "back") {
			if (qu.empty()) {
				cout << "-1" << endl;
			}
			else cout << qu.back() << endl;
		}
		else if (str == "size") {
			cout << qu.size() << endl;
		}
		else if (str == "pop") {
			if (qu.empty()) cout << "-1" << endl;
			else {
				cout << qu.front() << endl;
				qu.pop();

			}
		}
		else if (str == "empty") {
			if (qu.empty()) cout << "1" << endl;
			else cout << "0" << endl;

		}
	}



	return 0;
}