연결리스트를 이용한 큐 구현

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

 

 

연결리스트를 이용한 큐 구현

큐는 front 와 rear 양 쪽 값에 접근해야 하기 때문에 포인터 두 개를 만들어야 한다. 

삽입 삭제에 대해 각각 별도에 포인터가 사용된다. 

삽입 명령에 대해서는 rear 포인터가 가리키는 노드 바로 다음에 이어 붙이면 되고,

삭제 명령에 대해서는 front 포인터가 현재 가리키고 있는 노드 바로 다음 노드를 가리키게 하면 된다. 

 

 

 

 

다음은 위의 내용을 코드로 구현한 것이다. 

#include <iostream>

using namespace std;
typedef struct Node
{
    int Data;   //큐 데이터를 정수 타입으로 가정
    Node *Next; //다음 노드를 가리키는 포인터 변수
}node;


class Queue
{
public:
    Queue();    //생성자
    ~Queue();   //소멸자

    void Enqueue(int item); //item을 넣는다.
    int Dequeue();          //front에서 item을 반환한다.
    bool isEmpty;   //기본값은 true라고 한다.
    bool isOneData();   //큐 안 데이터가 하나라면, true이다. 

private:
    node * Front; // 기본값은 nullptr이다. 
    node* Rear;     //기본값은 nullptr이다. 
};

int main(void)
{
    Queue q;

    cout<<"enqueue: "; // 스택에 0부터 14까지 enqueue한다. 
    for(int i = 0; i<15; i++)
    {
        cout<<i<<" ";
        q.Enqueue(i);
    }
    cout<<endl<<endl;
    //결과 : enqueue: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
    
    cout<<"Dequeue: "; //스택이 비워질때까지 Dequeue한다.. 
    while(true) 
    {
        if(q.isEmpty == true)
            break;
        cout<<q.Dequeue()<<" ";
    }
    cout<<endl<<endl;
    //결과 : Dequeue: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
    
    cout<<q.isEmpty<<endl;
    //결과 1

    return 0;
}

Queue::Queue(): Front(nullptr), Rear(nullptr), isEmpty(true){}

Queue::~Queue()
{   
    //큐가 빌때동안 dequeue한다. 
    int num;
    while(isEmpty == false)
        num = Dequeue();
    
    //큐가 가지고 있던 공간을 반납한다. 
    delete Front;

    Front = nullptr;
    Rear = nullptr;
}

void Queue::Enqueue(int item)   //item을 넣는다. 
{
    if(isEmpty == true) //만약 큐가 비어있다면
    {   //새로운 노드를 만들어 Rear와 Front가 가리키게 한다. 
        Rear = new Node;
        Front = Rear;
    }    
    else//만약 큐가 비어있지 않다면
    {   //기존 Near->Next에 새로운 노드를 가리키게 한다. 
        Rear->Next = new Node;
        Rear = Rear->Next;
        //Rear는 새로운 노드를 가리킨다. 
    }

    //새로 만든 노드의 Data에 item을 넣는다.
    Rear->Data = item;
    //노드의 Next= nullptr로 지정한다. 
    Rear->Next = nullptr;
    //item이 들어왔으니 큐는 비어있지않다. 
    isEmpty = false;
}
int Queue::Dequeue()    //front에서 item을 반환한다.
{   //만약 큐가 비어있다면 -1을 반환한다. 
    if(isEmpty == true)
        return -1;
    
    //만약 Data가 하나뿐이었다면
    if(isOneData() == true)
        isEmpty = true;
        //그 Data가 리턴된다면 빈큐가 된다. 

    // Front를 다음 노드를 가리킨다. 
    Node* old_front = Front;
    Front = Front->Next;

    //기존 노드의 데이터를 저장한다. 
    int data = old_front -> Data;
    //이전 노드를 지운다. 
    delete old_front;
    return data;
    //데이터를 반환한다. 
}


bool Queue::isOneData()
{   //큐가 비어있지 않고, Front와 Rear가 같다면 그 큐는 원소를 하나 갖는다. 
    return (Front == Rear && isEmpty ==false) ? true: false;
}

 

 

 

물론 Rear 포인터 하나만으로도 큐를 구현할 수 있다. 

아래의 그림은 큐를 원형 연결 리스트로 구현하고, 마지막 데이터가 다시 처음 데이터를 가리키게 한 것이다. 이 경우 큐의 마지막 데이터는 Rear포인터로, 첫 데이터는 Rear->Next 포인터로 단번에 접근이 가능하게 된다. 

 

원형 연결 리스트

 

 

dequeue 연산을 한다면 

Rear->Next를  (Rear->Next)->Next로 옮긴후

할당을 해제한다. 

 

Enqueue 연산을 한다면

Rear->Next값을 저장한 후 

공간을 할당 받은 후 새로 생긴 Rear->Next값에 이전에 저장해 둔 Rear->Next를 넣는다.  

 

다음 그림과 같다. 

 

코드로 구현하자면 다음과 같다. 

 

#include <iostream>
using namespace std;
typedef struct Node
{
    int Data;   
    Node* Next; 
    // 노드는 데이터와 
    // 다음 노드를카리키는 포인터로 이루어져있다. 
}node;


class Queue
{
public: 
    Queue();    // 생성자
    // rear = nullptr, isEmpty는 true로 설정한다.  
    ~Queue();   // 소멸자

    void Enqueue(int item); // item을 추가한다.
    int Dequeue();  // 요소를 삭제한다. 

    bool isEmpty;   // 큐가 비었습니까?
    bool isOneData();   //원소가 하나입니까?

private:
    node* rear; // rear 포인터 
};

int main(void)
{
    Queue q;
    // Enqueue: 1 2 3 4 5 6 7 8 9 10 11 12 13
    cout<<"Enqueue: ";
    for(int i = 1; i<14; i++)
    {
        cout<<i<<" ";
        q.Enqueue(i);

    }   
    cout<<endl;

    //Dequeue: 1 2 3 4 5 6 7 8 9 10 11 12 13
    cout<<"Dequeue: ";
    for(int i = 1; i<3; i++)
    {   
        cout<<q.Dequeue()<<" ";
    }
    cout<<endl;

    return 0;
}
Queue::Queue():rear(nullptr), isEmpty(true){}  
//생성자
Queue::~Queue()
{   //소멸자 
    //큐가 빌때까지 dequeue하고
    //큐가 할당되었던 공간을 반납한다.
    int num;
    while(isEmpty ==false)
        num = Dequeue();
    
    delete rear;
    isEmpty = true;
}

void Queue::Enqueue(int item)
{   //큐에 요소를 추가한다. 
    // 만약 큐가 비어있다면,
    if(isEmpty == true)
    {   //rear는 새로운 노드를 가리킨다. 
        rear = new node();
        // rear-> Data에 item을 추가한다. 
        rear->Data = item;
        // rear-> Next는 rear을 가리킨다. 
        rear->Next = rear;
        // 더이상 큐는 비어있지 않다. 
        isEmpty = false;
        return ;
    }   

    // 새로운 리어는 새로운 노드를 카리킨다.
    node* new_rear = new node();
    // 새로운 리어의 Next는 기존에 리어가 가리키고 있던
    // Next를 가리킨다.
    new_rear->Next = rear->Next;
    // 기존의 rear->Next는 새로운 리어를 가리킨다.
    rear->Next = new_rear;

    //rear는 새로운 라어를 가리킨다.
    rear = new_rear; 
    // 리어에 데이터를 추가한다. 
    rear->Data = item;
    // 큐는 더이상 비어있지 않다. 
    isEmpty = false;
}

int Queue::Dequeue()  //요소를 반환한다. 
{   // 만약 큐가 비어있다면 -1을 반환한다. 
    if(isEmpty == true)
        return -1;
    // 만약 요소가 하나라면
    if(isOneData() == true)
    {   //그 요소가 dequeue되면 큐는 빈다.
        isEmpty = true;
        //rear->Data에 값을 저장한다.
        int data = rear->Data;
        //rear가 가리키고 있던 공간을 반납한다.
        delete rear;
        rear = nullptr;

        return data;
    }    

    //old_rear는 기존의 rear->Next이다.
    // 그리고 우리는 rear-> Next에 할당되었던 공간을 
    // 해제할 것이다. 
    node* old_rear = rear->Next;
    rear->Next = old_rear->Next;
    //rear-> Next는 old_rear->Next로 가리킨다. 

    int data = old_rear->Data;
    //old_rear->Data값을 저장한다.
    
    delete old_rear;
    old_rear = nullptr;
    //old_rear가 가리키고 있던 공간을 반납하고,
    // 포인터를 널값으로 넣는다. 
    return data;
}


bool Queue::isOneData()
{   
    //만약 rear->Next가 rear를 가리킨다면
    // 그 큐는 요소가 하나다. 
    return (rear->Next == rear) ? true : false;
}

 

수정 후

#include <iostream>
using namespace std;
typedef struct Node
{
    int Data;   
    Node* Next; 
    // 노드는 데이터와 
    // 다음 노드를카리키는 포인터로 이루어져있다. 
}node;


class Queue
{
public: 
    Queue();    // 생성자
    // rear = nullptr, isEmpty는 true로 설정한다.  
    ~Queue();   // 소멸자

    void Enqueue(int item); // item을 추가한다.
    int Dequeue();  // 요소를 삭제한다. 

    bool isEmpty;   // 큐가 비었습니까?
    bool isOneData();   //원소가 하나입니까?

private:
    node* rear; // rear 포인터 
};

int main(void)
{
    Queue q;
    // Enqueue: 1 2 3 4 5 6 7 8 9 10 11 12 13
    cout<<"Enqueue: ";
    for(int i = 1; i<14; i++)
    {
        cout<<i<<" ";
        q.Enqueue(i);

    }   
    cout<<endl;

    //Dequeue: 1 2 3 4 5 6 7 8 9 10 11 12 13
    cout<<"Dequeue: ";
    for(int i = 1; i<14; i++)
    {   
        cout<<q.Dequeue()<<" ";
    }
    cout<<endl;

    return 0;
}
Queue::Queue():rear(nullptr), isEmpty(true){}  
//생성자
Queue::~Queue()
{   //소멸자 
    //큐가 빌때까지 dequeue하고
    //큐가 할당되었던 공간을 반납한다.
    while(!isEmpty)
        Dequeue();
    
    delete rear;
    isEmpty = true;
}

void Queue::Enqueue(int item)
{   //큐에 요소를 추가한다. 
    // 만약 큐가 비어있다면,
    if(isEmpty == true)
    {   //rear는 새로운 노드를 가리킨다. 
        rear = new node();
        // rear-> Next는 rear을 가리킨다. 
        rear->Next = rear;
    }  
    else
    {
        // 새로운 리어는 새로운 노드를 카리킨다.
        node *new_rear = new node();
        // 새로운 리어의 Next는 기존에 리어가 가리키고 있던
        // Next를 가리킨다.
        new_rear->Next = rear->Next;
        // 기존의 rear->Next는 새로운 리어를 가리킨다.
        rear->Next = new_rear;
        //rear는 새로운 라어를 가리킨다.
        rear = new_rear; 
    } 

    // 리어에 데이터를 추가한다. 
    rear->Data = item;
    // 큐는 더이상 비어있지 않다. 
    isEmpty = false;
}

int Queue::Dequeue()  //요소를 반환한다. 
{   // 만약 큐가 비어있다면 -1을 반환한다. 
    if(isEmpty == true)
    {
        return -1;
    }    
    // 만약 요소가 하나라면
    if(isOneData())
    {   //그 요소가 dequeue되면 큐는 빈다.
        isEmpty = true;
    }    

    //old_rear는 기존의 rear->Next이다.
    // 그리고 우리는 rear-> Next에 할당되었던 공간을 
    // 해제할 것이다. 
    node* old_rear = rear->Next;

    rear->Next = old_rear->Next;
    //rear-> Next는 old_rear->Next로 가리킨다. 

    int data = old_rear->Data;
    //old_rear->Data값을 저장한다.
    
    //old_rear가 가리키고 있던 공간을 반납
    delete old_rear;
    return data;
}


bool Queue::isOneData()
{   
    //만약 rear->Next가 rear를 가리킨다면
    // 그 큐는 요소가 하나다. 
    return (rear->Next == rear && !isEmpty);
}