Queue

큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다.  나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

 

보통 큐(queue)는 선입선출(FIFO) 방식으로 작동한다. 반면, 양방향 큐가 있는데 그것이 바로 데크(deque)다. 즉, 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다.

큐와 데큐 구조

 

 

 

01. Queue 구현

Queue.h

#pragma once
#include <iostream>
using namespace std;

template <typename T>
class Queue
{
private:
	T* data;
	int count;
public:
	void Clear();
	int Count();
	bool IsEmpty();
	void Enqueue(T _data);
	T Dequeue();
public:
	Queue();
	~Queue();
};

 

 

 

Queue.cpp

#include "Queue.h"


template <typename T>
void Queue<T>::Clear()
{
    delete[] data;
    data = nullptr;
    count = 0;
}

template <typename T>
int Queue<T>::Count()
{
    return count;
}

template <typename T>
bool Queue<T>::IsEmpty()
{
    return data == nullptr ? true : false;
}

template <typename T>
void Queue<T>::Enqueue(T _data)
{
    if (data == nullptr)
    {
        data = new T;
        data[0] = _data;
    }

    T* temp = new T[count + 1];
    for (int i = 0; i < count; i++)
    {
        temp[i] = data[i];
    }
    temp[count] = _data;
    delete[] data;
    data = temp;
    count++;
}

template <typename T>
T Queue<T>::Dequeue()
{
    if (data == nullptr)
    {
        cout << "값이 없습니다." << endl;
        return -1;
    }
    T result = data[0];
    T* temp = new T[count - 1];
    for (int i = 1; i < count; i++)
    {
        temp[i - 1] = data[i];
    }
    delete[] data;
    data = temp;
    count--;
    if (count == 0) { data = nullptr; }
    return result;
}

template <typename T>
Queue<T>::Queue()
{
    data = nullptr;
    count = 0;
}

template <typename T>
Queue<T>::~Queue()
{
    delete[] data;
    data = nullptr;
}

 

 

 

Main.cpp

#include "Queue.cpp"

int main()
{
	Queue<int> queue;

	for (int i = 0; i < 5; i++)
	{
		queue.Enqueue(i);
		cout << i << "값을 넣었습니다." << endl;
		cout << "큐의 크기:" << queue.Count() << endl;
	}
	cout << "\n" << endl;

	while (!queue.IsEmpty())
	{
		cout<<queue.Dequeue()<<"값을 꺼냈습니다." << endl;
		cout << "큐의 크기:" << queue.Count() << endl;
	}
	cout << "\n" << endl;

	cout << "123값을 넣었습니다." << endl;
	queue.Enqueue(123);
	cout << "456값을 넣었습니다." << endl;
	queue.Enqueue(456);
	cout << "\n" << endl;

	if (queue.IsEmpty()){ cout << "큐가 비었습니다." << endl; }
	else { cout << "큐가 비어있지 않습니다." << endl; }

	cout << "큐에 있는 모든요소를 제거했습니다." << endl;
	queue.Clear();
	if (queue.IsEmpty()) { cout << "큐가 비었습니다." << endl; }
	else { cout << "큐가 비어있지 않습니다." << endl; }

	return 0;
}

 

---

02. Deque 구현

 

Deque.h

#pragma once
#include <iostream>
using namespace std;

template <typename T>
class Deque
{
private:
	T* data;
	int count;
public:
	void Push_Back(T num);
	void Push_Front(T num);
	T Pop_Back();
	T Pop_Front();
	bool isEmpty();
	void Clear();
	int Count();
public:
	void PrintAll();
public:
	Deque<T>();
	~Deque<T>();
};

 

 

 

Deque.cpp

#include "Deque.h"

template <typename T>
void Deque<T>::Push_Back(T num)
{
    if (data == nullptr) {
        data = new T;
        data[0] = num;
    }
    else 
    {
        T* temp = new T[count + 1];
        for (int i = 0; i < count; i++) 
            temp[i] = data[i];
        
        temp[count] = num;
        delete[] data;
        data = temp;
    }
    cout << num << "값을 Push_Back 했습니다." << endl;
    count++;
}

template <typename T>
void Deque<T>::Push_Front(T num)
{

    if (data == nullptr) {
        data = new T;
        data[0] = num;
    }
    else {
        T* temp = new T[count+1];
        temp[0] = num;

        for (int i = 1; i < count+1; i++) {
            temp[i] = data[i - 1];
        }
        delete[] data;
        data = temp;
    }
    cout << num << "값을 Push_Front 했습니다." << endl;
    count++;
}

template <typename T>
T Deque<T>::Pop_Back()
{
    if (data == nullptr) {
        cout << "값이 없습니다." << endl;
        return -1;
    }
    T result = data[count-1];

    T* temp = new T[count - 1];
    for (int i = 0; i < count - 1; i++) {
        temp[i] = data[i];
    }
    delete[] data;
    data = temp;
    count--;
    if (count <= 0) { data = nullptr; }
    cout << result << "값이 Pop_Back() 했습니다." << endl;
    return result;
}

template <typename T>
T Deque<T>::Pop_Front()
{
    if (data == nullptr) {
        cout << "값이 없습니다." << endl;
        return -1;
    }

    T result = data[0];

    T* temp = new T[count - 1];
    for (int i = 1; i < count; i++) {
        temp[i-1] = data[i];
    }
    delete[] data;
    data = temp;
    count--;
    if (count <= 0) { data = nullptr; }
    cout << result << "값이 Pop_Fornt() 했습니다." << endl;
    return result;
}

template <typename T>
bool Deque<T>::isEmpty()
{
    return data == nullptr ? true : false;
}

template <typename T>
void Deque<T>::Clear()
{
    cout << "값을 모두 제거 하였습니다" << endl;
    if (data != nullptr) {
        delete[] data;
        data = nullptr;
        count = 0;
    }
}

template <typename T>
int Deque<T>::Count()
{
    cout << "데큐의 크기는 " << count << " 입니다." << endl;
    return count;
}

template <typename T>
void Deque<T>::PrintAll()
{
    if (data==nullptr) {
        cout << "\n\n출력 할수 있는 값이 없습니다." << endl;
    }
    else 
    {
        cout << "\n\n데큐에 있는 값을 모두 출력합니다." << endl;
        for (int i = 0; i < count - 1; i++) {
            cout << data[i] << ", ";
        }
        cout << data[count - 1] << endl;
    }
   
}

template <typename T>
Deque<T>::Deque()
{
    data = nullptr;
    count = 0;
}

template <typename T>
Deque<T>::~Deque()
{
    delete[] data;
    data = nullptr;
}

 

 

Main.cpp

#include "Deque.cpp"

int main() {

	Deque<int> deque;

	for (int i = 0; i < 5; i++) {
		deque.Push_Back(i);
	}
	deque.Count();
	deque.PrintAll();

	deque.Push_Front(9);
	deque.Push_Front(8);

	deque.Pop_Back();
	deque.PrintAll();

	deque.Pop_Front();
	deque.PrintAll();

	deque.Pop_Back();
	deque.PrintAll();

	deque.PrintAll();

	deque.Count();

	deque.Clear();
	deque.PrintAll();


	return 0;
}