데이터구조 | 스택 (Stack)

스택(Stack)의 개념

  • 스택(stack)은 쌓아놓은 더미를 말한다.
  • 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 후입선출(LIFO:Last In First Out) 형식의 자료 구조이다.
    • 가장 최근에 들어온 데이터가 가장 먼저 나간다.

스택의 구조

  • 스택 상단: top
  • 스택 하단: 불필요
  • 요소, 항목
  • 삽입/삭제 연산

Stack

스택(Stack)의 연산

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

  • push(x): 주어진 요소 x를 스택의 맨 위에 추가한다.
  • pop(): 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하고 반환한다.
  • isEmpty(): 스택이 비어있으면 참(true)을 아니면 거짓(false)을 반환한다.
  • peek(): 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하지 않고 반환한다.
  • isFull(): 스택이 가득 차 있으면 참(true)을 아니면 거짓(false)을 반환한다.
  • size(): 스택내의 모든 요소들의 개수를 반환한다.
  • display(): 스택내의 모든 요소들의 출력한다.

스택(Stack)의 용도

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

스택(Stack)의 사용 사례

참조