[자료구조] 스택(Stack)

스택(Stack)

• 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조
  
  • LIFO(후입선출): 가장 최근에 들어온 데이터가 가장 먼저 나감
• 재귀적인 함수, 알고리즘에 사용
• 웹브라우저 방문 기록 등에 사용
• 삽입 및 삭제에 O(1), 탐색에 O(n)의 시간복잡도를 가짐

스택의 구조

스택의 구조

• 스택 상단(stack top): 스택의 가장 윗부분, 스택에서 입출력이 이루어지는 부분
• 스택 하단(stack bottom): 스택의 가장 아랫부분
• 요소(element): 스택에 저장되는 것
• 공백 스택(empty stack): 비어있는 스택
• 포화 스택(full stack): 포화 상태의 스택

스택의 연산

• pop(): 스택에서 가장 위에 있는 항목 제거
• push(element): 요소를 스택 상단에 추가
• top(): 스택 상단의 요소 반환
• isEmpty(): 스택이 비어있는 경우 true를 반환

스택의 연산 (push, pop)