queue 자료구조 설명 및 구현(c++)

큐 자료구조

---

 

 

- 먼저 들어온 데이터가 먼저 나가는 방식 (선입선출)의 자료구조

 

 

큐의 경우 복잡하게 생각할 것이 없다.

 

딱 편의점이라고 생각하면 쉽다. 편의점에서 알바생들이(나도 편의점 아르바이트는 많이 해봤지만...) 예전 물건들을 앞으로 내놓고 가장 최근에 들어온 물건들을 뒤에 놓는다. 왜냐? 제일 오래된 물건들을 먼저 팔아야 전체적인 물건의 유통기한도 길어질 뿐만 아니라 유통기한 지남에 의한 손해를 줄이기 위해서이다.

 

queue 자료구조는 이와 동일하다.

 

stack과 달리 먼저 들어온 자료가 먼저 나가도록 설계되었다.

 

Queue STL로 구현

#include <iostream>
#include <queue>

using namespace std;

int main() {

	// 큐 생성
	queue<int> q;

	// push
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	q.push(6);
	q.push(7);
	q.push(8);
	q.push(9);
	q.push(10);


	// pop
	q.pop();
	q.pop();
	q.pop();


	cout << "front : " << q.front() << '\n';
	cout << "back : " << q.back() << '\n';
	cout << "size : " << q.size() << '\n';
	cout << "empty? : " << (q.empty() ? "Yes" : "No") << '\n';

	// 출력
	while (!q.empty())
	{
		cout << q.front() << '\n';
		q.pop();
	}
	return 0;

}

기본 함수

• push(element) : 원소 추가(뒤)
• pop() : 원소 삭제(앞)
• front() : 맨 앞의 원소 반환
• back() : 맨 뒤의 원소 반환
• empty() : 비어있으면 true, 아니면 false 반환
• size(): 사이즈 반환

#include <iostream>
#include <queue>
using namespace std;

int main(void)
{
	queue<int> q;

	/* 값 넣기 */
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	q.push(6);
	q.push(7);
	q.push(8);
	q.push(9);
	q.push(10);

	/* size */
	cout << "queue size : " << q.size() << endl << endl; // 10

	/* front, back */
	cout << "queue front : " << q.front() << endl; // 1
	cout << "queue back : " << q.back() << endl << endl; // 10

	/* pop */
	cout << "popping" << endl; 
	q.pop();
	cout << "queue size : " << q.size() << endl; // 9
	cout << "queue front : " << q.front() << endl; // 2
	cout << "queue back : " << q.back() << endl; // 10

	cout << "queue empty? : " << (q.empty() ? "YES" : "NO") << endl; // NO
}

위 두 코드는 내용 자체가 유사하다

 

queue 함수 중 front는 가장 먼저 추가된 원소를 반환하고, back은 가장 나중에 추가된 원소를 반환한다는 것을 알 수 있다.

 

pop 함수는 queue 특성에 따라 가장 먼저 추가된 함수를 제거함에 따라 pop 이후에 front는 2로 출력되는 것을 확인할 수 있다.

 

 

 

코드 및 내용 참고

www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3