C언어 파일 입출력

 

C언어에서 scanf와 printf 함수를 통해서 키보드로 입력을 받고 모니터로 출력해주는 그런 프로그램들을 많이 보았을 겁니다. 이런 키보드나 모니터같은 입출력 장비를 콘솔이라고 합니다. 그래서 콘솔 입출력을 해왔던 것이죠.

여기서는 파일 입출력에 대해서 설명합니다. 사실 콘솔 입출력과는 별로 다를바가 없습니다. 단지 그 대상이 모니터나 키보드가 아닌 파일이기 때문이죠. 본격적으로 파일 입출력을 설명하기 전에 우리는 스트림에 대한 개념을 먼저 알아야합니다. 

> 그전에 왜 C 표준입출력을 사용하나요?

리눅스를 배우셨던 분들은 open, read, write, close를 이용해서 파일을 다뤄보셨을 겁니다. 그때는 open에 필요에 따라 여러 플래그들을 줄 수가 있는데요. 예를 들어 O_RDONLY, O_CREAT 등 말이죠. 이거 구차하게 일일히 헤더 추가한 다음에 파일 디스크립터를 가져와서 write, read하는 것을 C 표준입출력 라이브러리에서는 stdio.h만 포함해서 사용할 수 있습니다.  아주 개꿀이라는 얘기죠. 그리고 변태같은 플래그들을 포함하지 않아도 사용하기에 적합한 플래그들을 미리 조합해놨기 때문에 상큼하게 그걸 사용하면 됩니다. 또한 내부적으로 버퍼를 사용하기 때문에 read, write 함수들을 최적으로 사용하게 됩니다.

 

스트림(Stream)

영어를 그대로 직영하게 되면 흐름이라는 건데요. 비슷하게 생각하시면 됩니다. 프로그램에서 파일이 열리면 C표준입출력은 스트림(stream)이라는 파일과 프로그램 사이의 추상적인 흐름이 일어나는 파이프를 생성합니다. 그래서 파일이 열리게 되면 개념적으로 스트림을 통해서 파일에 기록하거나 읽을 수 있습니다. 만약 파일을 읽기만 하겠다하면 읽기 전용의 스트림을 여는 것이고, 파일을 쓰기만 할 것이라면 쓰기 전용의 스트림을 열어서 거기에 기록을 하면 됩니다. 

그래서 아래와 같이 어떤 프로그램에서 File이라는 이름의 파일을 읽고 쓰기 위해서 스트림을 열면 아래와 같은 상황이 발생하게 됩니다. 그래서 바이트 단위던, 줄 단위던 입력이 흐름이 가능한 상태가 됩니다.

 

기본적으로 보통 프로그램에서는 3개의 스트림이 열려있습니다. 바로 표준 입력 스트림(stdin), 표준 출력 스트림(stdout), 표준 에러 스트림(stderr)입니다. 이 3개는 콘솔에 대해서 열려있는 스트림들입니다. 

 

stdin, stdout, stderr

키보드로 입력받고, 모니터로 출력하는 것도 C표준 입출력에서는 스트림으로 간주하게 됩니다. 그래서 우리가 stdin을 통해서 입력을 받는다면 키보드를 통해서 입력을 받는 것이고, 표준 출력 스트림으로 출력한다면 모니터 화면에다가 출력이 되는 겁니다. 그래서 파일 대신 모니터와 키보드가 스트림 끝에 놓여있는 것을 보세요.

 

 

파일의 종류 ( 텍스트 파일 , 이진 파일)

파일을 사람이 쓰고 읽냐, 컴퓨터가 쓰고 읽냐에 따라서 텍스트 파일(text-file), 이진 파일(binary-file)로 나누게 됩니다. 이와 같은 구분은 문자열로 입출력을 하느냐, 아니면 바이너리로 입출력을 하느냐를 위해서 구분합니다. 맨 처음 파일에 대해서 스트림을 생성할 때 결정이 됩니다.

 

1. 파일 열기 fopen

파일 함수는 표준입출력(stdio.h) 헤더파일에 존재합니다. 파일에 어떤 데이터를 읽고, 쓰고, 추가하려면 일단 파일을 열어야겠지요. 함수를 한번 보시죠.

FILE *fopen(const char *filename, const char *mode);

filename : 파일명을 말합니다. 절대 경로나 상대 경로로 줄 수 있습니다. 상대 경로는 그 프로젝트 위치를 기준으로 합니다.

mode : 파일을 어떤 방식으로 열건지 정합니다. 스트림 방식을 정하는 겁니다. 입력 스트림인지, 출력 스트림인지.

  -동작 모드

 모드  설명 flag 조합
 r(read)  1. 파일을 읽기 전용으로 엽니다. 
 2. 파일이 있어야합니다.
O_RDONLY
 w(write)  1. 파일을 쓰기 전용으로 엽니다.
 2. 주의해야합니다. 파일이 존재한다면 기존의 내용을 지우고 쓰기 때문이죠.

 3. 파일이 없으면 새로 생성합니다.
O_WRONLY | O_CREAT | O_TRUNC
 a(append)  1. 파일이 있으면 파일의 끝에 내용을 추가합니다.
 2. 파일이 없으면 생성해서 내용을 추가합니다.
O_WRONLY | O_CREAT | O_APPEND
 r+  1. 파일을 읽고 쓰기 위해 엽니다.
 2. 파일이 반드시 있어야 합니다.
O_RDWR
 w+  1. 파일을 읽고 쓰려고 엽니다.
 2. r+와 다르게 파일이 있는 경우 내용을 덮어쓰고 없으면 생성해서 데이터를 씁니다. 
O_RDWR | O_CREAT | O_TRUNC
 a+  1. 파일을 읽고 갱신하기 위해 엽니다.
 2. 파일이 없으면 생성해서 데이터를 추가합니다.
O_RDWR | O_CREAT | O_APPEND

 

  - 이진 또는 텍스트 모드(t, b)

텍스트모드가 기본(default)입니다. 이진 모드로 파일을 열려면 b를 추가합니다. 

ex) 이진모드로 읽기 위해 파일을 open -> rb

파일을 여는 데 성공했다면 그 파일에 대한 포인터를 return합니다.

하지만 파일을 여는 데 실패했으면 NULL을 반환하죠.

 

2. 파일 닫기 fclose

무엇이든 열었으면 닫는 것이 원칙이죠. 파일 스트림을 닫으려면 fclose를 사용하시면 됩니다.

int fclose(FILE *stream);

그냥 열었던 파일 포인터를 집어넣으면 됩니다. 성공하면 0을 반환하고 실패하면 EOF(-1)를 반환합니다.

 

3. 텍스트 파일 읽기 함수 

파일은 두 종류의 파일이 있다고 했죠? 사람이 읽을 수 있는 텍스트 형식의 파일과 컴퓨터가 읽고 처리하는 바이너리 파일, 즉 이진 파일이 있습니다. 우선 텍스트 파일을 읽는 함수는 쓰임새에 따라 여러가지가 있습니다.

    3.1 한문자 읽기 : fgetc, getc, getchar

#include <stdio.h>
int fgetc(FILE *stream);
int getc(FILE *stream);
int getchar(void);

fgetc와 getc는 같은 기능을 하는 함수입니다. getchar() 함수는 키보드용 한문자 입력을 받는 함수와 같아서 getc(stdin)과 같습니다. 

getc = getc , getc(stdin) = getchar()

stream에서 한 글자를 읽어오는 함수이며, 일반적으로 반환형은 한 글자의 ASCII값인 정수형 값입니다. 파일의 끝에 도달할 시에 EOF를 return합니다. EOF는 End-Of-File로 -1입니다. 이렇게 반환형이 (signed) int인 이유는 이 EOF를 반환받기 위해서입니다. 

    3.2 한 줄 읽기 : fgets

#include <stdio.h>
char *fgets(char *s, int size, FILE *stream);

stream에서 문자 한줄을 읽어올때 사용하는 함수이며 size 이하의 문자 한줄을 s로 읽어옵니다. 이때 개행문자까지 읽어옵니다. 그래서 개행문자('\n') 다음 문자의 끝을 나타내는 문자인 NULL('\0')이 붙습니다. 간단히 사용법을 확인해볼까요? 다음은 stdin으로 콘솔(키보드)로부터 입력을 받는 단순한 예제입니다.

//fgets_test.c
#include <stdio.h>
#include <string.h>

#define BUF_SIZE 32
int main(){

        char buf[BUF_SIZE] = {0,};

        printf("입력:");
        fgets(buf, BUF_SIZE, stdin);

        printf("출력:");
        printf("%s(%ld)", buf, strlen(buf));
}
# ./a.out 
입력:hello world
출력:hello world
(12)#

여기서 보이는 "hello world"의 문자열 길이는 공백을 포함해서 11글자이지만, 개행문자를 포함했기 때문에 12글자가 되고, 문자 길이도 한 줄 밑에 출력이 되었네요. 

    3.3 서식화된 파일 입력 : fscanf

#include <stdio.h>
int fscanf(FILE *stream, const char *format, ...);

키보드 입력에 대해서 입력 포맷팅 함수는 scanf였죠? 파일에 대해서 포맷팅 함수는 fscanf입니다. 

 

4. 텍스트 파일 쓰기 함수  

텍스트 파일에 쓰는 함수는 아래와 같습니다. 위의 텍스트 파일 읽기 함수의 네이밍을 따라갑니다. 함수에 대한 소개만하고 넘어가도록 합시다. 

    4.1 한문자 쓰기 : fputc, putc, putchar

#include <stdio.h>
int fputc(int c, FILE *stream);
int putc(int c, FILE *stream);
int putchar(int c);

   putchar(c)는 putc(stdout, c)와 같습니다.

    4.2 한 줄 쓰기 : fputs, puts

#include <stdio.h>
int fputs(const char *s, FILE *stream);
int puts(const char *s);

    4.3 서식화된 파일 출력 : fprintf

#include <stdio.h>
int fprintf(FILE *stream, const char *format, ...);

 

예제 - 텍스트 데이터 저장, 읽어오기

//writer.c

#include <stdio.h>
#include <string.h>

#define NUM 3

typedef struct _student{
        char name[16]; //이름
        unsigned int age; //나이 
        unsigned int id; //학번
} student;


int main(){
        int i;
        student s[NUM] = {
                {"park", 18, 1234},
                {"jung", 18, 1235},
                {"kim", 19, 1111}
        };
        FILE *fp;

        //텍스트 파일, 없으면 새로운 파일 생성, 있으면 내용 덮어쓰기(w+)
        fp = fopen("info.txt", "w+");
        if(fp == NULL) {
                printf("fopen error\n");
                return 1;
        }

        for(i = 0;i < NUM; i++){
                fprintf(fp, "%s %d %d\n",
                        s[i].name, s[i].age, s[i].id);
        }
        fclose(fp);
}
//reader.c
#include <stdio.h>

#define NUM 3

typedef struct _student{
        char name[16]; //이름
        unsigned int age; //나이 
        unsigned int id; //학번
} student;

int main(){
        int i;
        FILE *fp;
        student s[NUM]; 

        //테스트 파일 읽기 전용
        fp = fopen("info.txt", "r");
        if(fp == NULL){
                printf("fopen error\n");
                return 1;
        }
        for(i = 0; i < NUM; i++){
                fscanf(fp,"%s %d %d", 
                                s[i].name, &(s[i].age), &(s[i].id));

                printf("[%d]\n", i);
                printf("name : %s, age : %u, id : %u\n",
                                s[i].name, s[i].age, s[i].id);
        }
        fclose(fp);
}
# gcc reader.c -o reader
# ./writer
# cat info.txt
park 18 1234
jung 18 1235
kim 19 1111

writer만 실행해보면 info.txt가 생겨났고 그 내용은 이렇게 적혀있습니다. 사람이 알아볼 수 있죠?

# ./reader 
[0]
name : park, age : 18, id : 1234
[1]
name : jung, age : 18, id : 1235
[2]
name : kim, age : 19, id : 1111

reader라는 프로그램으로도 아주 잘 읽을 수 있습니다.

 

5. 이진 파일 읽기 fread

파일을 읽는 함수는 fread입니다. 프리드라고 읽지마세요 제발. 앞에 f는 모두 file의 f입니다. 앞에 f가 붙은 함수는 거의 다 파일에 대한 함수라는 것을 기억하세요.  

#include <stdio.h>
size_t fread(void *buffer, size_t size, size_t count, FILE *stream);

 

stream으로부터 자료형인 size를 count만큼 읽어서 buffer에 저장합니다. buffer가 void*인 이유는 어떤 자료형이건 받아와야하기 때문입니다.  파일을 읽은 길이(count)만큼 반환합니다. 

만약에 단순 바이너리를 읽는다면, 그러니까 바이트 단위를 읽는다면 size는 1입니다. 그러면 만약 크기 16바이트인 구조체를 3개를 읽는다면 아래와 같이 호출이 됩니다. 

fread(buffer, 16, 3, fp);

6. 이진 파일 쓰기 fwrite

파일에 쓰는 함수입니다. fread와는 반대 기능이죠.

#include <stdio.h> 
size_t fwrite(const void *buffer, size_t size, size_t count, FILE *stream);

buffer에 담긴 내용을 기록하는데 size만큼의 count 만큼 버퍼로부터 stream쪽으로 씁니다. 성공하면 count를 return하고 실패한다면 count가 아닐 수 있습니다.

 

예제 - 이진데이터 구조체 저장, 읽어오기

이진 파일을 사용할 수 있는 가장 큰 장점은 모든 자료를 이진데이터로 쓸 수 있다는 점입니다. 객체(구조체)도 그냉 냅다 쓸 수 있습니다. 모든 것을 이진 데이터로 쓰기 때문이지요. 다음은 구조체를 파일에 쓰고, 그 파일로부터 읽어오는 예제를 보여줍니다.

//info_writer.c
#include <stdio.h>

#define NUM 3

typedef struct _student{
        char name[16]; //이름
        unsigned int age; //나이 
        unsigned int id; //학번
} student;

int main(){
        FILE *fp;
        student s[NUM] = {
                {"kim", 16, 1234},
                {"lee", 16, 1235},
                {"lim", 17, 1111}
        };

        //이진(b)으로 쓰기용, 없으면 만들고 있으면 덮어쓴다(w+)
        fp = fopen("info.bin", "wb+");
        if(fp == NULL){
                printf("fopen error\n");
                return 1;
        }

        if(fwrite(s, sizeof(student), NUM, fp) != NUM){
                printf("fwrite erorr\n");
                fclose(fp);
                return 1;
        }

        printf("Student Information Saved OK \n");
        fclose(fp);
}

 

//info_reader.c
#include <stdio.h>

#define NUM 3

typedef struct _student{
        char name[16]; //이름
        unsigned int age; //나이 
        unsigned int id; //학번
} student;

int main(){
        int i;
        FILE *fp;
        student s[NUM]; 

        fp = fopen("info.bin", "rb"); //읽기 전용
        if(fp == NULL){
                printf("fopen error\n");
                return 1;
        }

        if(fread(s, sizeof(student), NUM, fp) != NUM){
                printf("fread erorr\n");
                fclose(fp);
                return 1;
        }

        for(i = 0; i < NUM; i++){
                printf("[%d]\n", i);
                printf("name : %s, age : %u, id : %u\n",
                                s[i].name, s[i].age, s[i].id);
        }
        fclose(fp);
}

 

# gcc info_writer.c -o writer
# gcc info_reader.c -o reader
# ./writer 
Student Information Saved OK 
# ./reader 
[0]
name : kim, age : 16, id : 1234
[1]
name : lee, age : 16, id : 1235
[2]
name : lim, age : 17, id : 1111

 

7. 버퍼 

버퍼는 C표준입출력에서 입력과 출력을 효율적으로 처리하기 위한 일종의 저장공간입니다. 내부적으로 write, read를 적시에 한번만 호출하기 위한 것이 목적입니다. 그런데 이러한 버퍼의 처리 방식을 잘 모르면 낭패를 볼 수 있는데요. 아래의 코드를 봅시다.

//buffer.c
#include <stdio.h>

int main(){

        char c;

        printf("아무 글자나 하나 입력:");
        scanf("%c", &c);
        printf("입력받은 글자 : %c\n", c);

        printf("다시 입력 : ");
        scanf("%c", &c);
        printf("입력받은 글자 : %c\n", c);
}

 

실행하게 되면 두 번재 scanf에 입력을 주기도 전에 프로그램이 끝나게 됩니다. 분명 scanf를 통해서 한글자 입력을 받는 코드를 작성했으에도 말이죠. 

# ./a.out 
아무 글자나 하나 입력:H
입력받은 글자 : H
다시 입력 : 입력받은 글자 : 
#

 

이 프로그램은 내부적으로 이렇게 동작하게 됩니다. 'H'라는 문자를 입력하면 내부적으로 엔터에 해당하는 개행 문자 '\n'도 입력이 됩니다.

 

결국 버퍼에는 H와 '\n'이 입력이 되게 되며 변수 c에는 'H'가 담기게 되겠죠. 버퍼에 남아있는 건 개행문자 '\n'입니다. 그래서 다음 scanf는 이 개행문자를 입력받아 입력이 끝나게 되는 겁니다. 

 

위는 줄 단위 버퍼링의 사례로 결국에는 남아있는 버퍼를 비워줘야합니다. 버퍼를 비워주는 방법에는 여러 가지 방법이 있는데요.

7.1 버퍼를 비우는 방법들

- 간단한 방법은 단순히 문자 하나 입력받는 거죠. 아래와 같이말이죠. 

printf("아무 글자나 하나 입력:");
scanf("%c", &c);
getchar();
printf("입력받은 글자 : %c\n", c);

printf("다시 입력 : ");
scanf("%c", &c);
getchar();
printf("입력받은 글자 : %c\n", c);

 

- fflush 함수 사용

#include <stdio.h>
int fflush(FILE *stream);

fflush 함수를 사용할 수가 있는데, 이 방법은 표준이 아니므로 권장되지 않습니다. 실제 제 ubuntu시스템에서는 동작하지 않습니다.

 

- scanf에서 공백 사용

scanf("%c", &c) -> scanf(" %c", &c)

 

앞에 공백 문자 하나를 넣어주세요. 

 

- 개행문자가 나올때까지 제거 

while(getchar() != '\n');

어떤 시스템에는 \r\n으로 개행합니다. 그게 윈도우즈인데, 이럴 때는 getchar()만 사용하게 되면 \r만 제거 됩니다. 그래서 아예 \n까지 제거 할 수 있도록 while문을 도는 방식을 사용할 수 있습니다. 약간 고급진 말로 '\r'은 커서를 맨 앞으로 돌리는 CR(Carriage return)이라 하며 '\n'은 커서는 그자리이며 라인만 바꾸는 LF(Line Feed)라고 합니다.  

반응형
블로그 이미지

REAKWON

와나진짜

,

연결형 큐


큐를 링크드리스트 형태로 구현할 수 있습니다. 스택에서처럼 말이죠. 스택과는 다르게 큐는 front와 rear가 있기 때문에 큐는 두개의 노드를 갖고 있어야합니다.


아래 그림처럼 말이죠.




큐의 특징은 알아보았으니(또는 이미 알고있거나) 어떻게 구현을 할 지 생각해보도록 합시다.




구현

이제 Node라는 구조체 변수를 갖는 LinkedQueue를 구현해보겠습니다. 하나하나 차근차근히요.

Node구조체는 아래와 같습니다. data와 다음 노드를 가리키기 위한 next변수를 가지고 있지요.


1
2
3
4
struct node {
    int data;
    struct node *next;
};

이제 LinkedQueue를 간단하게 정의해보지요.

1
2
3
4
5
6
7
8
struct LinkedQueue {
    Node *front, *rear;
    int len;
    LinkedQueue() {
        front = rear = NULL;
                len=0;
    }
};


구조체의 초기값을 정합니다. front와 rear를 갖고 있고 이 둘은 처음에는 가리키는 노드가 없으니까 NULL이 됩니다. 그리고 길이 역시 0입니다.


우리는 이제 size, isEmpty, enqueue, dequeue 4개의 연산을 구현해보도록 할겁니다. 링크드리스트로 구현하는 형태이기 때문에 그 크기가 가변적입니다. 그렇기 때문에 isFull연산은 없습니다.


1. size

뭐 간단하죠? 그냥 len만 반환하면 되니까요.

1
2
3
int size() {
    return len;
}


2. isEmpty

간단합니다. len이 0이면 그냥 비어있는 겁니다. 바로 이해할겁니다. 허나, front로도 구할 수 있습니다. front는 이제 꺼내야될 노드를 가리키는 녀석입니다. front가 NULL이라면 꺼낼 노드가 없게 되니까 큐가 비어있는 상태로 보면 되겠죠. 


코드는 아래와 같습니다. 주석을 해제하고 같은 결과가 나오는지 확인해보세요.

1
2
3
4
bool isEmpty() {
    //return front == NULL;
    return len == 0;
}




3. enqueue

큐에 노드를 집어 넣습니다. 일단 큐가 비어있다면 front와 rear는 처음 들어오는 노드를 가리킵니다.


하지만 큐가 비어있지 않는다면 rear을 이용해야합니다. rear의 다음 노드(rear->next)가 새로 들어온 노드가 됩니다. 이후 rear을 새로 들어온 노드로 가리키면 되는 것이죠.


큐에 데이터가 추가되었으니 길이는 하나 증가합니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
void enqueue(int data) {
    Node *node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    if (isEmpty()) {
        front = rear = node;
    }
    else {
        rear->next = node;
        rear = rear->next;
    }
    len++;
}


4. dequeue

큐에서 하나 꺼내는 연산인데요. 어디서 꺼내느냐. front가 가리키는 노드를 꺼내면 됩니다. 아참, 그전에 큐가 비어있는지 확인하는게 먼저겠죠. 큐에 내용이 있다면 front노드의 데이터를 하나 꺼내고, 임의로 node라는 포인터를 써 front가 가리키는 노드를 같이 가리키게 합니다. 그 이후 front->next로 front를 다음 노드로 가리킵니다. 그리고 메모리를 해제하면 됩니다. 


큐에서 데이터가 삭제됐으니 길이는 줄겠죠?


1
2
3
4
5
6
7
8
9
10
11
12
13
int dequeue() {
 
    if (isEmpty()) {
        cout << "Q is empty" << endl;
        return INF;
    }
    Node *delNode = front;
    int ret = delNode->data;
    front = delNode->next;
    free(delNode);
    len--;
    return ret;
}




전체코드


이제 전체코드를 보도록 해요. 메인에서는 큐에 1부터 5까지 삽입하고 다시 10을 삽입합니다. 결과는 어떻게 될까요?

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
#include <iostream>
#define INF 987654321
using namespace std;
struct Node {
    int data;
    Node *next;
};
 
struct LinkedQueue {
    Node *front, *rear;
    int len = 0;
    LinkedQueue() {
        front = rear = NULL;
    }
    int size() {
        return len;
    }
 
    bool isEmpty() {
        return len ==0;
    }
 
    void enqueue(int data) {
        Node *node = (Node*)malloc(sizeof(Node));
        node->data = data;
        node->next = NULL;
        if (isEmpty()) {
            front = rear = node;
        }
        else {
            rear->next = node;
            rear = rear->next;
        }
        len++;
    }
 
    int dequeue() {
         
        if (isEmpty()) {
            cout << "Q is empty" << endl;
            return INF;
        }
 
        Node *delNode = front;
        int ret = delNode->data;
        front = delNode->next;
        free(delNode);
        len--;
        return ret;
    }
};
 
int main() {
     
    LinkedQueue q;
    for (int i = 1; i <= 5; i++)
        q.enqueue(i);
 
    q.enqueue(10);
 
    while (!q.isEmpty())
        cout << q.dequeue() << endl;
     
}

원하는 대로 결과가 나왔나요?




여기까지 큐를 링크드리스트로 구현하는 방법을 알아보았습니다. 링크드리스트로 구현한 큐이든, 선형큐이든 항상 무슨 프로그램을 구현할 것인지 고려하여 쓰기 바랍니다.

반응형
블로그 이미지

REAKWON

와나진짜

,

큐(Queue)


스택과 양대산맥인 큐는 스택과 반대의 성격을 지닌 녀석입니다. 스택이 후입선출(Last In First Out)방식이었다면 큐는 선입선출(First In First Out)방식이 되지요. 스택과 큐는 컴퓨터 과학에서 아주 중요한 도구들입니다. 스택의 개념과 사용처는 지난 포스팅에서 했으니, 큐에 대해서만 설명해보도록 하겠습니다.


큐는 개념은 정말 쉽습니다. 첫번째로 들어오는 녀석을 가장 먼저 내보내는 것이 큐입니다. 현실 세계에서도 역시 큐에 개념이 사용됩니다. 버스 기다릴때나 은행 업무를 기다릴때, 가장 먼저 도착한 사람이 버스를 타거나 은행업무를 보게 되지요. 새치기하지마라 진짜





'


위의 그림 처럼 말이죠. 그냥 쭉 줄서있죠? 이런 큐를 선형큐라고 합니다.


그림에서는 보이진 않지만 가장 앞에 있는 원소를 Front, 그리고 가장 뒤에 있는 원소를 Rear라고 합니다.


큐에는 기본적으로 두 가지의 연산이 있습니다. 바로 enqueue와 dequeue입니다.


enqueue 큐에 데이터를 삽입합니다.

dequeue 큐에서 데이터를 꺼내옵니다.


선형큐는 구현하는 게 매우 간단하지만( 단지 배열로 일직선으로 구현) 치명적인 약점이 있는데요.


1) 큐에 데이터가 꽉 찼다면 데이터를 더 추가할 수 없습니다(물론 큐 사이즈를 늘리고 원소를 다시 복사하면 됩니다. 근데 시간이 안습이죠.). 


2)공간의 효율성을 고려해야합니다. 배열로 단순히 구현하면 front가 뒤로 계속 밀려 앞의 공간이 남게 되죠. 그러니까 하나의 원소가 빠져나가면 그 다음부터 모든 녀석들을 앞으로 당겨와야하니까 속도 측면에서 상당히 느립니다. 작은 데이터들이라면 물론 상관없지만, 요즘처럼 사이즈가 크고 많은 데이터를 처리하기에는 무리죠.


사용하기에는 단점이 좀 아프니까 선형큐는 개념 정도만 알고 가겠습니다.




원형큐(Circular Queue)

선형큐의 단점을 보완할 수 있는 큐로는 바로 원형큐가 있습니다. 큐를 직선 형태로 놓는 것 보다 원형으로 생각해서 큐를 구현하는 것이죠. 큐를 원형으로 생각해야되기 때문에 모듈러 연산(나머지 연산)을 해야합니다.


그림으로 설명해보도록 하지요.





우선 큐의 시작점은 어느 점이라도 됩니다. 그냥 단순히 보기 위해서 가장 아래에 있는 점을 시작 점이라고 정의해보겠습니다.


그리고 색이 칠해져있는 부분이 노드가 삽입된 상태입니다.


또한, front가 노드를 가리키고 있지 않고 그 전의 점을 가리키고 있는 이유는 우선 증가 연산 후에 데이터를 꺼내오기 때문입니다.

 


우리는 아래 구조체를 코딩을 통해서 큐를 구현할 겁니다. SIZE는 원형큐의 SIZE를 의미합니다. 그리고 front와 rear가 배열의 마지막 원소로 지정한 것은 배열 인덱스 0부터 시작하려고 하기 때문입니다(선증가 후 원소를 삽입한다는 사실만 지금은 기억하기 바랍니다.). 뭐 front와 rear를 0으로 하건 1로하건 상관없습니다.


1
2
3
4
5
6
7
8
9
10
struct cirQueue {
     
    int arr[SIZE];
    int front, rear;
     
    cirQueue() {
        front = SIZE-1;
        rear = SIZE-1;
    }
};


cirQueue()는 front와 rear의 초기값을 지정합니다. 이렇게 하고 싶지 않다면  변수를 선언할때 일반적인 구조체를 다루듯이 

cirQueue q;

q.front=q.rear=SIZE-1;

이런식으로 코딩하면 됩니다.


우리는 이제 4가지의 연산을 정의할 건데요. 잘 따라오세요.




1. isEmpty

큐가 비어있냐 아니냐를 질의하는 연산입니다. 처음 큐의 rear와 front는 같은 자리에 위치하게 됩니다. 그러니 rear와 front는 당연히 같은 값이 되지요. 그리고 큐가 삽입되고 꺼내어지고 할 때 역시 큐가 비어있게 된다면 rear와 front는 역시 같은 값이 됩니다. front를 하나 증가하고 난 이후에 데이터를 꺼내오니까요.




코드도 역시 간단하게 구현이 되는 군요.

1
2
3
bool isEmpty() {
        return rear == front;
}


2. isFull

큐에 데이터가 꽉차있는 상태인지 알아보는 연산입니다. rear를 하나 증가시키고 데이터를 넣으려보니까 그 자리에는 front라는 것이 자리잡고 있는 겁니다. 


여기서 중요한 사실은 큐에서 1개는 쓸 수 없다는 사실입니다. rear+1자리에 front가 있는 지 알아보기 위해서지요.





1
2
3
4
<p>bool isFull() {
        return ((rear + 1) % SIZE) == front;
}
</p>


여기서 큐의 SIZE로 나누는 이유는 계속 rear+1이 큐의 SIZE보다 클 수 있다는 겁니다. rear가 SIZE-1의 원소(배열의 마지막 원소)를 가리키고 있고 다음 rear+1은 SIZE가 아니라 0이 되어야합니다. 그래야 원형큐가 되니까요.


아참! 간간히 눈에 보이지 않는 오류가 있는데 수식을 잘 보셔야됩니다. 덧셈보다 모듈러 연산의 우선순위가 더 높기 때문에 (rear +1 % SIZE) == font 를 하게 되면 1%SIZE 부터 계산하게 됩니다. 우리가 원하는 것은 rear를 먼저 1증가시킨 후 SIZE로 나눈 나머지를 구하는 것이니 괄호를 처리해야 합니다. 

( (rear + 1) % SIZE ) == front 로요.




3. enqueue

큐에 원소를 삽입하는 연산입니다. 우선 큐가 꽉차있는 상태인지 아닌지 부터 알아봅니다. 삽입하기 충분한 공간이 있다면 현재 rear에서 1을 증가시킵니다 다음 원소에 추가시키기 위해서요. 그자리에 원소를 삽입하면 됩니다. 


여기서도 역시 나머지 연산이 들어갑니다. 원형큐이기 때문에 SIZE보다 크면 다시 처음부터 원소가 삽입되어야 하기 때문입니다.


1
2
3
4
5
6
7
8
void enqueue(int data) {
        if (isFull()) {
            cout << "Q is full" << endl;
            return;
        }
        rear = (rear + 1) % SIZE;
        arr[rear] = data;
}

4. dequeue

큐에 원소를 꺼내어 오는 연산입니다. 맨 처음 들어간 원소는 front+1이 됩니다. 그러니까 우선 큐가 비어있는 지 확인하는 작업이 필요합니다. 비어있는 큐에 원소를 꺼내올 수 없으니까요.


이후 front를 한칸 증가시켜 그 원소를 빼내옵니다. 그러고 나면 front는 빈 원소를 가리키게 되는 것이죠.


역시 모듈러 연산이 쓰이는 군요. 이유는 위와 같습니다.



1
2
3
4
5
6
7
int dequeue() {
        if (isEmpty()) {
            cout << "Q is empty" <<endl;
            return INF;
        }
        return arr[front = (front + 1) % SIZE];
}



전체 코드

이렇게 큐의 연산을 모두 끝냈습니다. 전체 코드는 아래에 있습니다.

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
#include <iostream>
#define INF 987654321
#define SIZE 6
using namespace std;
 
struct cirQueue {
     
    int arr[SIZE];
    int front, rear;
     
    cirQueue() {
        front = SIZE-1;
        rear = SIZE-1;
    }
     
    bool isEmpty() {
        return rear == front;
    }
     
    bool isFull() {
        return ((rear + 1) % SIZE) == front;
    }
 
    void enqueue(int data) {
        if (isFull()) {
            cout << "Q is full" << endl;
            return;
        }
        rear = (rear + 1) % SIZE;
        arr[rear] = data;
    }
 
    int dequeue() {
        if (isEmpty()) {
            cout << "Q is empty" << endl;
            return INF;
        }
        return arr[front = (front + 1) % SIZE];
    }
};
 
int main() {
     
    cirQueue q;
    for (int i = 1; i <= 6; i++)
        q.enqueue(i);
    q.enqueue(10);
    while (!q.isEmpty())
        cout << q.dequeue() << endl;
    cout << q.isEmpty() << endl;
    cout << q.isFull() << endl;
}


결과는?


메인함수에서 코드를 보면 왜 이렇게 결과가 나오는지 이해할 수 있을 겁니다.

반응형
블로그 이미지

REAKWON

와나진짜

,