[ 자료구조 기초] 자료구조의 기초 선형 구조와 수식 계산

 

1.자료구조란?

자료구조(資料構造, 영어: data structure)는 전산학에서 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다.

2. 자료구조 분류 

 

 

자료구조는 크게 선형구조와 비선형구조로 나누어진다. 선형구조란?

국어사전

선형적 

(線形的)

[선형적]

• 선처럼 길게 일렬로 나아가는. 또는 그런 것.

 

말그대로 데이터들이 선처럼 길에 일렬로 나아가는 구조를 선형구조라고 한다. 선형구조에는 배열 연결리스트 스택 큐

등이 포함됩니다. 스택은 일반적으로  수식계산에서 많이사용되며 스택과 큐(스택+큐)가 사용되는 구조를 데큐(Deque)라고 한다.

 

 

선형구조

비선형구조란 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 것을 의미 합니다.

비선형구조

 

 

3. 전위표기법과 후위 표기법

 

 

우리가 일상생활에서 쓰이는 표기법의 경우 중위표기(Infix)를 사용하고있다

 

그렇다면 전위표기(Prefix)와 후위표기(Postfix)란?

 

전위표기란 연산자를 피연산자 앞에 표기하는방법이다

 

후위표기란 연산자를 피연산자 뒤에 표기하는 방법

 

 

중위 표기법(infix notation) : 연산자를 연산 대상의 가운데에 쓰는 표기법(Ex : 5 + 2 / 7) ㄴ> 일상생활에서 쓰이는 표기법 
전위 표기법(prefix notation) : 연산자를 연산 대상의 앞에 쓰는 표기법(Ex : + 5 / 2 7)
후위 표기법(postfix notation) : 연산자를 연산 대상의 뒤에 쓰는 표기법(Ex : 5 2 7 / +)

 

 

1 2 * 3 1 - / 4 5 * +

해당 후위 표기 방식을 중위 표기 방식으로 바꾸면 아래와 같습니다.

(1 * 2) / (3 - 1) + (4 * 5)

따라서 해당 값을 계산하면 21입니다.

 

+ - 5 4 / * 2 3 * 2 1

해당 전위 표기 방식을 중위 표기 방식으로 바꾸면 아래와 같습니다.

(5-4) + ((2*3) / (2*1))

따라서 해당 값을 계산하면 4입니다.