열코의 프로그래밍 일기

※  그래프란 비선형(non-linear) 자료구조이며 노드(node)와 엣지(edge)로 구성되어 있습니다.

- 노드는 꼭짓점(vertex)으로 표현됩니다

- 엣지는 두 노드를 연결하는 선(line)으로 표현됩니다.

위 그래프를 V(vertex) = {0, 1, 2, 3, 4}와 E(edges) = {01, 12, 23, 34, 04, 14, 13}으로 표현할 수 있습니다.

그래프는 많은 일상 생활의 문제점을 해결하기 위해 사용됩니다. (네트워크의 표현 등) 

※ 그래프의 표현

그래프를 인접 행렬(Adjacency Matrix) 또는 인접 리스트(Adjacency List)로 표현할 수 있습니다.

1. 인접 행렬 

인접행렬은 2차원 배열(v x v)로 표현될 수 있습니다. 엣지가 존재하는 노드의 짝(i, j)의 배열 값을 1로 설정하고, 엣지가 존재하지 않는 노드의 짝(i, j)의 배열 값을 0으로 설정합니다.가중치 그래프(Weighted Graph)에서는 배열 값을 w(가중치)로 설정 할 수 있습니다.

☞ 소스코드(C++)

2. 인접 리스트

각 꼭짓점(vertex)의 리스트는 헤더(Header)노드를 가집니다. 각 헤더노드들은 배열을 이용하여 연결된 각각의 노드를 순차적으로 가리킵니다.(오름차순)

☞ 소스코드(C++)

정보가 유익하셨다면 아래 공감버튼 눌러주시면 감사하겠습니다.

질문사항은 댓글로 달아주시면 성의껏 답변해드리겠습니다.

1. 의미
- 큐(Queue)의 사전적 의미는 무엇을 기다리기 위해 서는 줄, 대기열입니다.
예를들어 우리가 게임을 할 때 '큐를 잡는다, 큐를 기다린다'라는 말의 큐는 바로 줄, 대기열을 의미합니다. 우리가 줄을 서면 가장 앞에있는 사람(가장 먼저 들어온 데이터)이 가장 먼저 들어가죠? 이러한 구조를 선입선출(First In First Out; FIFO)구조라고 합니다. 

2. 연산
- 일반적으로 큐 자료구조의 앞을 Front, 뒤를 Rear라고 칭합니다. 그림으로 표현하면 다음과 같습니다.

큐가 비어있는 상태를 front == rear(같음) 상태로 표현합니다.
(초기화시 front = rear = 0으로 초기화)

삽입(Enqueue)연산은 rear의 위치에 데이터를 삽입하고 rear의 위치를 1 증가 시켜줍니다.

큐의 끝(rear)가 배열의 마지막을 가리키고있는 상태가 큐가 가득 찬 상태입니다.
이렇게 큐를 배열로 구현했을 경우 0번 인덱스는 사용하지 않는 메모리가 되었습니다.
물론 고정적인 배열의 크기도 문제가 됩니다.
이를 해결하기 위해 원형 큐, 링크드 리스트로 구현한 큐... 등 여러가지 큐가 존재합니다.

3. 사용
프로세스 관리
운영체제(OS)의 작업 큐
프린터 출력의 문서 대기...등 
입력된 시간 순서대로 처리해야하는 모든 상황에 거의 큐가 사용됩니다.

4. 구현
배열로 구현한 큐)
#include <iostream> 
using namespace std;

class queue
{
private:
     int *queue_arr; // 큐 배열(동적 할당을 위해 포인터로 선언) 
     int queue_size; // 큐의 크기 
     int front, rear;

public:
     queue() // 디폴트 생성자 함수 
     {
          front = 0; rear = 0; // front와 rear 위치를 0으로 초기화
          queue_size = 5; // 매개변수 없이 객체 생성 시 스택 크기 5로 지정 
          queue_arr = new int[queue_size]; // 배열 동적 할당 
          for (int i = 0; i < queue_size; i++)
          {
               queue_arr[i] = 0; // 큐의 배열은 모두 0으로 초기화 
          }
     }
     queue(int size) // 생성자 함수 
     {
          front = 0; rear = 0; // front와 rear 위치를 0으로 초기화
          queue_size = size; // 입력한 매개변수 크기만큼 스택 크기 지정 
          queue_arr = new int[queue_size]; // 배열 동적 할당 
          for (int i = 0; i < queue_size; i++)
          {
               queue_arr[i] = 0; // 큐의 배열은 모두 0으로 초기화 
          }
     }
     ~queue() // 소멸자 함수 
     {
          delete[] queue_arr;
     }
     void enqueue(int data) // 삽입 함수 
     {
          if (queue_is_full()) // 큐가 가득 차 있는 경우 
          {
               cout << "큐가 가득 차 있습니다." << "\n";
               return; // 함수 종료 
          }
          else // 아닐 경우
          {
               queue_arr[rear++] = data;
               // 큐 배열 rear 위치의 데이터를 삽입 후 rear의 크기 1 증가
               // 위 코드가 이해가지 않는다면 후위 증감 연산자에 대해 공부할 것
               cout << "데이터 삽입 성공!" << "\n";
          }
     }
     void dequeue() // 삭제 함수 
     {
          if (queue_is_empty()) // 큐가 비어있는 경우 
          {
               cout << "큐가 비어있습니다." << "\n";
               return; // 함수 종료 
          }
          else // 아닐 경우 
          {
               cout << "반환 된 데이터 : " << queue_arr[front] << "\n"; // 데이터 반환 
               queue_arr[front++] = 0; 
               // 큐 배열 front 위치의 데이터를 삭제 후 front 크기 1 증가
          }
     }
     bool queue_is_empty() // 큐가 비어있는지 확인 함수 
     {
          if (front == rear) // front와 rear가 같은 위치라면
               return true;
          else // 아닐 경우 비어있지 않음 
          return false;
     }
     bool queue_is_full() // 큐가 가득 차 있는지 확인 함수 
     {
          if (rear == queue_size - 1) // rear가 큐 배열의 마지막 위치라면
               return true;
          else // 아닐 경우 가득 차 있지 않음 
               return false;
     }
     void print_queue() // 큐 배열 전체 출력 함수 
     {
          cout << "Queue : [ ";
          for (int i = 0; i < queue_size; i++)
          {
               if (i != queue_size - 1)
               {
                    cout << queue_arr[i] << " , ";
               }
               else
               {
                    cout << queue_arr[i];
               }
          }
     cout << " ] " << "\n";
     cout << "front 위치 : " << front << "\n";
     cout << "rear 위치 : " << rear << "\n";
     }
};

int main()
{
     queue *que;
     int input_size;
     cout << "큐 배열 크기 입력 : ";
     cin >> input_size;
     if (input_size <= 0)
     {
          cout << "잘못 된 입력입니다. 디폴트 사이즈(5)로 생성합니다." << "\n";
          que = new queue();
     }
     else
     {
          que = new queue(input_size);
     }
     while (1)
     {
          int input;
          cout << "\n" << "[명령어 입력]" << "\n";
          cout << "1. ENQUEUE " << "\n" << "2. DEQUEUE " << "\n" << "3. PRINT " << "\n" << "4. EXIT : ";
          cin >> input;
          switch (input)
          {
          case 1:
               int input_data;
               cout << "삽입 할 데이터를 입력하세요 : ";
               cin >> input_data;
               que->enqueue(input_data);
               break;
          case 2:
               que->dequeue();
               break;
          case 3:
               que->print_queue();
               break;
          case 4:
               cout << "프로그램을 종료합니다." << "\n";
               return 0;
          default:
               cout << "잘못 된 입력입니다. 다시 입력해 주세요" << "\n";
          }
     }     
}

질문 사항은 댓글로 남겨주세요!