정리 불가능의 영역

3. Stack / Queue

2010. 6. 7. 21:28

- Search를 고려하지 않음

- Insert와 Delete 대신에 Push와 Pop을 씀.

- 값에 의존하지 않고 순서에만 의존.

*Stack : Last-in First-out 방식(LIFO)

*Queue : First-in First-out 방식(FIFO)

-Queue에서는 full 과 Empty 일 때 top,bottom포인터의 상대위치가 같기 때문에 구별해주어야 한다.

*미로찾기

-길을 찾다가 막혀있으면 왔던 길을 되돌아 간다. 왔던 길의 좌표를 Stack에 저장해 놓을 수 있다.

*수식의 계산

-infix(중위표기법) : 연산자를 연산하려는 두 숫자 사이에 두는 방법. 예) 3 + 5

-postfix(후위표기법) : 연산자를 연산하려는 두 숫자 뒤에 두는 방법. 예) 35+

-prefix(전위표기법) : 연산자를 연산하려는 두 숫자 앞에 두는 방법. 예) +35

이 중에서 인간이 이해하기 쉬운 표현은 infix, 프로그램 입장에서 이해하기 쉬운 표현은 postfix.

*infix를 postfix로 변환하는 알고리즘

1. 피연산자인 경우 출력

2. 연산자인 경우 Stack top의 연산자와 우선순위를 비교하여 입력된 연산자의 우선순위가 더 높을 경우 Push하고, Stack top의 연산자의 우선순위가 더 높을 경우 Pop한 후 반복 비교.

*postfix로 된 수식을 계산하는 알고리즘

1. 피연산자이면 Stack에 Push

2. 연산자이면 Stack에서 피연산자 2개를 Pop해서 계산 한 후, 결과는 Push

-최하위 우선순위를 가지는 연산자를 하나 지정해서 Stack에 미리 넣어두면, 코드가 단순해진다.