[자료구조] 스택

오늘은 스택에 대해 배웠던 내용들을 정리해보려고 한다.

 

스택이란

대표적인 자료구조 중 하나로 후입선출(LIFO) 방식의 자료구조이다 / Last In First Out

말 그대로 가장 마지막에 넣은 요소가 가장 먼저 나오게 되는 방식이다.

 

스택의 대표적인 연산

push()	스택에 데이터 삽입
pop()	스택에서 데이터 꺼내기
peek()	가장 상단에 있는 데이터 반환
empty()	스택이 비었는지 안 비었는지 반환
size()	스택의 크기를 반환
search(Object o)	파라미터 객체를 찾아서 해당 인덱스(1부터 시작) 를 반환 / 없으면 -1
...	...

Java 에서 기본적으로 제공하는 Stack 메소드들이다.

 

 

후위표기식 과 중위표기식

대표적으로 스택 자료구조를 배우게 되면 활용할 수 있는 주제이다. 

먼저 후위표기식과 중위표기식에 대해 알아보면

 

중위표기식은 우리가 보통 사용하는 1 + 3 + 5 .. 이렇게 연산자가 숫자 사이에 있는 표기식이다

반대로 후위표기식은 숫자 뒤에 연산자가 위치한다. 즉 1 3 5 + + 이런 식으로...

 

그렇다면 후위표기식을 어떻게 계산해볼 수 있을까?

 

1. 숫자를 일단 스택에 Push

2. 연산자가 나오면 스택에서 Pop * 2번 (즉 숫자 2개가 나옴) 후 연산한 결과를 스택에 Push

 

중위표기식을 후위표기식으로 바꾸려면

 

1. 숫자를 읽으면 그대로 출력한다.

2. 스택에 아무 값이 없으면 연산자를 스택에 Push

3. 만약 가장 상단에 있는 연산자의 우선 순위보다 지금 읽은 연산자의 우선순위가 크면 스택에 Push

4. 같거나 아래라면 2,3 번이 될때까지 반복하여 Pop 하여 출력한다.

5, 모든 값을 읽었다면 Pop 해서 스택을 모두 출력해준다.

 

 

 

 

 

 

[참고자료]

[1] https://inpa.tistory.com/entry/JCF-%F0%9F%A7%B1-Stack-%EA%B5%AC%EC%A1%B0-%EC%82%AC%EC%9A%A9%EB%B2%95-%EC%A0%95%EB%A6%AC

[2] https://todaycode.tistory.com/73