자료구조 강의 3화 :: 스택

자료구조 3화를 듣고 배운내용

 

KEYWORDS

스택: 객체와 저장된 순서를 기억하는 방벙에 관한 추상 자료형

늦게 들어온게 먼저 나가는 구조

왔던 길 되돌아가는 경우에 많이 사용됨

처리했던 값들을 역순으로 돌아가며 찾아내서 처리하는 경우 많이 사용

 

중위 표기법(infix notation): 연산자를 피연산자의 사이에 표기하는 방법, 가장 많이 사용되는 표기방법(A + B)

전위 표기법(prefix notation): 연산자를 핀연산자의 앞에 표기하는 방법(+AB)

후위 표기법(postfix notation): 연산자를 피연산자 뒤에 표기하는 방법(AB+)

 

 

스택

0개 이상의 원소를 갖는 유한 순서 리스트

push(add)와 pop(delete)이 한 곳에서 발생

 

스택의 추상 자료형

create, push, pop만 접근할 수 있도록 제한을 둔다.

top(제일 위의 값)만 이용해서 접근할 수 있다.

 

*추상 자료형: 할 수 있는 것을 제한해 두는 내용

 

 

스택 수식의 계산

연산자의 계산순서를 생각해야 된다.

A + B * C + D

 

중위 표기법 => 후위 표기법

1. 중위 표기식을 연산자의 우선수위를 고려하여 괄호로 묶어준다.
2. 연산자를 오른쪽으로 이동
3. 반복
4. 괄호를 모두 제거

예시)

A + B => AB+

A - ((B + K) / D)) => ABK+D/-