스택(Stack)

• 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out)형식의 자료구조

스택(Stack)의 연산 - 추상자료형(ADT)

스택(Stack)은 LIFO(Last In First Out)를 따른다. 즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.

• pop() : 스택에서 가장 위에있는 항목을 제거 후 반환한다.
• push(item) : item하나를 스택의 가장 윗 부분에 추가한다.
• peek() or top() : 스택의 가장 위에 있는 항목을 반환한다.
• isEmpty() : 스택이 비어있을 때에 true를 반환한다.
• isFull() : 스택이 가득 차있을 경우 true를 반환한다.
• getSize() : 스택에 있는 요소의 수를 반환한다.

스택의 특징

1. 데이터를 쌓아올린 선형구조이다.
2. 스택은 완전히 꽉 찼을 때 Overflow상태라고 하며 완전히 비어 있으면 Underflow상태라고 한다.
3. 삽입과 제거는 모두 Top이라는 스택의 한쪽 끝에서만 일어난다.

스택사용 사례

1. 재귀알고리즘
   • 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
   • 재귀함수를 빠져 나와 퇴각검색(backtrack)을 할 때는 스태에 넣어 두었던 임시 데이터를 빼줘야 한다.
   • 스택은 이런 일련의 행위를 직관적으로 가능하게 해준다.
   • 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
2. 웹 브라우저 방문기록(뒤로가기)
3. 실행 취소(undo)
4. 역순 문자열 만들기
5. 수식의 괄호검사(연산자 우선순위 표현을 위한 괄호검사)
   • ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
6. 후위 표기법 계산