큐

선입선출(FIFO, First In First Out) 구조이다.

큐는 한 쪽 끝에서는 삽입만 다른 한 쪽 끝에서는 제거만 가능한 구조이다.

• 맨 뒤에 자료를 삽입하는 연산을 enQueue 라고 부르고,
• 맨 앞에 자료를 제거하는 연산을 deQueue 라고 부른다.

C++ STL

#include <queue>
queue<int> q;

기본 함수로는
push pop front size empty 가 있다.

push: 데이터를 스택에 삽입한다.

q.push(x);

pop: 가장 최근에 삽입된 데이터를 스택에서 제거한다.

q.pop();

front: 가장 앞에 있는 데이터를 반환한다.

data = q.front()

size: 큐의 크기를 반환한다.

int sz = q.size();

empty: 큐가 비어있으면 1, 아니면 0을 반환한다.

bool isEmpty = q.empty();

C Code 배열 기반 구현

#define SIZE 10000
#define EMPTY 0x3f3f3f3f

int q[SIZE];
int sz = 0, rear = 0;

void push(int x) {
	if (SIZE <= rear) return;
	q[rear++] = x, sz++;
}

void pop(void) {
	if (sz == 0) return;
	sz--;
}

int front(void) {
	if (sz == 0) return EMPTY;
	return q[rear - sz];
}

int size(void) {
	return sz;
}

int empty(void) {
	return sz == 0;
}

추천 문제

백준 10845번: 큐
백준 1966번: 프린터 큐