큐 구현하기

서론

큐에서 디큐 에러시 리턴을 그냥 -1로 내 보냈는데..

이 큐가 사용하는 것이 signed 정수형이라고 생각하면 -1자체가 값이 될 수 있다.

그래서 어떻게 해야하나 파워 고민했었는데..

교수님이 수업 시간에 해답을 말씀해주셨다. 

"음 이렇게 에러를 체크하기 위해서 일반적으로 리턴형을 포인터타입으로 한다."

그렇다! 포인터를 사용하면 되는 것이었다!

하지만 일단 수정하기 파워 귀찮아서................

환형 큐는 처음에 정말 헷갈렸는데

Rear가 Front의 뒤를 잡는 것이 자료 인풋의 마지막이며

환형 큐에서는 무조건 1개의 공간이 낭비된다.

물론 배열 기반일 시 인덱스 자체가 낭비가 되는 것은 아니다!

Rear가 Front 뒤에 왔을 시 해당 인덱스에 값을 넣지 않고

가득 찬 상태를 표시하는 것이다!

선형 큐

/*
작성자 : 조민혁
작성일: 2015.06.04
작성내용
: 선형 큐 만들기

*/
 
#pragma once
#include <iostream>
 
// 선형 큐
template <typename T>
class MH_LinearQueue
{
private:
    // 큐 공간
    T* m_queueSpace;
 
    // 큐 앞
    int m_front;
    // 큐 뒤
    int m_rear;
    // 최대 공간
    int m_maxSpace;
 
public:
    // 생성자
    MH_LinearQueue(int queueSize);
    // 소멸자
    ~MH_LinearQueue(void);
    // 인큐
    void enQueue(T value);
    // 디큐
    T deQueue(void);
};
 
// 생성자
template <typename T>
MH_LinearQueue<T>::MH_LinearQueue(int queueSize)
{
    // 앞 값 초기화
    m_front = 0;
 
    // 뒤 값 초기화
    m_rear = 0;
 
    // 큐 사이즈만큼 동적할당
    m_queueSpace = new T[queueSize];
 
    // 최대공간 저장
    m_maxSpace = queueSize;
}
 
// 소멸자
template <typename T>
MH_LinearQueue<T>::~MH_LinearQueue(void)
{
    // 큐 해제
    delete [] m_queueSpace;
}
 
// 인큐
template <typename T>
void MH_LinearQueue<T>::enQueue(T value)
{
    // 가득 찼을 때
    if (m_rear == m_maxSpace)
    {
        cout<<"Queue is Full."<<endl;
        return;
    }
 
    // 큐에 값 넣기
    m_queueSpace[m_rear] = value;
    m_rear++;
 
    return;
}
 
// 디큐
template <typename T>
T MH_LinearQueue<T>::deQueue(void)
{
    // 비었을 때
    if (m_front == m_rear)
    {
        cout<<"Queue is Empty"<<endl;
        return -1;
    }
 
    // 리턴할 값을 저장
    T rtnValue = m_queueSpace[m_front];
    // 값 지우고 앞 증가
    m_queueSpace[m_front++] = NULL;
 
    return rtnValue;
}

환형 큐

/*
작성자 : 조민혁
작성일: 2015.06.04
작성내용
: 환형 큐 만들기

*/
 
#pragma once
#include <iostream>
 
// 선형 큐
template <typename T>
class MH_CircularQueue
{
private:
    // 큐 공간
    T* m_queueSpace;
 
    // 큐 앞
    int m_front;
    // 큐 뒤
    int m_rear;
    // 최대 공간
    int m_maxSpace;
 
public:
    // 생성자
    MH_CircularQueue(int queueSize);
    // 소멸자
    ~MH_CircularQueue(void);
    // 인큐
    void enQueue(T value);
    // 디큐
    T deQueue(void);
    // 비었는지 검사
    bool isEmpty(void);
};
 
// 생성자
template <typename T>
MH_CircularQueue<T>::MH_CircularQueue(int queueSize)
{
    // 앞 값 초기화
    m_front = 0;
 
    // 뒤 값 초기화
    m_rear = 0;
 
    // 큐 사이즈만큼 동적할당
    m_queueSpace = new T[queueSize];
 
    // 최대공간 저장
    m_maxSpace = queueSize;
}
 
// 소멸자
template <typename T>
MH_CircularQueue<T>::~MH_CircularQueue(void)
{
    // 큐 해제
    delete [] m_queueSpace;
}
 
// 인큐
template <typename T>
void MH_CircularQueue<T>::enQueue(T value)
{
    // 끝이 최대치에 도달 했을 때를 대비하여 다음 끝을 검사한다.
    int nextRear = (m_rear+1)%m_maxSpace;
 
    // 다음 끝이 처음이면 큐가 가득 찬 것.
    if (nextRear == m_front)
    {
        cout<<"Queue is Full."<<endl;
        return;
    }
 
    // 큐에 값 넣기
    m_queueSpace[m_rear] = value;
 
    // 현재 끝을 환형으로 앞으로 간 끝으로 바꿔준다.
    m_rear = nextRear;
 
    return;
}
 
// 디큐
template <typename T>
T MH_CircularQueue<T>::deQueue(void)
{
    // 비었을 때
    if (m_front == m_rear)
    {
        cout<<"Queue is Empty"<<endl;
        return -1;
    }
 
    // 리턴할 값을 저장
    T rtnValue = m_queueSpace[m_front];
    // 값 지우고
    m_queueSpace[m_front++] = NULL;
    // 환을 고려하여 프론트 값 모드연산
    m_front = m_front%m_maxSpace;
 
    return rtnValue;
}
 
// 비었는지 검사
template <typename T>
bool MH_CircularQueue<T>::isEmpty(void)
{
    // 비었을 때
    if (m_front == m_rear)
    {
        cout<<"Queue is Empty"<<endl;
        return true;
    }
    return false;
}

리스트기반 큐

#pragma once
 
// 사용할 노드
template<typename T>
struct NODE
{
    // 데이터
    T data;
    // 다음 노드
    NODE<T>* nextNode;
    // 이전 노드
    NODE<T>* prevNode;
};
 
// 링크드 리스트 큐
template<typename T>
class MH_LinkListQueue
{
private:
    // 앞
    int m_front;
    // 뒤
    int m_rear;
 
    // 머리 노드
    NODE<T>* m_headNode;
    // 꼬리 노드
    NODE<T>* m_tailNode;
 
public:
    // 생성자
    MH_LinkListQueue(void);
    // 소멸자
    ~MH_LinkListQueue(void);
 
    // 인큐
    void enQueue(T value);
    // 디큐
    T deQueue(void);
 
    // 새 노드 생성
    NODE<T>* getNewNode(T element);
};
 
// 생성자
template<typename T>
MH_LinkListQueue<T>::MH_LinkListQueue(void)
{
    // 초기화
    m_front = 0;
    m_rear = 0;
 
    // 더미 노드 생성
    m_headNode = new NODE<T>;
    m_tailNode = new NODE<T>;
 
    // 더미 초기화
    m_headNode->prevNode = NULL;
    m_headNode->nextNode = m_tailNode;
    m_tailNode->nextNode = NULL;
    m_tailNode->prevNode = m_headNode;
}
 
// 소멸자
template<typename T>
MH_LinkListQueue<T>::~MH_LinkListQueue(void)
{
    // 올 팝
    while(m_headNode->nextNode != m_tailNode)
    {
        this->deQueue();
    }
 
    // 더미노드 삭제
    delete m_headNode;
    delete m_tailNode;
}
 
 
// 인큐
template<typename T>
void MH_LinkListQueue<T>::enQueue(T value)
{
    // 새 노드 생성
    NODE<T>* newNode = getNewNode(value);
 
    // 노드 연결
    newNode->prevNode = m_tailNode->prevNode;
    newNode->nextNode = m_tailNode;
    m_tailNode->prevNode->nextNode = newNode;
    m_tailNode->prevNode = newNode;
 
    // 큐 뒤 값 증가
    m_rear++;
}
 
// 디큐
template<typename T>
T MH_LinkListQueue<T>::deQueue(void)
{
    int rtnData = m_headNode->nextNode->data;
 
    NODE<T>* delNode = m_headNode->nextNode;
 
    // 노드 재연결
    m_headNode->nextNode = delNode->nextNode;
    delNode->nextNode->prevNode = m_headNode;
    
    // 노드 삭제
    delete delNode;
 
    // 큐 앞 값 증가
    m_front++;
 
    return rtnData;
}
 
// 새 노드 생성
template<typename T>
NODE<T>* MH_LinkListQueue<T>::getNewNode(T element)
{
    // 노드 할당
    NODE<T>* newNode = new NODE<T>;
 
    // 데이터 넣기
    newNode->data = element;
 
    // 포인터 초기화
    newNode->nextNode = NULL;
 
    // 노드 반환
    return newNode;    
}