Special Effects FX 스스로를 감동시켜야 최선을 다 한 것이다.

원형 큐를 연결 리스트를 기반으로 구현하는 경우에는 의외로 신경 쓸 부분이 적다.

스택과의 차이점

- 스택은 push와 pop이 이뤄지는 위치가 같은 반면, 큐는 enqueue와 dequeue가 이뤄지는 위치가 다르다.

Header File

Source File

Main File

실행 결과

큐의 활용

큐는 운영체제 및 네트워크와 관련된 소프트웨어의 구현에 있어서 중요한 역할을 담당하는 자료구조이다. 

그리고 '큐잉 이론(Queuing Theory)' 이라는 학문에서는 수학적으로 모델링 된 결과의 확인을 위해서 특정 현상을 '시뮬레이션(simulation)' 하게 되는데, 이때에도 큐는 중요한 역할을 담당한다. 

F(Front), R(Rear)

F는 큐의 머리를, R은 큐의 꼬리를 가리키는 일종의 변수를 의미.

R이 배열의 끝에 도달하면, 다시 맨 앞으로 이동시켜서 R이 회전하게 만든다. 물론 R을 뒤쫗아 가는 F도 배열의 끝에 도달하면 회전해야 한다. 그리고 이러한 방식으로 동작하는 배열 기반의 큐를 가리켜 '원형 큐(Circular Queue)' 라 한다. 

논리적으로 배열이 원형의 형태를 갖춘다고 해서 붙여진 이름이다.

원형 큐의 문제점

원형 큐는 F와 R의 위치만 가지고는 꽉 찬 경우와 텅 빈 경우를 구분할 수가 없다.

원형 큐의 문제해결

배열을 꽉 채우지 않는다. 꽉 차면 구분이 안되니 꽉 채우지 않는다.

즉, 배열의 길이가 N이라면 데이터가 N-1개 채워졌을 때, 이를 꽉 찬 것으로 간주한다.

이렇게 하면 저장 공간 하나를 낭비하지만 이로 인해서 문제 하나가 해결이 되는 셈이니 잃는 것보다 얻는 것이 더 많다.

실제 큐의 구현을 위해서 인지하고 있어야 하는 2가지

1. enqueue 연산 시, R이 가리키는 위치를 한 칸 이동시킨 다음에, R이 가리키는 위치에 데이터를 저장한다.

2. dequeue 연산 시, F가 가리키는 위치를 한 칸 이동시킨 다음에, F가 가리키는 위치에 저장된 데이터를 반환 및 소멸한다.

이 중에서 특히 dequeue 연산 시에도 F가 가리키는 위치를 우선 한 칸 이동한다는 사실을 잊어선 안된다.

이로써 구현할 큐의 특성 두 가지를 다음과 같이 추가로 정리할 수 있다.

# 원형 큐가 텅 빈 상태        -        F와 R이 동일한 위치를 가리킨다.

# 원형 큐가 꽉 찬 상태        -        R이 가리키는 위치의 앞을 F가 가리킨다.

Header File

Source File

Main File

큐의 이해

큐는 스택과 함께 언급되고 또 비교되는 자료구조이다.  스택은 먼저 들어간 데이터가 나중에 나오는 구조인 반면, 큐는 먼저 들어간 데이터가 먼저 나오는 구조이다. 이것이 스택과 큐의 유일한 차이점이다.

큐의 자료구조를 실생활에서 예를 들자면 터널, 고무 호스, 양쪽으로 구멍 난 통, 줄을 서는 것 등등이 있다. 

이렇듯 큐는 '선입선출' 구조의 자료구조이다. 때문에 FIFO(First-In, First-Out) 구조의 자료구조이다.

큐의 ADT 정의

스택과 마찬가지로 큐의 ADT도 정형화된 편이다. 큐의 핵심 연산

enqueue        : 큐에 데이터를 넣는 연산

dequeue        : 큐에서 데이터를 꺼내는 연산

보편적인 큐 자료구조의 ADT

void QueueInit(Queue * pq);

- 큐의 초기화를 진행한다.

- 큐 생성 후 제일 먼저 호출되어야 하는 함수이다. 

int QIsEmpty(Queue * pq);

- 큐가 빈 경우 TRUE(1)를, 그렇지 않은 경우 FALSE(0)를 반환한다.

void Enqueue(Queue  * pq, Data data);

- 큐에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.

Data Dequeue(Queue * pq);

- 저장순서가 가장 앞선 데이터를 삭제한다.

- 삭제된 데이터는 반환된다.

- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

Data QPeek(Queue * pq);

- 저장순서가 가장 앞선 데이터를 반환하되 삭제하지 않는다.

- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

Stack 자료구조로 구현 된 계산기

InfixCalculator

InfixCalculator.c

InfixCalculator.h

InfixToPostfix.c

InfixToPostfix.h

ListBaseStack.c

ListBaseStack.h

main.c

PostCalculator.c

PostCalculator.h

warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result

이 경고문은 scanf 함수가 자체적으로 int형 리턴 값을 반환하는데 그것을 무시했다는 경고의 메시지이다.

즉, 이 경고를 보이지 않게 하려면 scanf 함수의 리턴 값을 받아주면 된다.

scanf 함수는 정상적으로 작동했을 시 1을 반환하고, 에러가 났을 시 1이 아닌 값을 반환하니까 이것을 토대로 리턴 값을 받아주면 되겠다.

#include <stdio.h>

int main() {
    int t;
    if(scanf("%d", &t) == 1) {
        printf("%d", t);
    } else {
        printf("failed to read integer.\n");
    }
    return 0;
}

void * memset(void * ptr, int val, size_t len);

-> ptr로 전달된 주소의 메모리에서부터 len 바이트를 val의 값으로 채운다.

-> ctype.h 표준 헤더파일을 포함해야 한다.

int isdifit(int ch);

-> ch로 전달된 문자의 내용이 10진수라면 1을 반환한다.

-> string.h 표준 헤더파일을 포함해야 한다.

중위 표기법(infix notation)        =>        예) 5 + 2 / 7            예) (1 + 2) * 7

전위 표기법(prefix notation)        =>        예) + 5 / 2 7            예) * + 1 2 7

후위 표기법(postfix notation)        =>        예) 5 2 7 / +            예) 1 2 + 7 *

이 중에서 우리에게 익순한 것은 '중위 표기법'이다. 그러나 중위 표기법을 이용해서 작성된 수식에는 연산순서에 대한 정보가 담겨있지 않다.

나눗셈이 덧셈보다 우선순위가 높다는 사실을 알고 있기 때문에 가능한 것이지 만약, 처음 보는 낯선 연산자가 중위 표기법에 존재한다면 연산의 순서를 판단하기는 곤란할 것이다.

하지만 익숙지 않은 '전위 표기법의 수식'이나 '후위 표기법의 수식'에는 연산순서의 정보가 담겨 있다. 

연산자의 종류나 우선순위를 알지 못해도, 연산자가 자리한 위치만 보고서도 다음과 같은 판단이 가능하다.

"OP1이 먼저 등장했으니 OP1 연산을 하고 나서 OP2 연산을 해야겠다."

이렇듯 '전위 표기법으로 작성된 수식'과 '후위 표기법으로 작성된 수식'에는 배치순서를 근거로 한 연산순서의 정보가 담기기 때문에, 이를 대상으로 한 연산에서는 연산자의 우선순위가 필요치 않다.

다시 말해서 연산자의 우선순위란 중위 표기법만을 위한 것이다.

뿐만 아니라, 연산자의 배치순서를 바꿈으로써 연산의 순서를 바꿀 수 있기 때문에, 소괄호를 필요로 하지도 않는다.

즉 소괄호도 중위 표기법만을 위한 것이다.

중위 표기법: 3 + 2 * 4        =>        후위 표기법: 3 2 4 * +

중위 표기법: 2 * 4 + 3        =>        후위 표기법: 2 4 * 3 +

중위 표기법: 2 * 1 + 3 / 2        =>        후위 표기법: 2 1 * 3 2 / +

※ 참고로 프로그램상에서 작성되는 연산문도 컴파일러에 의해서 후위 표기법으로 바뀌어 처리가 된다.

후위 표기법의 수식에서는 연산자의 앞에 등장하는 두 개의 숫자가 피연산자입니다.

ex) 3 * 2 + 4    =>    3 2 * 4 +    =>    6 4 +    =>    10

HDK User Reference

Users writing plugins may appreciate a key for the library prefixes used in the HDK:

Prefix  Meaning

AU -     Audio

FS -     File System

GB -     Geometry Base Classes

GD -     Geometry Domain (2d profile curves)

GDT -     Geometry Delta. This is for the efficient representation of thedifferences between two geometries. It is used by the Edit, Paint, andsimilar SOPs.

GEO -     Geometry (3d)

GOP -     Geometry Group Operations. Has the pattern matching code used bySOPs.

GP -     Geometry Pasting (used for NURBs pasting)

GQ -     Geometry Quad Edge library

GU -     Geometry Utility (derives from GEO through multiple inheritence)

GVEX -     Wrapper for VEX to access Geometry

KIN -     Kinematics

SYS -     System Dependent

TS -     Metaball Kernel Library

UT -     Utility