스택(Stack)

스택(Stack)이란?

• 아이템 추가/삭제 연산이 항상 한 쪽 끝(top)에서만 나타나는 자료 구조이다.
• LIFO (Last-In-First-Out) : 나중에 들어간 것이 먼저 나온다.

• 스택의 구현체는 주로 Single Linked List.
  • Array List를 쓴다면 pop(), push() 할 때 시간복잡도가 Ө(n)
  • Linked List를 쓴다면 pop(), push() 할 때 시간복잡도가 Ө(1)

응용 예

• 그래프의 깊이 우선 탐색(DFS)에서 사용

• 재귀적(Recursion) 함수를 호출 할 때 사용

• 인터럽트처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임

• 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함

• 함수의 콜스택

• 10진수를 2진수로 바꿀 때

• 코드에서 괄호 쌍이 맞는지 확인할 때

• 연산자 후위표기법