[알고리즘] 큐(Queue)

[알고리즘] 큐(Queue)

---

FIFO(First In First Out) 먼저 들어온 것이 먼저 나가는 구조로 스택과는 반대되는 개념의 자료구조이다.  

다음 숫자들을 삽입/삭제 해보자

7, 3, 2, 삭제 , 5, 삭제

소스코드 구현 (C++ / STL)

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	queue<int> q;
	q.push(7);
	q.push(3);
	q.push(2);

	q.pop();

	q.push(5);

	q.pop();

	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}


	return 0;
}

출력 결과

소스코드 구현 (C)

#include <stdio.h>

struct Queue {
	int arr[10000];
	int last;

	void init() {
		last = -1;
	}

	void push(int data) {
		arr[++last] = data;
	}

	bool empty() {
		return last < 0;
	}

	void pop() {
		if (last < 0) return;
		int* temp = arr;
		for (int i = 0; i < last; i++)
		{
			arr[i] = temp[i + 1];
		}
		last--;
	}

	int size() {
		return last + 1;
	}

	int front() {
		return last < 0 ? -1 : arr[0];
	}
};

int main()
{
	Queue q;
	q.init();
	q.push(7);
	q.push(3);
	q.push(2);

	q.pop();

	q.push(5);

	q.pop();

	while (!q.empty())
	{
		printf("%d", q.front());
		q.pop();
	}

	return 0;
}

---

흔히들 큐을 은행 창구와 유사한 형태로 비유를 한다. 우리가 은행업무를 위해 은행을 방문하면 먼저 번호표를 뽑고 대기하닥 번호표의 순서대로 은행 업무를 치루게 된다. 이처럼 FIFO의 구조라는 점을 가장 크게 생각하면 될것 같다. 큐는 자체로 큰 의미를 가지고 있지않지만 데큐나 선형큐와 같은 많은 자료구조 알고리즘에 기본이 되는 자료구조이다.