[CS][Data Structure] 스택 (Stack)

Stack이란?

스택은 데이터를 저장하고 가져오는 작업이 LIFO(Last In First Out) 순서로 이루어지는 자료구조입니다.

이렇게 데이터가 들어오고 나가는 입구가 일정한 위치에서만 이뤄지기 때문에 한쪽 끝에서만 삽입과 삭제가 된다는 점이 스택의 주요 특징입니다.

Stack의 기본 연산

1. push(n) : 스택의 제일 위에 데이터를 추가하는 연산입니다.

2. pop() : 스택의 제일 위의 데이터를 제거하고 반환하는 연산입니다.

3. peek() : 스택의 제일 위의 데이터를 반환하는 연산입니다.

4. isEmpty() : 스택이 비어있는지 확인하는 연산입니다.

Stack의 장점

간단한 구현

스택은 배열이나 연결 리스트를 사용하여 쉽게 구현할 수 있습니다.

빠른 속도

스택에서 데이터를 삽입하거나 삭제할 때 제일 위에 있는 요소만 다루기 때문에 O(1)의 시간 복잡도를 가집니다. 
peek() 또한 데이터 조회는 한쪽에서만 일어나기 때문에 O(1)의 시간복잡도를 가지지만 전체 탐색 시에는 각 원소를 한 번씩 처리해야 하기 때문에 O(n)의 시간복잡도를 가집니다.

Stack의 단점

크기 제한

스택의 크기가 고정되어 있을 경우, 스택이 가득찬 상태에서 삽입을 실행하면 오버플로우가 발생할 수 있습니다.

Stack의 활용

재귀 알고리즘 : 스택을 사용하여 상태를 저장하고 복원합니다.

문자열 연산 : 괄호 짝 맞추기, 후위 표기법 계산 등에서 스택이 사용됩니다.

함수 호출 관리 : OS가 함수 호출을 관리하기 위해 스택을 사용합니다. 이를 통해 반환 주소 및 로컬 변수를 저장하고 복원할 수 있습니다.

컴파일러 및 인터프리터 : 스택을 통해 프로그램의 실행 콘텍스트를 관리합니다.