C++로 쉽게 풀어쓴 자료구조 연습문제 4-8

[QueueFibonacci.cpp]

/*

큐를 이용하여 피보나치 수열을 계산하는 프로그램을 작성하라

*/

#include <iostream>

#include "CircularQueue.h"

using namespace std;

 

int main(void)

{

        CircularQueue queue;

        int num;

        queue.enqueue(0); //F(0)=0

        queue.enqueue(1); //F(1)=1

        cout << "몇번째 피보나치 수열을 보고 싶으십니까 >";

        cin >> num;

        if (num == 0)

               cout << "찾으시는 " << num << "번째 피보나치 수열 숫자는 0 입니다" << endl;

        else if(num==1)

               cout << "찾으시는 " << num << "번째 피보나치 수열 숫자는 1 입니다" << endl;

        else

        {

               for (int i = 0; i < num; i++)

               {

                       int num1 = queue.dequeue(); //F(n-2)

                       int num2 = queue.dequeue(); //F(n-1)

                       int add = num1 + num2;

                       queue.enqueue(num2); //F(n)=F(n-1)+F(n-2)

                       queue.enqueue(add);

               }

               cout << "찾으시는 " << num << "번째 피보나치 수열 숫자는 " << queue.dequeue() << "입니다" << endl;

        }

        return 0;

}

[CircularQueue.h]

/*

원형 큐 프로그램

*/

#include <iostream>

#include <cstdlib>

using namespace std;

 

#define MAX_QUEUE_SIZE 100

 

inline void error(char *str)

{

        cout << str << endl;

        exit(1);

}

 

class CircularQueue

{

protected:

        int front; //첫 번째 요소 앞의 위치

        int rear; //마지막 요소 위치

        int data[MAX_QUEUE_SIZE]; //요소의 배열

public:

        CircularQueue()

        {

               front = rear = 0;

        }

        bool isEmpty()

        {

               return front == rear;

        }

        bool isFull()

        {

               return (rear + 1) % MAX_QUEUE_SIZE == front;

        }

        void enqueue(int val) //큐에 삽입

        {

               if (isFull())

                       error("error:큐가 포화상태입니다\n");

               else

               {

                       rear = (rear + 1) % MAX_QUEUE_SIZE;

                       data[rear] = val;

               }

        }

        int dequeue() //첫 항목을 큐에서 빼서 반환

        {

               if (isEmpty())

                       error("Error: 큐가 공백상태입니다\n");

               else

               {

                       front = (front + 1) % MAX_QUEUE_SIZE;

                       return data[front];

               }

        }

        int peek() //첫 항목을 큐에서 빼지 않고 반환

        {

               if (isEmpty())

                       error("Error: 큐가 공백상태입니다\n");

               else

                       return data[(front + 1) % MAX_QUEUE_SIZE];

        }

        void display() //큐의 모든 내용을 순서대로 출력

        {

               cout << "큐의 내용: ";

               int maxi = (front < rear) ? rear : rear + MAX_QUEUE_SIZE;

               for (int i = front + 1; i <= maxi; i++)

                       cout << data[i%MAX_QUEUE_SIZE] << " ";

               cout << endl;

        }

};

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] C++로 쉽게 풀어쓴 자료구조