스택 (Stack) 데이터 구조에 대한 설명

Tags:

• Data Structure
• Stack

스택(Stack)의 개념

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

스택의 구조

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

스택(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)이란