Queue 자료구조 직접 구현하기

개요

안녕하세요.

C++ 자료구조 (Data Structure)의 가장 기본인 Queue 를 구현한 예제입니다.

• 먼저 들어간 값이 먼저 나오는 FIFO (First In First Out) 구조.
  

• 배열 (Array) 로 구성

• Push, Pop 이 일어날 때 배열의 값이동(X), 인덱스 (head, tail) 이동(O)

• 생성자에서 동적할당하는 클래스는 복사생성자, 대입연산자를 따로 정의
  

개발 환경

• C++17, Qt Creator 9.0.1, MinGW 11.2.0 64bit
  

• Windows 11 Pro

 

queue.h

#ifndef QUEUE_H
#define QUEUE_H

const int MAX = 5;

class Queue
{
public:
    Queue(int _size=MAX);
    ~Queue();
    Queue(const Queue& other);

    Queue& operator=(const Queue& other);

private:
    int size;
    int head, tail;
    int *p;

public:
    void print();
    void push(int v);
    int pop();
};

#endif // QUEUE_H

queue.cpp

#include "queue.h"
#include <iostream>
#include <cstring>
using namespace std;

Queue::Queue(int _size)
    : size(_size), head(0), tail(0), p(nullptr)
{
    cout << "Constructor" << '\n';

    p = new int[size];
    memset(p, 0, sizeof(int)*size);
}

Queue::~Queue()
{
    cout << "Destructor" << '\n';
    if(p)
    {
        delete[] p;
        p = nullptr;
    }
}

Queue::Queue(const Queue& other)
{
    cout << "Copy Constructor" << '\n';
    this->size = other.size;
    head = other.head;
    tail = other.tail;

    p = new int[size];
    memcpy(p, other.p, sizeof(int)*size);
}

Queue& Queue::operator=(const Queue& other)
{
    cout << "Assignment Operator" << '\n';
    if(this==&other)
        return *this;

    if(p)
    {
        delete[] p;
        p = nullptr;
    }

    this->size = other.size;
    head = other.head;
    tail = other.tail;

    p = new int[size];
    memcpy(p, other.p, sizeof(int)*size);
    return *this;
}

void Queue::print()
{
    for(int i=0;i<size;i++)
    {
        cout << p[i] << ' ';
    }
    cout << '\n';
}

void Queue::push(int v)
{
    p[tail%size] = v;
    tail++;
    if (tail>=size)
    {
        head = tail%size;        
    }
}

int Queue::pop()
{
    int temp = head;
    head++;
    return p[temp%size];
}

main.cpp

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

using namespace std;

int main()
{
    Queue q;

    // push    
    for(int i=0;i<5;i++)
        q.push(i);

    q.print();

    // pop
    for(int i=0;i<5;i++)
        cout << q.pop() << ' ';

    cout << '\n';
    return 0;
}

output

감사합니다.