[C++] 자료구조 - 큐 (Queue)

큐의 개요   

Queue 컨테이너는 FIFO( First In First Out)방식의 컨테이너를 구현한 템플릿 클래스다.

컨테이너지만 정확하게는 어댑터 컨테이너라고 불린다.

 

 

 

 

큐의 초기화   

#include <queue> 

std::queue<int> q;

std::queue<pair<int, int> > q; // 페어큐 선언

 

 

 

 

큐의 함수   

 

삽입

원소를 추가한다.

q.push(element)

q.push(make_pair(fisrt_element, second_element)); // 페어큐의 푸시

 

삭제

첫번째 원소를 제거한다.

q.pop()

 

참조 

첫번째 원소를 반환한다.

q.front()

// 페어큐의 참조
q.front().first; 
q.front().second;

마지막 원소를 반환한다.

q.back()

// 페어큐의 참조
q.back().first; 
q.back().second;

사이즈

현재 들어있는 원소의 개수를 int형으로 반환한다.

q.size()

 

비어있는지 확인

q.empty()

 

 

 

큐 예제   

 

기본예제

#include <queue> // std::queue를 사용하기 위한 헤더
#include <iostream>

int main()
{
    std::queue<int> q;

    // 삽입
    for (int i = 1; i <= 5; ++i)
    {
        q.push(i);    // q { 1, 2, 3, 4, 5 }
    }


    // 삭제
    q.pop();    // q { 2, 3, 4, 5 }


    // 읽기
    std::cout << "q.front() : " << q.front() << "\n";
    std::cout << "q.back() : " << q.back() << "\n";

    // 크기
    if (q.empty())
    {
        std::cout << "q is empty\n";
    }
    std::cout << "q.size() : " << q.size() << "\n";
}

 

 

큐 구현   

 

큐는 스택과 달리 정적배열을 사용하지 않고, 유연하게 자료를 삽입 / 삭제하기 위해 연결리스트로 구현을 한다.

그리고 연결 재료인 Node는 클래스 외부에 구조체로 선언해준다.

초기에 front와 rear는 특정 메모리를 가리키지 않고, 원소가 실질적으로 들어갔다는것을 알리는 count도 0으로 초기화 시켜준다.

 

 

myQueue.h

#pragma once

struct Node
{
	int data;
	Node* next;
};

class MyQueue
{
public:

	// 기본 생성자
	MyQueue() = default;

	// 소멸자
	~MyQueue() {};

	// 가장 먼저 노드를 저으이하고, Queue 구조체를 정의한다. 큐를 초기화 하는 initQueue()함수를 이용해 front와 rear를 null로 초기화

	int _front();

	int _back();

	int size();

	bool isEmpty();

	void enqueue(int data);

	int dequeue();

private:
	Node* front = nullptr;
	Node* rear = nullptr;
	int count = 0;

	size_t	_size = 0;
};

 

 

Queue.cpp

#include "myQueue.h"
#include  <iostream>

int MyQueue::_front()
{
	return front->data;
}

int MyQueue::_back()
{
	return rear->data;
}

int MyQueue::size()
{
	return count;
}

bool MyQueue::isEmpty()
{
	if (count == 0) { return true; }
	else { return false; }
}

void MyQueue::enqueue(int data)
{
	Node* newNode = new Node();
	newNode->data = data;
	newNode->next = nullptr;

	if (isEmpty())
	{
		front = newNode;
	}
	else
	{
		rear->next = newNode;
	}

	rear = newNode;
	count++;
}

int MyQueue::dequeue()
{
	int data;
	Node* pick = nullptr;

	if (isEmpty())
	{
		std::cout << "Error!" << " / result : ";
		return 0;
	}

	pick = front;
	data = pick->data;
	front = pick->next;
	delete pick;
	count--;

	return data;
}

front() / back()

각각 노드의 객체안에 들어있는 Data값을 반환시켜주면 된다. 큐가 비어있다면 각각 null을 반환한다.

 

size()

MyQueue의 필드인 count를 반환시켜주면 된다.

 

isEmpty()

Count =0. 즉 큐가 비어있다면 true를 반환, 그렇지않으면 false를 반환시켜준다.

 

enqueue()

실질적으로 원소를 삽입하는 메서드다, 노드타입 객체를 블럭처럼 만들어서 데이터를 삽입하고, 맨끝에있는 블럭에 연결시켜주는 과정이라고 생각하면 편하다. Node타입의 새로운 인스턴스를 만들고, 매개변수로 받는 값을 인스턴스의 data에 대입한다. 제일 마지막에 삽입되므로, next는 null값으로 초기화하고, 다음 메모리를 가리키지는 않는다.

큐에 원소가 한개도 없다면 front가 새롭게 만든 인스턴스가 되고, 원소가 남아있으면 맨 마지막 원소의 next는 newNode를 가리킨다. 기존 마지막 원소를 가리키던 rear는 newNode를 가리키고, count를 +1해주면 원소삽입작업이 끝난다.

 

dequeue()

원소를 꺼내오는 메서드다.

큐안에 원소가 들어있지않으면, 오류메세지를 띄운다. 

원소가 들어있을 경우 우선 노드객체를 가리킬 Pick이라는 포인터 변수를 선언해주고 front를 가리킨다.

그런뒤 front의 데이터를 꺼내서 data에 담아두고, front는 Pick다음의 원소를 가리킨다.

pick을 제거하고 count를 -1시켜주고 data를 반환하면 원소를 꺼내오는 작업이 끝난다.

 

myQueueTest.cpp

#include <iostream>

#include "myQueue.h"

using namespace std;
MyQueue q;

int main()
{
	q.enqueue(1);
	q.enqueue(3);
	q.enqueue(5);
	q.enqueue(7);
	q.enqueue(9);


	cout << "맨 앞 원소 : " << q._front() << endl;
	cout << "맨 뒤 원소 : " << q._back() << endl;
	cout << "사이즈 : " << q.size() << endl;

	while(!q.isEmpty())
	{
		cout << q.dequeue() << " ";
	}
	cout << "\n";
	cout << q.dequeue();

	return 0;
}

 

출력 결과