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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

#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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#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

감사합니다.