큐

큐, Queue

한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 빼는 자료구조

FIFO: First Input First Output

 

큐의 성질

원소의 추가, 제거, 확인이 O(1)

제일 앞/뒤가 아닌 나머지 원소들의 확인과 변경이 원칙적으로 불가

추가는 뒤쪽(rear, tail), 제거는 앞쪽(front, head)에서 이루어짐

 

원형 큐 Circular Queue

선형 큐를 배열로 만들었을 때, pop으로 앞쪽에 빈 공간이 생겨도 원소를 더 채울 수 없다.

큐를 원형으로 만들면 앞쪽 빈 공간을 활용할 수 있다.

 

구현

head는 제거하는 앞쪽, tail는 추가하는 뒤쪽

#include <bits/stdc++.h>
using namespace std;

const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;

void push(int x) {
	dat[tail++] = x;
}

void pop() {
	head++;
}

int front() {
	return dat[head];
}

int back() {
	return dat[tail - 1];
}

void test() {
	push(10); push(20); push(30);
	cout << front() << '\n'; // 10
	cout << back() << '\n'; // 30
	pop(); pop();
	push(15); push(25);
	cout << front() << '\n'; // 30
	cout << back() << '\n'; // 25
}

int main(void) {
	test();
}

큐의 크기는 tail - head로 계산

 

STL queue

#include <bits/stdc++.h>
using namespace std;

int main(void) {

	queue<int> Q;
	
	Q.push(10); // 10
	Q.push(20); // 10, 20
	Q.push(30); // 10, 20, 30

	cout << Q.size() << "\n"; // 3

	if (Q.empty()) cout << "Q is empty\n";
	else cout << "Q is not empty\n";

	Q.pop(); // 20, 30

	cout << Q.front() << "\n"; // 20
	cout << Q.back() << "\n"; // 30

	Q.push(40); // 20, 30, 40
	Q.pop(); // 30, 40
	cout << Q.front() << "\n"; // 30

	while (!Q.empty()) { // 30, 40
		cout << Q.front() << ", ";
		Q.pop();
	}

}

 

큐가 비어있다면 Q.pop(), Q.front(), Q.back() 은 런타임 에러 발생

두 개의 큐 내용을 서로 바꾸고싶다면

swap(Q1, Q2);