시험 직전 요약장

스택·큐·데크에서 특정 값을 찾는 작업은 일반적으로 O(n)이다. 끝 연산이 O(1)이라는 사실과 임의 검색도 O(1)이라는 주장은 다르다.

후위식은 왼쪽에서 오른쪽으로 읽으며 피연산자를 스택에 넣는다. 이항 연산자를 만나면 두 값을 꺼내 계산 결과를 다시 넣는다.

1. right = pop() — 오른쪽 피연산자
2. left = pop() — 왼쪽 피연산자
3. push(left 연산자 right)

뺄셈과 나눗셈은 피연산자 순서를 바꾸면 결과가 달라지므로 특히 주의한다.

후위식 8 2 3 * +의 계산 과정은 다음과 같다.

입력을 모두 처리했을 때 스택에 값이 정확히 하나 남아야 정상적인 식이다. 위 식의 결과는 14다. 예를 들어 8 2 /에서 먼저 꺼낸 2가 오른쪽 피연산자이므로 계산은 8 / 2다.

후위식은 이항 연산 직전에 스택 값이 두 개 이상 필요하다. 입력 종료 때 값 하나가 남는 조건만 검사하지 말고 각 연산의 피연산자 부족도 검사한다.