[자료구조] 큐(Queue)의 개념과 구현(1)

 

큐(Queue)란?

큐는 먼저 들어온 데이터가 먼저 나가는 특성인 선입선출(FIFO)의 특징을 가진 선형 자료구조이다.

큐는 뒤쪽(rear)에서 데이터가 삽입되고, 앞쪽(front)에서 데이터 삭제가 이루어진다.

 

 

스택(Stack)과의 차이점

스택(Stack)은 데이터의 삽입과 삭제가 같은 곳(top)에서 이루어지지만, 큐는 데이터의 삽입과 삭제가 다른 곳에서 수행된다.

또한 후입선출(LIFO)의 특징을 가진 스택과는 달리, 큐는 선입선출(FIFO)의 특징을 가지고 있다.

---

큐의 삽입과 삭제

enqueue : 큐의 맨 뒤(rear)에 원소를 추가 - push()

dequeue : 큐의 맨 앞(front)에 있는 원소를 삭제 - pop()

 

 그림과 함께 차례대로 살펴보겠다. 먼저 enqueue(30)을 실행하면 다음과 같은 상태가 된다.

enqueue(30)

 

이후 추가적으로 enqueue(20), enqueue(10)을 진행해보겠다

추가 입력

이후 dequeue()를 진행하여 원소를 삭제해보겠다.

dequeue()- 원소 삭제

스택과는 다르게 가장 먼저 들어온 30이 가장 먼저 삭제가 됨을 볼 수 있다.

---

 

큐의 구현

c++ 에서는 std::queue라는 STL을 제공하지만, 그것과는 별개로 연결리스트를 이용해서 큐를 구현해보았다.

큐의 구현은 다음과 같다.

#include <iostream>
#include <list>

template <class T>
class Queue
{
private:
//pop_front 이용하기 위해 vector가 아닌 연결리스트인 list 사용
	std::list<T> que;

public:
	Queue() {}
	//원소의 삽입
	void enqueue(const T& element)
	{
		que.push_back(element);
	}
	//원소의 삭제
	void dequeue()
	{
		que.pop_front();
	}
	// 큐 내부가 비어있는지 확인
	bool empty()
	{
		return que.empty();
	}
	// 큐의 front에 있는 원소 반환
	const T& front()
	{
		return que.front();
	}
	// 큐의 크기 확인
	int size()
	{
		return que.size();
	}
};