3-2 자료구조 - queue

수정 필요
2-1 문자열 입력 받는거랑 같은 문제 (한글 최대 4자)
1. fgets로 이름 입력을 받는데, 사이즈를 넘어가면 stdin에 남아있음
입력버퍼는 따로 while 반복문으로 제거함.
따라서 이름을 입력할때 사이즈 오버되어도 괜찮음.
2. 문제는 사이즈를 오버하지 않으면, stdin에 아무것도 남지 않음
fgets는 \n을 포함해서 저장하니까 \n이 같이 출력됨 <<수정해야함
사이즈를 오버하지 않을때, 마지막 문자가 \n이라면, \0으로 바꿔주면 되는데
str[strlen(str)-1]='\0'
오버하지 않을때랑 오버할때 구분하는법을 찾아야함

입력버퍼 처리

1. 개행문자 자리에 강제로 널문자 넣어줌
   문제-fgets는 잘 받아지는데, 인원 수 입력을 건너뜀.

fgets(input, sizeof(input), stdin);
if (input[strlen(input)-1] == '\n')
	input[strlen(input)-1] = '\0';
while (getchar() != '\n') {};

2. 표준 fflush 함수로 비우기
   문제-안 먹힘

fgets(input, sizeof(input), stdin);
fflush(stdin);

3. 4글자 초과시에는 잘 적용됨
문제-4글자 이하를 받으면 \n을 한번 더 입력해야 인원 수 입력을 받음

fgets(input, sizeof(input), stdin);
int ch;
while ((ch = getchar()) != EOF && ch != '\n') {};

4. 문제-안 먹힘

fgets(input, sizeof(input), stdin);
fseek(stdin, 0, SEEK_END);

5. 3번과 같은 문제

if (fgets(input, sizeof(input), stdin) == NULL) {
	if (feof(stdin))
    	return 0;
	else {
    	perror("Could not read from stdin");
		exit(1);
	}
}
else if (strchr(input, '\n') == NULL) {
	int c;
	while (c = getc(stdin) != '\n' && c != EOF) {};
    fprintf(stderr, "Input too long\n");
}

6. 입력 받은 문자열은 개행문자로 구분되어 잘림
   문제-문자열은 4글자 안으로 잘 들어오는데, 인원 수 입력을 건너뜀

fgets(input, sizeof(input), stdin);
strtok(input, "\n");

7. 문제-인원 수 입력을 건너뜀

char input[NAME_LEGNTH];
char* p;
if (fgets(input, sizeof(input), stdin) != NULL) {
	p = strchr(input, '\n');
    if (p)
    	*p = '\0'; //개행문자에 널문자로 바꾸어줌
    else
    	puts("에러");
}

Queue 개념

선입선출 FIFO 방식의 자료구조
순서 있는 리스트
스택과 마찬가지로 배열과 연결리스트로 구현이 가능합니다.
활용 예시 - 프린터 인쇄 대기열, 프로세스 관리, 은행 업무, 너비 우선 탐색 구현, 캐시 구현
1. 삽입 연산은 한쪽 끝인 rear에서 일어납니다.
2. 삭제 연산은 삽입의 반대쪽인 front에서 일어납니다.

• 선형 큐
  • 삽입을 계속하기 위해서는 요소들을 이동시켜야 합니다.
  • 인덱스를 감소하지 않고 증가만 하는 방식이기에, 실제로 앞부분에 데이터가 없을 때에는 비어있는 공간을 활용할 수 없습니다.
• 원형 큐
  • 큐에서 원소가 최대로 삽입되면 큐가 full이 됩니다. (isEmpty()랑 isFull() 동시에 참인 경우도 있음)
  • 배열을 원형으로 만들고 원형 배열에 데이터를 저장합니다.
  • 초기값 front와 rear는 -1이 아닌 0으로 설정합니다.
  • 공백상태: front == rear
  • 포화상태: front == (rear+1) % Max_Q_Size
    • 전체 5인 큐에서, rear가 2에 있으면, front는 (2+1) % 5 == 3임

과제 - 1 (연결리스트 선형큐)

좌석 대기 프로그램

1. 대기자 이름과 인원 수를 입력 받습니다.
2. 입력한 대기자가 10명을 초과하거나, "exit" 입력 시 대기자 입력을 종료합니다.
3. 이름은 한글로 최대 4자 입력합니다. 에러 출력
4. 인원 수는 정수로 1~4로 입력. 해당 범위를 벗어나면 에러 출력 이름을 다시 입력 받습니다.
5. 대기자 입력이 완료된 경우 "대기자 입력이 완료되었습니다." 라고 출력합니다.
6. 유휴 좌석 수를 입력 받습니다. 값은 1, 2, 4만 가능합니다. 해당 범위를 벗어나면 에러 출력 다시 입력받습니다. 현재 대기자수: xx 유휴 좌석수: __
7. 대기자 중에서 인원수가 "유휴 좌석 수보다 작거나 같으면" 가장 빠른 순번을 대기자 리스트에서 제거하고, 화면에 사람 이름과 인원 수를 출력합니다. 입장하실 분: 이름(인원 수)
   반대로 인원수가 "유휴 좌석 수보다 크면" 해당 유휴 좌석은 스킵 처리됩니다. 조건에 만족하는 대기자가 없다는 뜻이니 조건에 만족하는 사람이 없습니다.라고 출력하고 유휴 좌석 수를 다시 입력 받습니다.
8. 유휴 좌석 수 입력은 모든 대기자가 없어질 때까지 반복해서 입력 받고, 모든 대기자가 없어지면 프로그램을 종료합니다.

#include <stdio.h>
#include <stdlib.h>                         //malloc, free
#include <string.h>                         //strlen

enum { NAME_LENGTH = 13, MAX_PERSON = 10,
        NAME_LENGTH_ERROR = -13, PERSON_RANGE_ERROR = 6, SEAT_RANGE_ERROR = 7,
        EMPTY_QUEUE = -1, DEQUEUE_SUCCESS = 1 };

typedef struct _Person {                    //대기자 정보
    char name[NAME_LENGTH];                 //이름 - UTF-8은 한글 1글자를 3바이트로 저장
    int num;                                //인원수
    struct _Person* next;                   //다음 노드를 가리키는 포인터
} Person;

typedef struct _Queue {
    Person* front;
    Person* rear;
    int count;                              //큐 안의 노드 갯수 - 최대 10개
} Queue;

void Init(Queue* q);                        //큐 초기화
int isEmpty(Queue* q);                      //큐가 빈 경우 True(1), 않은 경우 False(0)
void Enqueue(Queue* q, char c[], int n);    //큐에 데이터를 저장
int Dequeue(Queue* q);                      //데이터 삭제 및 삭제된 데이터를 반환
int PERSON_RANGE_CHECK(int n);              //인원 수 범위 체크
int SEAT_RANGE_CHECK(int n);                //유휴 좌석 수 범위 체크

void Init(Queue* q)
{
    q->front = q->rear = NULL;
    q->count = 0;
}

int isEmpty(Queue* q)
{
    return (q->count == 0);
}

void Enqueue(Queue* q, char c[], int n)
{
    Person* p = (Person *)malloc(sizeof(Person)); //새로운 노드인 p(대기자 정보)를 동적할당함
    int j = 0;
    for (int i = 0; i < (int)strlen(c); i++) { //전달받은 char배열(대기자 이름)을 하나하나 대입함
    	p->name[j] = c[i];
        j++;
    }
    p->name[j] = '\0'; //문자열 끝에 널문자 포함
    p->num = n; //대기 인원수
    p->next = NULL; //p가 가리키는 next는 일단 없으니까 NULL

#ifdef DEBUG
    printf("Enqueue된 이름: %s\n", p->name);
    printf("Enqueue된 인원 수: %d\n", p->num);
#endif

    if (isEmpty(q)) //초기 상태에는 큐가 비어있으니까
        q->front = p; //front에 p를 넣어줌
    else //나머지 모두 rear 뒤쪽에 푸쉬해야함
        q->rear->next = p; //따라서 rear의 next에 p를 넣어줌

    q->rear = p; //p는 마지막에 들어온 노드임 (초기 상태에는 p는 front이자 rear임)
    q->count++; //큐 갯수 1 증가

#ifdef DEBUG
    printf("큐에 들어있는 노드의 갯수: %d\n", q->count);
#endif
}

int Dequeue(Queue* q)
{
    if (isEmpty(q)) {
        puts("큐가 이미 비어있습니다.");
        return EMPTY_QUEUE; //-1
    }

    Person* temp = q->front; //맨 앞 노드를 삭제하기 위해 만든 임시노드

    char* str = malloc(NAME_LENGTH); //임시 노드의 이름을 str에 넣어줌 (malloc으로 초기화)
    int j = 0;
    for (int i = 0; i < (int)strlen(temp->name); i++)
            str[j++] = temp->name[i];
    str[j] = '\0';

    int n; //임시 노드의 인원 수를 n에 넣어줌
    n = temp->num;

    q->front = temp->next; //맨 앞 원소는 결국 맨 앞의 다음 노드를 가리킴
    free(temp); //맨 앞 원소 삭제
    q->count--; //큐 갯수 1 감소

    puts("==================");
    printf("입장하실 분: %s(%d)\n", str, n); //디큐와 동시에 팀의 이름과 인원수를 출력함
#ifdef DEBUG
    printf("큐에 들어있는 노드의 갯수: %d\n", q->count);
#endif

    return DEQUEUE_SUCCESS; //1
}

int PERSON_RANGE_CHECK(int n)
{
    if (n < 1 || n > 4) {
        puts("인원 수는 1부터 4까지입니다. 다시 입력해주세요.");
        return PERSON_RANGE_ERROR; //6
    }
    return 0;
}

int SEAT_RANGE_CHECK(int n)
{
    if (n != 1 && n != 2 && n != 4) {
        puts("유휴 좌석 수는 1, 2, 4만 가능합니다. 다시 입력해주세요.");
        return SEAT_RANGE_ERROR; //7
    }
    return 0;
}

int main()
{
    Queue q;
    Init(&q);

    char input[NAME_LENGTH];
    int numPerson;
    int numSeat;

    /* 대기자 정보 입력 */
    do {
        puts("==================");
        printf("현재 대기자 수: %d\n", q.count);
        printf("대기자 이름: ");

        fgets(input, sizeof(input), stdin);
        int ch;
        while ((ch = getchar()) != EOF) && ch != '\n') {};
        while (ch == '\n')
            ch = '\0';

        if (strcmp(input, "exit\n") == 0) { //위에서 개행문자 처리 못해서 exit\n..
            puts("대기자 정보 입력을 종료합니다."); 
            puts("==================");
            break;
        }

        do {
            printf("대기 인원수: ");
            scanf("%d", &numPerson);
            while (getchar() != '\n') {};
        } while (PERSON_RANGE_CHECK(numPerson));

        Enqueue(&q, input, numPerson);

        puts("대기자 입력이 완료되었습니다.");
        puts("==================");
    } while (q.count < MAX_PERSON); //대기자가 10명을 넘기면 반복문 중지

    /* 유휴 좌석 수 입력 */
    do {
        do {
            printf("현재 대기자 수: %d\n", q.count);
            printf("유휴 좌석 수: ");
            scanf("%d", &numSeat);
        } while (SEAT_RANGE_CHECK(numSeat)); //유휴 좌석 수를 제대로 입력 받으면 반복문 중지

        if (!isEmpty(&q) && //큐가 비어있지 않고,
            q.front->num <= numSeat) { //인원 수가 유휴 좌석 수보다 작거나 같으면
            Dequeue(&q); //가장 빠른 순번을 제거
        }
        else { //해당 유휴 좌석은 스킵 처리
            puts("조건에 만족하는 사람이 없습니다.");
            puts("유휴 좌석 수를 다시 입력해주세요.");
            puts("==================");
        }
    } while (!isEmpty(&q));

    return 0;