[Algorithm] 큐 (Queue)

[Algorithm] 큐 (Queue)

 

큐 (Queue)

 

-정의

 

 컴퓨터의 기본적인 자료구조 중 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식

큐 (Queue)

-연산/용어

 

(1) push() : 큐의 제일 앞에 값을 삽입 (=Enqueue)

(2) pop() : 큐의 마지막 값을 제거 (=Dequeue, Pull)

(3) front(head) : 데이터를 pop할 수 있는 위치

(4) rear(tail) : 데이터를 put할 수 있는 위치

(5) 오버플로우(overflow) : 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우

(6) 언더플로우(underflow) : 큐가 비어 있어 자료를 꺼낼 수 없는 경우

(7) 큐의 길이(size) : rear - front

 

 

-종류

 

(1) 선형 큐(linear queue) : 막대 모양으로 된 큐. 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있다. (배열로 큐를 선언할시 큐의 삭제와 생성이 계속 일어났을때, 마지막 배열에 도달후 실제로는 데이터공간이 남아있지만 오버플로우가 발생)

 

 

선형 큐 (Linear Queue)

 

(2) 환형 큐(circular queue) : 선형 큐의 문제점을 보완한 것이 환형 큐. front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결 하는 방식이다. 원형 큐라고도 한다.

 

환형 큐 (Circular Queue)

 

 

(3) 링크드 큐(linked queue): 연결 리스트로 구현한 큐는 연결 리스트를 사용한 것으로써, 큐의 길이를 쉽게 늘릴 수 있어 오버플로우가 발생하지 않는 것이 특징이다. 필요에 따라 환형으로 만들 수도 있으며, 환형으로 만들지 않아도 삽입과 삭제가 제한되지 않아 편리하다.

 

(4) 우선순위 큐 : 원소들에게 우선순위를 매겨서 넣을 때의 순서와 상관없이 뺄 때에는 우선순위가 높은 원소부터 빼내는 것. 대표적인 예로는 heap이 있다. 

 

 

-활용

 BFS, Flood fill

 

 

-시간복잡도

 

(1) 원소 추가: O(1)

(2) 원소 제거: O(1)

(3) 원소 확인: O(1)

 

 

-구현

 

(1) C++ STL queue 사용하여 구현

(2) 배열로 구현

 

    선형 큐로 구현 - 백준 10845번 큐

 

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

 

입력 : 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

 

출력 : 출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

 

내 코드

 

#include <iostream> 
#include <string>

using namespace std;

int queue[100000];
int front = 0, rear = 0;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	//배열로 선형큐 구현
	int n = 0;
	cin >> n;

	while (n--) {
		string input;
		cin >> input;

		if (input == "push") {
			int tmp = 0;
			cin >> tmp;
			queue[rear++] = tmp;
		}
		else if (input == "pop") {
			if (rear != front) {
				cout << queue[front++] << endl;
			}
			else cout << -1 << endl;
		}
		else if (input == "size") {
			cout << rear - front << endl;
		}
		else if (input == "empty") {
			if (rear != front) cout << 0 << endl;
			else cout << 1 << endl;
		}
		else if (input == "front") {
			if(rear != front) cout << queue[front] << endl;
			else cout << -1 << endl;
		}
		else if (input == "back") {
			if (rear != front) cout << queue[rear -	1] << endl;
			else cout << -1 << endl;
		}
	}

	return 0;
}

 

 

(3) Linked List로 구현

 

 

 

 

 

 

참고

 

https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

https://blog.encrypted.gg/727?category=773649