/ C

자료구조 정복하기 with C++ (4)Queue 큐

자료구조 정복하기 with C++ (4)Queue 큐

직접 코딩하면서 자료구조 공부하기

개요

자료구조와 알고리즘은 프로그램을 구성하는 가장 핵심적인 요소입니다. 프로그램 개발을 집을 짓는 것에 비유한다면 흙이나 모래, 시멘트, 목재와 같은 자재들이 바로 ‘자료구조’에 해당되고, 이러한 자재들을 이용해서 집을 짓는 것이 ‘알고리즘’에 해당됩니다. 자료구조는 가장 기본적이고 중요한 부분이기 때문에 복습하는 겸해서 직접 여러가지 자료구조를 코딩하면서 공부하기로 했습니다.

큐(Queue)

큐의 구조는 스택과 다르게 ‘선입선출’의 구조를 가지고 있습니다. 스택은 막힌 박스와 같아 먼저 들어온 것이 가장 나중에 나가는 구조지만, 큐는 먼저 들어온 것이 먼저 나가는 구조입니다. 대표적인 예로 번호표가 있습니다. 번호표를 뽑고 기다리는데, 늦게 온 다른 분이 먼저 업무를 본다면 기분이 나쁘겠죠? 따라서 도착한 순서대로 번호표를 뽑고 순서대로 업무를 볼 수 있도록 합니다. 이와 같은 자료구조를 큐(Queue)라고 합니다.

큐 기능

구현할 stack의 기능은 다음과 같습니다.

  1. 큐의 공간 유무 반환
  2. 큐의 앞과 끝 원소 반환
  3. 큐의 톱에 아이템 삽입
  4. 톱 아이템 삭제

Queue

Queue.h

큐의 헤더파일

#pragma once

template <class T>
class Queue
{
private:
	T* queue;
	int front, rear, capacity;

public:
	Queue(int queueCapacity = 10);		//처음에 크기가 stackCapacity인 공백 큐를 생성

	bool IsEmpty();				//큐의 원소 수가 0이면 true, 아니면 false를 반환

	T& Front();					//큐의 앞 원소를 반환

	T& Rear();					//큐의 끝 원소를 반환

	void Push(const T& item);			// 큐의 톱에 item을 삽입

	void Pop();					// 큐의 톱 원소를 삭제
};

Queue.cpp

큐 소스코드

#include "Queue.h"
#include <algorithm>

template <class T>
Queue<T>::Queue(int queueCapacity) : capacity(queueCapacity)
{
	if (capacity < 1) throw "Queue capacity must be > 0";
	queue = new T[capacity];
	front = rear = 0;
}

template <class T>
inline bool Queue<T>::IsEmpty() { return front == rear; }

template<class T>
inline T& Queue<T>::Front()
{
	if (IsEmpty()) throw "Queue is empty. No front element";
	return queue[(front + 1) % capacity];
}

template <class T>
inline T& Queue<T>::Rear()
{
	if (IsEmpty()) throw "Queue is empty. No rear element";
	return queue[rear];
}

template <class T>
void Queue<T>::Push(const T& x)
{
	if ((rear + 1) % capacity == front)
	{
		T* newQueue = new T[2 * capacity];

		int start = (front + 1) % capacity;
		if (start < 2)
			std::copy(queue + start, queue + start + capacity - 1, newQueue);
		else
		{
			std::copy(queue + start, queue + capacity - 1, newQueue);
			std::copy(queue, queue + rear + 1, newQueue + capacity + start);
		}

		front = 2 * capacity - 1;
		rear = capacity - 2;
		capacity *= 2;
		delete[] queue;
		queue = newQueue;
	}

	rear = (rear + 1) % capacity;
	queue[rear] = x;
}

template <class T>
void Queue<T>::Pop()
{
	if (IsEmpty()) throw "Queue is empty. Cannot delete.";
	front = (front + 1) % capacity;
	queue[front].~T();
}

결과

main.cpp

#include "Queue.h"
#include <iostream>
#include "queue.cpp"

using namespace std;

int main()
{
	//stack 생성
	Queue <int>queue;

	//queue의 원소 수 검사
	cout << "queue 공백 검사" << endl;
	cout << queue.IsEmpty() << endl;

	//queue에 원소 대입
	cout << "\n0, 1, 2 순서로 큐에 대입" << endl;
	queue.Push(0);
	queue.Push(1);
	queue.Push(2);

	cout << "\nqueue 공백 검사" << endl;
	cout << queue.IsEmpty() << endl;

	//queue의 앞 원소
	cout << "\n앞 원소: " << queue.Front() << endl;

	//queue의 끝 원소
	cout << "\n끝 원소: " << queue.Rear() << endl;

	//stack의 톱 원소 삭제
	cout << "\nqueue 톱 원소 삭제" << endl;
	queue.Pop();

	cout << "\n앞 원소: " << queue.Front() << endl;


	return 0;
}

Queue 자료구조를 작성했습니다. 결과가 잘 나옵니다!