[자료구조] 스택 (Stack)
스택은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조로 되어 있습니다.
식당에 쌓여있는 접시들이 좋은 예입니다. 순서대로 쌓인 접시가 스택 구조와 같습니다.
접시가 필요하면 제일 위에 있는 접시부터 사용하며 가장 아래 있는 접시는 마지막에 사용됩니다.
스택은 LIFO (Last In First Out) / FILO (First In Last Out) 순서를 따릅니다.
- LIFO : 마지막으로 들어온 값이 처음으로 나가는 것
- FILO : 처음 들어온 값이 마지막에 나가는 것
스택은 완전히 꽉 찼을 때 Overflow 상태라고 하며 완전히 비어 있으면 Underflow 상태라고 합니다.
삽입(Push)과 제거(Pop)는 모두 Top이라는 스택의 한쪽 끝에서만 일어납니다.
추상 자료형(ADT)
스택은 아래 연산들로 추상화할 수 있습니다.
- push - 스택 맨위에 항목을 삽입
- pop - 스택 맨위에 항목 삭제
- peek or top - 스택의 맨 위(top)를 표시
- isEmpty - 스택이 비어있는지 확인
- isFull - 스택이 가득 차 있는지 확인
- getSize - 스택에 있는 요소 수를 반환
기본 동작
Push 작업
데이터를 스택에 넣는 작업을 push 라고 합니다. push는 다음 단계를 거칩니다.
- 1 단계 - 스택이 가득 찼는 지 확인합니다.
- 2 단계 -스택이 가득 차면 오류가 발생하고 종료됩니다.
- 3 단계 -스택이 가득 차지 않으면 Top을 증가시킵니다.
- 4 단계 - Top이 가리키는 스택 위치에 데이터를 추가합니다.
Pop 작업
데이터를 스택에 제거하는 작업을 pop이라고 합니다. pop은 다음 단계를 거칩니다.
- 1 단계 -스택이 비어 있는지 확인합니다.
- 2 단계 -스택이 비어 있으면 오류가 발생하고 종료됩니다.
- 3 단계 -스택이 비어 있지 않으면 Top 이 가리키는 데이터를 제거합니다.
- 4 단계 -Top 값을 감소시킵니다.
- 5 단계 -성공을 반환합니다.
시간 복잡도 (Time complexity)
| Operation | Average | Worst |
| Access | Θ(n) | O(n) |
| Search | Θ(n) | O(n) |
| Insert (push) | Θ(1) | O(1) |
| Delete (pop) | Θ(1) | O(1) |
push(), pop(), isEmpty(), peek() 모두 O(1) 시간이 걸립니다. 이유는 삽입 삭제는 항상 Top에서만 일어나기 때문입니다.
구현
스택을 구현하는 방법에는 두 가지가 있습니다.
- 배열 사용
- 장점 : 구현하기 쉬움.
- 단점: 크기가 동적이 아님. 런타임시 필요에 따라 늘어나거나 줄어들지 않음.
- 연결 리스트 사용
- 장점 : 크기가 동적임. 런타임시 필요에 따라 크기가 확장 및 축소될 수 있음.
- 단점 : 포인터를 위한 추가 메모리 공간이 필요함.
스택(Stack)의 사용 사례
- 재귀 알고리즘을 반복문을 통해서 구현할 수 있게 해줌
- 실행 취소 (undo)
- Backtracking
- 웹 브라우저 뒤로가기
- 구문분석
- 후위(postfix) 표기법 연산
- 문자열의 역순 출력 등
