스택(Stack)

목차

1. 스택이란
2. 스택의 특징
3. 스택의 연산
   3-1. top
   3-2. pop
   3-3. push
   3-4. empty
4. 스택 사용 예시

1. 스택이란

한쪽 끝에서 삽입과 삭제가 일어나는 자료구조의 일종입니다.

2. 스택의 특징

한쪽 끝에서만 입력과 출력이 이루어지기 때문에

후입선출(LIFO: Last In First Out)의 형태를 가집니다.

위의 경우 A, B, C, D, E를 차례로 입력하고 삭제를 하거나 F를 입력했을 때의 그림이다.

3. 스택의 연산

3-1. top

앞서 설명했듯 스택은 한 쪽 끝에서 입력과 출력이 일어납니다.
top은 그 끝쪽의 자료가 무엇인지 출력하는 역할을 합니다.

위의 경우 E를 출력하게 된다.

3-2. pop

top가 가장 끝쪽의 자료를 출력했다며 pop는 그 자료를 삭제하는 역할을 합니다.
바로 위의 사례에서 pop을 진행한다면 E가 삭제됩니다.

3-3. push

가장 끝쪽의 자료를 추가하는 역할입니다.
push가 진행되면 top나 pop를 진행할 때 대상이 되는 자료가 달라지게 됩니다.
바로 위의 사례에서 push('F')를 진행할 경우 아래와 같은 모습이 됩니다.

3-4. empty

위의 top과 pop를 실행하기 위해 필요한 연산입니다.
배열에 아무런 자료가 없다면 출력도 삭제도 할 수 없습니다.
이러한 상황에서 오류가 발생하는 것을 막기 위해 필요합니다.

4. 스택 사용 예시

1. 웹브라우저의 뒤로가기 버튼
   자신이 방문한 홈페이지를 스택에 쌓아 두었다가
   뒤로가기를 눌러 스택에서 꺼내 그 페이지로 이동할 수 있습니다.

2. 각종 프로그램들의 undo
   실행했던 명령을 순서대로 저장한 다음 바로 직적에 했던 명령을 취소할 수 있습니다.
   간단한 문서작업에서도 붙여넣기를 취소하거나 잘못 삭제된 표를 다시 불러오는 것들을 할 수 있습니다.

3. 수식의 괄호 검사
   가장 간단하게는 '('과 ')'의 갯수 검사부터 시작하여
   소괄호, 중괄호, 대괄호의 갯수 검사 및 중복 검사등을 진행할 수 있습니다.

4. 후위 표기법
   생소한 사람이 있을 수 있어 잠깐 설명하면
   연산자가 피 연산자들 뒤에 위치하는 표기법입니다.

   (A + B) *(C - D) = A B + C D - *

위 식은 저희가 사용하는 표기법을 후위표기법으로 바꾸었을 때의 모습니다.
이러한 과정에서도 스택이 사용됩니다.