Computer Science & Engineering

개발환경

• Windows 10 pro 64bit
• Visual studio 2019(Intel(R) C++ Complier)
• Visual Studio Code (version 1.59.0)
• Node.js (version 14.16.0)
• Jupyter Notebook
• dlib (version 19.22.1)
• OpenCV
• React (version 17.0.2)
• Ubuntu (version 20.04)
• oracle cloud
• Django (version 3.2.6)

소스 코드

https://github.com/Seo-sang/Stroke_Self_Diagnosis

위 링크의 장고 웹서버를 포함한 모든 소스코드는 django2 branch에 존재한다.

master branch에는 리액트 프론트엔드와 머신러닝을 활용한 학습 및 예측하는 코드가 존재한다.

느낀점

    이번 공모전을 통해 오픈소스를 실제로 사용해보고 깃허브를 통해 팀원들과 한 repository에 push, pull하며 함께 프로그램을 만들고 실수도 많이 해보며 많이 배울 수 있었고 여러가지 오류들을 접하며 구글링을 통해 대처하고 해결하는 능력도 키울 수 있었던 것 같다.

    여러가지 프로그램을 설치해야하고 팀원과의 환경이 달라 내 PC에서는 동작하지 않은 문제들을 접하며 다른 사람들이 동작시킬 때에도 무엇이 문제가 될지를 생각해볼 수 있었다. 또 http를 사용할 때 보안문제로 인해 웹캠이 실행되지 않은 문제가 있었다. 따라서 localhost를 이용할 때는 문제가 없었지만 외부망에서 접속할 때 문제가 생겼다. 이를 해결하기 위해선 ssh로 접속해야하는 부분을 추가해야하지만 이 부분까지는 고려하지 못했다. 계속 수정할 계획이기 때문에 해결될 경우 다시 글을 적어보도록 하겠다.

    많은 것을 배울 수 있는 공모전이었고 동기들과 팀을 이뤄 원했던 결과가 딱 뜨는 순간 희열을 느낄 수 있었다. 마무리를 할 수 있어 굉장히 뿌듯했고 다음 번에는 또 다른 주제로 공모전에 참가해보도록 하겠다.

시연 영상

https://www.youtube.com/watch?v=i8v_ckeE2G4 

이번에는 장고 프레임 워크를 활용하여 벡엔드를 구현한 기능에 대하여 설멍하겠다. 저번 글에서 리액트를 활용하여 프론트엔드를 구현하였고 프론트엔드로부터 받은 사진을 백엔드에서 처리한 후 결과를 다시 프론트엔드로 보여주는 과정이 필요하다. 백엔드를 구현하는데에는 장고라는 python 프레임워크를 이용하였다. 장고의 구성도는 다음과 같다

. 주 역할

• 홈페이지 파일 클라이언트에 http로 전송
• 홈페이지와 서버 내부의 뇌졸중 여부 판단 함수 사이에 주고 받아야 하는 값 네트워크 통신을 통해 전달
• 이목구비 구분 이미지 서버 내부에 저장

프로젝트 내 포함 파일

• 홈페이지를 구성하는 리액트 앱 및 자바스크립트 파일
• 홈페이지와 통신하는 장고 stroke앱 및 파이썬 파일
• 얼굴 인식 및 뇌졸중 판단 여부 확인 함수의 results.py, train.py
• 홈페이지에 나타낼 이목구비 구분 이미지 파일 (사진을 업로드 할 때 마다 저장)
• 그 외 미디어 파일 및 정적 파일 (배경 사진, 정적 이미지)

프로젝트 수행 순서 (장고 위주 기술)

1. 장고 프로젝트(리액트 앱) 내에 존재하는 index.html 파일을 views.py를 통해 클라이언트에게 http로 return한다.
2. return 받은 index.html로 홈페이지를 출력한다. (리액트가 index.html을 이용하여 홈페이지 출력한다.)
3. 홈페이지에서 장고 서버에 ip(고유 정보)와 이미지 파일(base64타입)을 post요청한다.
4. post request를 통해 전달 받은 데이터를 views.py에서 results.py로 전달한다.
5. results.py에서 연산한 결과값(1)을 json으로 직렬화하여 jsonrepsonse로 홈페이지에 리턴한다.

(1) 뇌졸중 여부, 이목구비 구분된 이미지, 코 중앙에서부터 양쪽 눈 끝으로 각각 이었을 때의 길이 비율, 양쪽 입술 끝으로 이었을 때의 길이 비율, 양쪽 코 끝으로 이었을 때의 길이 비율

로컬 호스트 서버 구동

서버 구동 이후

localhost:8000에 접속할 경우 장고에서 리턴하는 홈페이지에 접속 가능하다.

실제 서버에서는 nginx를 이용하여 서버를 구동한다.

정상적인 이미지를 넘겨 받아 뇌졸중 확인을 한 경우 서버 로그에 얼굴 비율 값에 대한 로그를 남깁니다.

저번 글에서는 landmark detection이라는 오픈소스를 활용하여 얼굴의 특징점들을 얻고 각 거리를 구하여 얼굴의 비대칭성을 구했었다. 사용자가 쉽게 사용할 수 있는 방법이 웹캡을 활용하는 방법이었다. 따라서 노트북으로 홈페이지를 접속하여 얼굴을 찍어 넘기게 하였다. 프론트엔드는 리액트라는 자바스크립트 api를 활용하여 구성하였다.

메인 화면

웹페이지는 총 3개의 큰 페이지로 구성되어 있다. 페이지 상단에는 여러 페이지를 탐색할 수 있는 Navigation Bar가 위치해 있고 중앙에는 현재 화면이 표시된다. 처음은 홈 화면으로, 누구든지 사용 방법을 쉽게 알아볼 수 있도록 프로그램 이름과 함께 검사를 바로 진행할 수 있는 사진 찍기 버튼으로 구성하였다.

검사 방법

사진 찍기 버튼을 누르게 되면 간단할 설명과 함께 예시 표정이 오른쪽에 주어진다. 검사 방법 밑에 위치한 사진 찍기 버튼을 다시 누르게 되면 다음 창으로 넘어가 웹 캠 또는 스마트폰 카메라를 통해 사진을 캡처한 후 검사를 위해 서버에 전송할 수 있다. 사진에서는 잘 보이지 않지만 검사 방법은 다음과 같다.

1. 카메라가 바닥과 수평인지 확인 해주세요.
2. 얼굴에 그림자가 지지 않도록 밝은 곳에서 진행해주세요.
3. 오른쪽 사진과 같이 정면을 보고 웃어주세요.
4. 카메라를 응시한 채 '캡쳐' 버튼을 눌러주세요.
5. 결과가 나올 때까지 잠시 기다려주세요.

사진 찍기

사진 찍기 버튼을 누를 경우 위와 같이 사진을 찍을 수 있다. 웹캠이 화면에 표시되면 앞선 설명에 나와 있던 대로 사진을 찍으면 된다. 왼쪽의 캡처 버튼을 누르게 되면 사진은 서버로 전송되고 분석 과정을 거치게 된다.

결과 출력

사진을 전송한 뒤 잠시 후 인식된 얼굴의 사진과 함께 계산에 사용된 얼굴 부위의 좌표들을 사용자에게 보여준다. 그리고 왼쪽에는 뇌졸중 의심 여부에 대한 판단과 함께 분석한 결과의 세부 사항들을 사용자가 참고할 수 있도록 출력하였다. 위 결과에서 뇌졸중 의심 여부 : false이므로 뇌졸중이 의심되지 않는 것으로 나온다. 또한 눈, 입술,  코의 비대칭성을 수치로 보여주어 어느 부위가 비대칭적인지 알 수 있게 하였다. 사진은 위에서 찍을 때와 다른 사진이다.

이외의 페이지들

네비게이션 바의 설명을 누르면 다음과 같이 다른 정보들도 알 수 있다.

소스코드는 마지막 글에서 확인할 수 있다.

    이전 글에서 설명한 API와 logistic regression을 이용하여 얼굴 비대칭성을 계산하고 정상인과 환자 사진을 학습시켜 결과를 예측하도록 하였다. 뇌졸중 자가진단에 머신러닝을 사용하기 위해선 3단계의 과정이 필요하다. 첫 번째는 비대칭성 계산, 두 번째는 학습, 세 번째는 예측이다. 이 세 가지 단계는 다음과 같이 이루어져있다.

비대칭성 계산

    우리가 구현하고자 하는 기능을 위해선 얼굴의 눈, 코, 입을 인식하고 위치를 알 수 있는 API가 필요했다. 이 API는 github에 있는 cv2, dlib를 사용한 코드를 얻어올 수 있었다. API를 이용하여 아래 그림처럼 얼굴의 좌표를 얻을 수 있다.

뇌졸중의 초기 증상중 하나인 안면마비를 검증하기 위해 안면마비 환자들의 특징을 알아보았고 환자가 웃었을 때 왼쪽과 오른쪽의 비대칭성을 통해 의사가 판단한다는 것을 알 수 있었다. 따라서 얼굴의 좌표를 이용해 얼굴 중앙을 중심으로 3가지를 특징을 종합하여 왼쪽과 오른쪽의 비대칭성을 계산해보았다. 특징은 다음 3가지이다. 괄호 안에 있는 숫자는 아래 사진에서의 좌표 번호이다.

1. 중심(34)에서 왼쪽 눈 끝(37)까지의 거리 : 중심(34)에서 오른쪽 눈 끝(46)까지의 거리

2. 중심(34)에서 왼쪽 코 끝(32)까지의 거리 : 중심(34)에서 오른쪽 코 끝(36)까지의 거리

3. 중심(34)에서 왼쪽 입술 끝(49)까지의 거리 : 중심(34)에서 오른쪽 입술 끝(55)까지의 거리

    얼굴의 비대칭성이 심할수록 왼쪽과 오른쪽 거리의 차이가 더 커질 것이다. 따라서 비대칭성을 표현하는 수는 (작은 거리)/(큰 거리)를 이용하여 비율로 나타내었다. 즉 이 값이 1에 가까울수록 얼굴이 대칭적이고 1에서 멀어질수록 얼굴이 비대칭적이라는 말이다. 눈, 코, 입에 (작은 거리)/(큰 거리) 식을 이용하여 각각 계산하고 그 합을 더하였다. 따라서 3가지를 합하므로 3에 가까울수록 얼굴이 대칭적이라는 것이다.

학습

    실제 환자 사진과 정상인 사진으로부터 계산한 비대칭성을 나타낸 수를 이용하여 학습을 시켜야한다. 실제 환자 얼굴은 개인정보이기 때문에 많은 사진을 구할 수 없었다. 따라서 크롤링을 이용해 구글에서 찾을 수 있는 환자의 사진을 최대한 많이 모아보았다. 그 결과 160장의 사진을 구할 수 있었다. 정상인의 사진도 비슷한 개수로 구글링을 통해 154장을 구하여 총 314장의 사진으로 학습을 진행하였다. 1번 과정을 통해 얼굴의 비대칭성을 수로 표현할 수 있었다. 그 다음엔 각 사진이 하나의 숫자로 표현되기 때문에 logistic regression의 Classification을 이용하여 뇌졸중이 의심된다(1) 아니다(0)로 판단할 수 있다. 학습 과정은 다음과 같다.

- linear regression(선형 회귀)

    선형 회귀로 환자와 정상인으로부터 계산한 비대칭성을 나타내는 수들의 분포로부터 최적의 직선을 하나 만든다. 수치미분을 하며 학습시킬 비대칭성 수들로부터 최적의 직선을 만든다. 이 직선의 기울기가 W, y절편이 b이다. x가 뇌졸중이 의심되는지 판단하고자 하는 사람의 비대칭성을 계산한 수라고하면 (W*x + b) 값은 학습한 점들로부터 유추되는 예측 값이다. 매번 학습시킬 수 없기 때문에 학습한 결과인 W값과 b값은 파일에 저장하여 예측을 할 때 사용된다.

- Classification(분류)

    과정 1에서 한 선형 회귀의 결과 값은 뇌졸중이 의심되는지 판단하기 위해 1 또는 0의 값만을 가져야한다. 따라서 분류에 자주 사용되는 함수인 sigmoid 함수를 이용하여 1과 0 사이의 값으로 나타낸다. sigmoid함수는 오른쪽과 같은 수식과 함수 그래프로 나타난다. 따라서 sigmoid함수의 결과 값이 0.5보다 크면 안면마비일 확률이 높다는 뜻이므로 1을 리턴하고 0.5보다 작으면 안면마비일 확률이 낮으므로 0을 리턴한다.

- 학습 과정 구성도

예측

     이제 학습된 결과를 이용해 사용자로부터 사진을 받으면 안면마비인지 예측할 수 있다. 우선 사진의 비대칭성을 나타내는 수를 구하여 Wx + b값을 얻는다. 그 다음 결과 값을 sigmoid함수에 넣어 0.5보다 클 경우 안면마비로 판단, 0.5보다 작을 경우 안면마비가 아닌 것으로 판단할 수 있다. 결과를 예측하는 과정은 아래와 같은 구성도와 같이 동작한다.

예시

환자 사진을 예측한 결과이다. 아래서 세 번째 줄에 있는 0.2604..라는 값은 0이 완전 대칭이라고 할 때 얼마나 비대칭적인지를 나타낸 값이다. numpy배열로 나타난 아래서 두 번째 줄의 첫 번째 원소인 0.67138494는 sigmoid함수 결과 값으로 0.5보다 클 경우 뇌졸중으로, 0.5보다 작을 경우 정상으로 나온다. 0.67138494은 0.5보다 크므로 뒤에 1이라는 결과가 나와 뇌졸중 의심으로 판단한 것을 알 수 있다.

정산인 사진을 예측한 결과이다. 환자 사진과 비교해보면 0.0469..라는 값으로 0에서 크게 벗어나지 않은 것을 볼 수 있다. 또 0.28130981의 sigmoid 결과값은 0.5보다 훨씬 작은 수치로 뇌졸중 의심이 되지 않는다고 예측한 것을 알 수 있다.

머신러닝과 딥러닝API를 이용하여 안면비대칭을 진단하는 과정은 이렇게 이루어진다. 이제 사용자가 이용할 수 있게 웹사이트에 올려 사진을 받고 결과를 보여주는 작업이 남았다.

이전 글에서 다룬 기획 의도로 구현한 작품에 대한 설명을 해보겠다.

작품 개요

    사용자가 언제 어디서든 쉽게 사용할 수 있도록 하는 것이 중요한 사안이었기 때문에 웹페이지에 접속해 검사를 진행할 수 있도록 프로그램을 구현하였다. 웹페이지에 접속을 하게 되면 사용자는 사용하고 있는 전자기기에 따라 PC의 웹 카메라 또는 스마트폰의 전면 카메라를 통해 자신의 얼굴 사진을 캡처 하고 이 사진은 서버에 전송된다. 장고 웹 프레임워크를 사용하는 서버에 전달된 사진은 머신 러닝으로 학습된 함수 값에 따라 안면 비대칭에 근거한 뇌졸중 의심 여부를 판단하여 사용자가 분석 결과를 볼 수 있도록 웹페이지에 출력된다.

    웹페이지와 UI는 React라는 JS 라이브러리를 사용하여 구현하였으며 검사를 위한 사진 캡처, 프로그램에 대한 설명과 같은 기능을 제공한다. 사용자는 웹페이지에 접속하자마자 별 다른 과정 없이 간편하게 사진 캡처를 하고 결과 분석을 열람할 수 있다.

    사용자가 자신의 얼굴을 캡처한 사진을 제출하게 되면 이는 장고 웹 프레임워크로 구현한 서버로 전송된다. 해당 사진은 서버의 DB에 저장되며 python으로 구현한 분석 함수의 입력 값으로 주어지게 된다. 분석 결과가 함수로부터 반환되면 이는 서버로부터 다시 웹페이지로 전송되어 사용자가 볼 수 있도록 결과와 함께 설명이 출력된다.

캡처한 사진이 담고 있는 얼굴을 분석하기 위해 이미지를 처리하는 라이브러리인 OpenCV와 dlib를 사용하였다. 이 중 사진에서 얼굴을 인식하는 face detector와 눈, 코, 입 등 얼굴의 주요 부위를 인식하는 landmark predictor라는 기능을 사용하였다. Landmark predictor는 사진에서 인식한 얼굴의 주요부위를 68개의 좌표 값으로 출력하며 해당 값들을 통해 얼굴의 전체적인 비대칭 비율을 계산하였다.

    뇌졸중으로 인한 안면 마비 증상을 보이는 환자들의 얼굴 사진들과 정상인의 얼굴 사진들을 미리 구해 앞서 언급한 비대칭 비율을 계산하여 logistic regression과 classification을 활용해 학습 과정을 진행하였다. 학습된 결과를 바탕으로 새로운 얼굴 사진이 주어졌을 때 sigmoid 함수를 이용해 뇌졸중 의심 여부를 판단하여 결과 값을 반환한다.

시스템 구성도

프로그램은 크게 세 가지로 이루어진다. 리액트를 이용한 웹 페이지와 장고를 이용한 웹 서버와 머신러닝, 딥러닝 API를 이용한 학습 및 예측으로 구성되어 있다. 이 세 가지가 서로 동작하는 방법은 위 그림과 같이 이루어진다.

사용한 API

얼굴의 landmark detection을 위해 구글링을 통해 얼굴을 인식하고 눈, 코 입 등의 좌표를 얻을 수 얻을 수 있는 API를 찾을 수 있었다.
링크 : http://matthewearl.github.io/2015/07/28/switching-eds-with-python/

여기서 제공하는 코드에서 dlib, OpenCV를 이용하여 얼굴을 인식하고 아래 그림과 같이 눈, 코, 입의 좌표를 얻을 수 있다.

다음에는 이 좌표를 가지고 뇌졸중의 증상 중 하나인 안면마비로 인한 안면 비대칭을 logistic regression을 이용하여 학습하고 예측하는 방법을 적어보겠다.

전 세계 사망 원인 2위, 한국인 사망 원인 4위인 뇌졸중은 국내에서만 연간 60만 명에 달하는 환자들이 발생하고 있다. 현대인들의 식습관, 흡연, 운동 부족 등의 이유로 인하여 어느 날 갑자기 뇌졸중이 찾아올 수 있기 때문에 일반인은 미리 대비하는 것이 쉽지 않다. 뇌졸중이 발생한 후 적절한 응급 치료를 빠른 시간 내에 받지 못한다면 근력마비, 보행장애, 언어장애, 감각장애 등의 후유증이 생길 수 있고 최악의 경우에는 사망할 수 있다. 따라서 골든타임인 발병 후 6시간에서 최대 10시간 이내에 병원을 찾아 치료받는 것이 중요하다.

(출처: https://www.monews.co.kr/news/articleView.html?idxno=112694)

뇌졸중이 발병되었음을 인지할 수 있는 초기 증상들로는 말할 때 발음의 어눌함, 심한 두통, 얼굴이 부분적으로 마비되는 등 여러 종류가 있을 수 있다. 이들 중 안면 마비 증상이 제3자가 보았을 때 환자가 발생했음을 인지하기 제일 쉬운 방법이다. 뇌졸중이 발병한 환자들은 일반적으로 얼굴 한쪽이 마비되어서 심한 비대칭성을 나타내기 때문이다. 그러나 뇌졸중을 경험하고 있는 환자들은 감각에 대한 둔화가 오는 증상들이 동반되기 쉬워 거울을 보았을 때 스스로 얼굴에 이상이 있음을 인지하기 쉽지가 않다.

그래서 ‘건강한 얼굴 건강한 정신’이라는 프로그램을 기획하게 되었다. 이 프로그램은 주위에 제3자가 없더라도 핸드폰이나 노트북 등으로 손쉽게 뇌졸중의 초기 증상인 안면 마비 증상을 인지할 수 있도록 도움을 준다. 1인 가구 또는 혼자 보내는 시간이 많은 이들에게 자신이 뇌졸중을 경험하고 있는지 판단할 수 있도록 자가 진단을 제공하는 것이 이 프로그램의 목적이다.

STL priority_queue

    이번 글에는 STL의 <queue> 헤더파일에 존재하는 내부 함수 우선순위 큐를 직접 구현해보았다. priority_queue를 C++ STL 홈페이지(https://www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue)에서 찾아볼 경우 다음과 같이 나온다.

초록색 글씨를 보면 선언할 때 변수의 type(class도 가능)을 받고 두 번째 인자로 우선순위 큐를 구성하는 컨테이너, 즉 배열을 선언할 수 있다. 기본값으론 vector를 사용한다. 마지막 인자로 힙을 구성하는 비교 함수 연산자가 있는 class를 포함한다. 기본값인 less는 최대힙을 만들 때 사용한다. 최소힙으로 사용하고 싶을 경우 greater를 사용한다. 다음과 같이 최대힙, 최소힙을 선언할 수 있다.

#include <queue>

priority_queue<int, vector<int>, less<int>> pq; //최대힙
priority_queue<int, vector<int>, greater<int>> pq; //최소힙

우선순위 큐 동작 방식

 우선순위 큐는 힙을 이용한다. FIRST IN FIRST OUT인 queue와 다르게 우선순위가 높은 인자가 우선적으로 나온다. 힙의 push와 pop은 다음과 같이 동작한다. 예시는 5, 6, 3, 7, 10, 4가 순서대로 push될 경우 최대힙이 만들어지는 과정이다.

힙은 언제나 완전 이진트리이다. 동작방식은 다음과 같다.

삽입

• 삽입하려는 값을 트리의 맨 마지막에 넣는다.
• 부모노드와 비교하며 삽입하려는 값이 더 큰 경우 부모노드와 값을 바꾼다.
• 삽입하려는 값보다 큰 값이 나오지 않을 때까지 반복한다.
• 만약 root노드보다 삽입하려는 값이 큰 경우 root노드에 저장한다.

삭제

• 트리의 맨 아래의 맨 오른쪽에 있는 원소인 pivot을 root노드로 위치시킨다.
• 왼쪽 자식 노드와 오른쪽 자식 노드 중 큰 값과 비교한다.
• 자식 노드가 더 큰 경우 자식노드와 값을 바꾼다.
• pivot 값보다 작은 값을 만날 때까지 반복한다.
• 만약 leaf노드까지 도달한 경우 pivot 값을 leaf노드에 저장한다.

우선순위 큐는 위의 과정으로 동작한다. 여기서 비교하는 함수는 선언의 마지막 인자에 있는 class를 이용하여 비교연산을 한다. 

priority_queue 코드 설명

class의 구조와 멤버 변수는 다음과 같다.

template <class T, class CONT = std::vector<T>, class CMP = less<typename CONT::value_type>>
class mypriority_queue {
private:
    CONT container;
    int num;
    CMP compare;
}

    맨 첫 번째 줄을 보면 글 맨 위에 있는 사진에서 확인할 수 있듯이 template를 동일하게 선언하였다. 타입, 컨테이터, 비교클래스.

    멤버변수는 template로 선언한 container가 컨테이너, num은  원소의 수를 나타내고 compare는 비교를 실행할 인스턴스이다. 비교 클래스를 받기 때문에 클래스 안에 있는 비교함수나 연산자를 이용하기 위해선 그 class를 타입으로 가지는 인스턴스가 존재해야하기 때문에 선언하였다. 예를 들어 CMP안에 ()연산자가 정의된 경우 compare(a, b)와 같이 사용하여 비교연산을 수행할 수 있다.

사이트에 나와있는 멤버 함수는 다음과 같다.

이 중에 구현한 함수는 생성자를 포함해 empty, size, top, push, pop을 구현하였다. 다른 함수들은 많이 사용되지 않기 때문에 생략하였다.

소스 코드

아래 링크에서 확인할 수 있다.

https://github.com/Seo-sang/Cpp-_Standard_Template_Library/blob/master/mypriority_queue.cpp

이번에는 여러가지 알고리즘을 사용할 때 꼭 필요한 queue를 구현해보았다. STL의 queue에서 제공하는 priority_queue는 따로 minheap, maxheap으로 따로 구현하도록 하겠다. 우선 구현한 코드는 아래 링크에서 확인할 수 있다.

https://github.com/Seo-sang/Cpp-_Standard_Template_Library/blob/master/myqueue.cpp

queue란?

    queue(큐)는 stack과 같은 기본적인 자료구조로 가장 마지막으로 들어간 원소가 가장 먼저 나오는 LIFO(Last In First Out)인 stack과 다르게 가장 먼저 들어간 원소가 가장 먼저 나오는 FIFO(First In First Out)이다. queue를 그림으로 표현하면 다음과 같다.

그림과 같이 한쪽은 나올 수 만 있는 출구가 있고 다른 한 쪽은 들어갈 수만 있는 입구가 있다. queue안에서 순서는 바뀌지 않는다. 따라서 들어간 순서와 나오는 순서가 똑같다. 큐에 원소를 넣는 것을 'push'라고 하고 원소를 빼는 것을 'pop'이라고 한다. 위 그림은 1부터 6까지 push한 상태에서 1번 pop을 하고 7을 push하려고 하는 상태이다.

구현

     큐의 구현은 여러가지로 할 수 있다. 배열로 구현하는 것은 간단하지만  pop을 여러번 하는 경우 배열의 크기는 일정하기 때문에 배열의 앞 부분은 비어있는 상태가 될 수 있다. 또 배열의 크기보다 push를 많이 하는 경우 새로 할당해줘야하는 등의 오버헤드가 있기 때문에 그러한 번거로움을 줄일 수 있는 연결리스트로 구현하였다. 연결 리스트를 이용하여 구현하였기 때문에 이전 글 만들었던 list와 비슷한 부분이 많았다. 우선 각 노드를 나타내는 구조체는 아래와 같다.

struct node {
    T data; //값이 들어가는 변수
    node* next; //다음 노드를 가리키는 포인터

    node(T input) { //생성자
        data = input; //input을 준 경우 input으로 data를 설정
        next = NULL; //다음 노드는 NULL포인터로 설정
    }
    
    node() { //생성자
        data = 0; //input이 없는 경우 0으로 초기화
        next = NULL; //다음 노드는 NULL포인터로 설정
    }
};

STL queue에서 제공하는 대부분의 함수를 구현하였다. iterator가 없기 때문에 굉장히 간단했다. 구현한 메소드로는 empty, size, front, back, push, pop, swap이 있다.

실행 결과

1. push, pop 실행 결과

int main() {
    myqueue<int> q1;
    for(int i = 1; i <= 10; i++) //q1에 1부터 10까지 넣음
        q1.push(i);
    
    while(!q1.empty()) { //q1 출력
        cout << q1.front() << ' ';
        q1.pop();
    }
}

2. front, back 실행 결과

int main() {
    myqueue<int> q1;
    for(int i = 1; i <= 10; i++) //q1에 1부터 10까지 넣음
        q1.push(i);
    
    cout << "front : " << q1.front() << "\nback : " << q1.back() << endl; //front, back 출력

    while(!q1.empty()) { //q1 출력
        cout << q1.front() << ' ';
        q1.pop();
    }
}

3. swap 실행 결과

int main() {
    myqueue<int> q1, q2;
    for(int i = 1; i <= 10; i++) //q1에 1부터 10까지 넣음
        q1.push(i);
    
    for(int i = 101; i <= 110; i++) //q2에 101부터 110까지 넣음
        q2.push(i);

    q1.swap(q2); //q1과 q2 swap

    while(!q1.empty()) { //q1 출력
        cout << q1.front() << ' ';
        q1.pop();
    }
    
    cout << endl;

    while(!q2.empty()) { //q2 출력
        cout << q2.front() << ' ';
        q2.pop();
    }
    
}

이렇게 간단한 자료구조 queue를 구현해보았다. 우선순위 큐는 따로 minheap과 maxheap으로 구현하도록 하겠다.