[자료구조] 스택(Stack)이란? 🦖

 

스택(Stack)은 말 그대로 '쌓아놓은 더미'를 뜻합니다. 식당에 쌓여있는 접시 더미, 책상에 쌓인 책, 겹겹이 쌓인 상자 모두 스택의 예에 해당합니다. 

 

스택(Stack) 자료구조를 쉽게 예를 들어보자면, 박스 쌓기를 생각하면 됩니다. 박스를 아래에서 하나씩 쌓고, 그 박스를 뺄 때는 마지막에 쌓은 박스부터 빼야 한다는 점을 생각하면 쉽습니다.

 

후입선출(LIFO: Last-In First-Out)

스택의 가장 큰 특징은 후입선출(LIFO)입니다. 가장 최근에 들어온 데이터가 가장 먼저 나간다는 의미입니다.

스택의 입출력은 맨 위에서만 이루어지기 때문에 스택의 중간에 데이터를 삽입하거나 삭제하는것은 불가합니다.

프링글스를 생각하면 쉽습니다. 과자를 만들때 가장 나중에 넣은 과자를 제일 먼저 먹고, 가장 먼저 넣은 과자를 마지막에 먹게 되는 것과 같은 의미입니다.

 

 

스택을 언제 사용 ?

스택은 자료의 출력 순서가 입력 순서의 역순으로 이루어질 때 사용되는 자료구조입니다.

 

문서 편집기에서 '되돌리기(undo)' 기능을 사용하면 바로 직접에 실행했던 작업이 취소됩니다. 그때 바로 이 스택 자료구조를 사용합니다.

내가 했던 작업을 스택에 쌓아놓고 가장 최근 기능을 삭제하는 연산을 실행시키면 '되돌리기'와 같은 기능이 실행됩니다.

• 상단(stack top) : 스택에서 입출력이 이루어지는 부분
• 하단(stack bottom) : 반대쪽 바닥 부분
• 요소(element) : 스택에 저장되는 것
• 공백 스택(empty stack) : 공백 상태의 스택
• 포화 상태(full stack) : 포화 상태의 스택 (풀스택)

스택 추상자료형

1. 스택 ADT (추상데이터타입)

객체 : n개의 요소들의 선형리스트

2. 스택의 연산

: 스택에 요소를 추가/삭제하는 연산과, 현재 스택 상태를 검사하는 연산들로 구성됩니다.

스택의 사용 사례

• 웹 브라우저 방문기록
• 실행 취소 (undo)
• 역순 문자열 만들기

오늘은 자료구조 Stack에 대해 정리해봤습니다. 다음 포스팅에서는 자료구조 Queue에 대해 알아보겠습니다. 감사합니다 🫠