[자료구조] 큐 (Queue)

큐 (Queue) 란?

• 큐는 FIFO(First In, First Out) 구조로, 먼저 들어온 데이터가 먼저 나가는 자료구조
• 스택과는 다르게 먼저들어온것이 먼저나가는 FIFO 구조를 가지고있다.

장단점

장점

• 데이터의 삽입과 삭제가 O(1) 시간으로 이루어져 빠르게 처리가 된다.

단점

• 중간과 마지막에 있는 데이터의 접근하려고하면 비효율적이다.

구현

#include <queue> 사용

#include <iostream>
#include <queue>

using namespace std;

int main(void) {

	queue<int> q;

	q.push(1);
	q.push(2);
	q.push(3);
	cout << q.front() << "\n"; // output : 1
	q.pop();
	cout << q.front() << "\n"; // output : 2

	if (!q.empty()) {
		cout << "not empty" << "\n"; // output : not empty
	}
	if (q.size()) {
		cout << "size : " << q.size() << "\n"; // output : size : 2
	}

	return (0);
}

 

deque를 활용한 구현

#ifndef CUSTOMQUEUE_HPP_
#define CUSTOMQUEUE_HPP_

#include <iostream>
#include <deque>

template <typename T>
class CustomQueue 
{
	private:
		std::deque<T> c;
		int _size;
	public:
		CustomQueue() {};
		~CustomQueue() {};

		void push(T data) {
			c.push_back(data);
		}
		T pop() {
			T temp = c.front();
			c.pop_front();
			return temp;
		}
		size_t size() const {
			return c.size();
		}
		bool empty() const {
			return c.empty();
		}
		T front() const {
			return c.front();
		}
};

#endif

• queue에 경우에는 stack과 다르게 FIFO를 사용하고 있기때문에 list나 deque같은 동적할당방식을 사용하지않으면 배열의 재사용이 이루어지지않기때문에 낭비되는 메모리가 많기때문에 deque 방식 사용
• stack과 queue의 실제 구현에서도 deque방식이 사용되어 인터페이스 제한을 사용하여 구현되어있다.