[ 알고리즘 ] 스택(Stack)의 개념과 용도

스택(Stack)의 개념과 용도

 

■ 스택의 용도

 

모바일 게임 중에 한창 유명했던 어플리케이션 STACK이 있습니다.

떨어지는 블럭을 잘 쌓아야 하는 게임인데 최근에는 4D로도 나온것 같더라고요. 

이처럼 스택(Stack)은 영어 단어로 쌓여있는 더미라는 뜻입니다. 

 

 

배열과 달리 스택은 삽입과 삭제에 대한 규칙이 있습니다. 

삽입할 때 1, 2, 3, 4 순이었다면, 

삭제는 4, 3, 2, 1 순으로 해야 합니다. 

중간에 있는 요소를 제거하는 것은 원칙상 불가능합니다. 

즉, 중간 자료의 임의 접근이 안됩니다. 

 

이런 제약이 있는 스택, 주로 어느 용도로 사용될까요?

 

---

 

■ 스택의 용도

 

1.  자료의 순서를 뒤집는데 유용합니다.

 

 

스택의 요소를 하나씩 뽑아서 배열에 저장합니다. 그럼 배열의 요소가 뒤집어집니다. 

이런 식으로 데이터의 순서를 뒤집는데 스택이 많이 활용되고 있습니다. 

 

 

 

2. 재귀 함수를 제거하는데 유용합니다. 

재귀 함수는 자기 자신을 계속 부릅니다.

 

재귀 함수란? 글 보러가기

 

그렇게 부를 때마다 스택 메모리를 잡죠. 

함수안에 가지고 있는 변수를 스택 메모리에 안에 저장합니다. 그렇게 스택의 중간 변수값을 계속 올리고 있는 것입니다. 

 

따라서 재귀 함수를 재귀를 빼고 반복문으로 작성할 수 있습니다.

스택의 중간 값을 저장하는 과정을 스택 자료 구조로 사용할 수 있습니다. 

스택 자료구조 + 반복문 -> 재귀로 만듬.

 

 

 

 

 

 

3. 컴퓨터 연산 순서에 맞게 자료 재정리합니다.

대표적인 예로 후위(postfix) 표기법으로 적힌 식을 쉽게 계산할 수 있습니다. 

 

2*(4+5)-15/3	(중의 표기법)
2 4 5 + * 15 3 / -	(후위 표기법)

 

중의(infix) 표기법은 사람들에게 익숙하지만 컴퓨터 입장는 한글자씩 순서대로 읽어야 하기 때문에 평가가 불가능합니다.  

그래서 후위(postfix) 표기법 변환한 다음 스택을 이용해서 간단하게 계산합니다. 

 

 

계산 로직은 이러합니다. 

1. 한 글자를 읽는다

2. 글자를 읽는데 성공하면 

   2_1. 피연산자이면 스택에 넣는다

   2_2 연산자이면, 스택에 들어있는 피연산자를 꺼내 연산자로 계산하고 다시 그 결과를 스택에 넣는다. 

   2_3 1번으로 돌아간다.

3 글자를 읽는데 실패하면

스택에 남은 결과를 꺼내고 계산을 종료한다. 

 

---

 

1. 한글자를 읽습니다. 

2. 피연산자(2)라서 스택에 넣습니다. 

3. 다음 한 글자를 읽습니다. 

4. 피연산자(4)라서 스택에 넣습니다. 

5. 다음 한 글자를 읽습니다.

6. 피연산자(5)라서 스택에 넣습니다. 

 

 

 

 

 

7. 다음 한 글자를 읽습니다.

8. 연산자(+)라서 스택에서 피연산자를 꺼내 계산하여 그 값을 스택에 넣습니다. 

9. 다음 한 글자를 읽습니다.

....

위 과정을 반복하면 됩니다. 

 

 

 

------------------------------

알고리즘 개념 모아보기 

------------------------------