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

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

내가 필요로하는 것이 존재하지 않을 때 다음 두 가지 방법중 하나를 선택해야 한다.

1. 처음부터 새로 만든다.

2. 기존의 것을 활용해서 만든다.

상황에 따라 좋은 선택은 달라지기 마련이다. 마땅히 활용할 대상이 없거나 활용의 결과가 만족스럽지 못하다면 처음부터 새로 만들어야겠지만, 그렇지 않은 경우라면 기존의 것을 활용하는게 훨씬 합리적인 판단일 수 있다.

CLinkedList.c

CLinkedList.h

기능적인 부분만 고려를 한다면 배열은 대부분 연결 리스트로 교체가 가능하다. 배열도 연결 리스트도 기본적인 선형 자료구조이기 때문이다.

head -> data1 -> data2 -> data3 -> NULL

이렇게 메모리 구조만 놓고 보면 이것이 스택을 구현한 것인지, 단순 연결 리스트를 구현한 것인지 알 수 없다.

다만 위의 메모리 구조를 바탕으로 push 연산과 pop 연산이 포함된 ADT를 갖는다면 이것이 스택이 되는 것이다.

스택이란 '쟁반 위에 쌓인 접시', '쌓아 올려진 상자더미' 를 연상할 수 있겠다.

즉, 맨 밑에 상자(제일 먼저 들어간 데이터) 를 꺼내려면 위에 얹혀있는 상자들부터 꺼내야 꺼낼 수 있다. 이것이 바로 스택의 특성이다.

스택은 나중에 들어간 것이 먼저 나오는 구조이다 보니 '후입선출방식의 자료구조' 라고도 불리고, 영어로 'LIFO(Last-In, Fisrt-Out) 구조의 자료구조' 라고도 불린다.

실제로 스택은 쉽게 이해할 수 있고 또 숩게 구현할 수 있는 자료구조이다.

스택을 대표하는 넣고, 꺼내고, 들여다 보는 연산을 가리켜 각각 push, pop, peek 라고 한다.

void StackInit(Stack * pstack); 

- 스택의 초기화를 진행한다.

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

int IsEmpty(Stack * pstack);

- 스택이 빈 경우 TRUE(1)을 그렇지 않은 경우 FALSE(0)을 반환

void Push(Stack * pstack, Data data);

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

Data Pop(Stack * pstack);

- 마지막에 저장된 요소를 삭제

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

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

Data Peek(Stack * pstack);

- 마지막에 저장된 요소를 반환하되 삭제하지 않는다.

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

실행결과에서 입력된 데이터가 역순으로 출력됨을 보이고 있다. 

그리고 이것이 스택의 가장 중요한 특성이다.

데이터를 저장할 때, 리스트의 머리와 꼬리에 각각 더미 노드가 존재하기 때문에 추가의 방법에 있어서 경우의 수가 나뉘지 않는다.

새 노드를 추가할 때의 과정

1. 새 노드를 생성하고 데이터를 저장

2. 새 노드와 새 노드의 왼쪽에 위치할 노드가 서로를 가리키게 한다.

3. 새 노드와 새 노드의 오른쪽에 위치할 노드가 서로를 가리키게 한다.

즉, 이렇게 된다.

               head                                                       tail

                 ↓                                                          ↓

NULL <-  dummy  ->  <-  data1 ->  <-  data2  ->  <-  dummy ->  NULL

'양방향 연결 리스트(doubly linked list)' 또는 '이중 연결 리스트' 라고도 불리는 이 자료구조는 그 이름이 의미하듯이 노드가 양쪽 방향으로 연결된 구조의 리스트이다.

즉, 왼쪽 노드가 오른쪽 노드를 가리킴과 동시에 오른쪽 노드도 왼쪽 노드를 가리키는 구조이다.

ex) data1-> <-data2 -> <-data3

더미 노드 양방향 연걸리스트도 있고, 원형 연결 기반의 양방향 연결 리스트 등등도 있다.

밑에 나오는 예제는 기본적인 양방향 연결 리스트이다.

서로 봐라보는 것이라 복잡하게 느껴진다. 하지만 실제로 코드를 비교해 보면 상대적으로 더 복잡하지 않음을 알 수 있다. 

양쪽 방향으로 이동할 수 있기 때문에 단방향 연결 리스트에서는 어렵게 구현했던 것이 쉽게 구현되기도 한다. 때문에 오히려 단순하게 느껴지는 측면도 있다.

내 나름대로 원형 연결리스트에 더미노드를 추가해서 바꿔보았다.

바뀐 부분은 붉은색 네모로 표시를 해두었다. 나머지 main함수나 기타등등은 모두 똑같다.