최종 수정 : 24.12.28
스택(Stack)
1. 스택의 정의
스택은 "쌓아 올린다"는 뜻을 갖고 있다. 선형의 구조를 가지며, 한쪽 끝이 막혀 있고, 다른 한쪽으로만 삽입(입력)과 삭제(출력)가 가능한 구조이다. 후입선출구조(Last-In First-Out[LIFO])라 한다.
스택에서 사용하는 연산은 삽입(PUSH), 삭제(POP)이 있다. 현재 원소(스택의 최상위 원소)가 들어있는 위치를 지시하는 top이라는 포인터가 있고, 스택의 바닥을 지시하는 포인터로 bottom이 있으며, top을 통해서 데이터를 삽입/삭제할 수 있다.
- PUSH 연산 : 스택에 원소를 입력하는 연산, top이 증가한다.
- POP 연산 : 스택의 top에 있는 원소를 출력하는 연산, top이 감소한다.
스택은 입력의 순서와 출력의 순서가 반대가 되는 간단한 구조를 가지고 있지만, 프로그래밍이나 시스템을 간리하기 위해 많은 부분에서 유용하게 사용되고, 아래와 같은 경우 연산이 제한된다.
- 오버플로(overflow) : 스택의 크기보다 많은 자료가 입력되고 삽입할 수 없는 상태
- 언더플로(underflow) : 스택이 비어있으므로 삭제를 할 수 없는 상태
2. 스택의 적용 분야들
스택은 프로그래밍이나 시스템을 관리하기 위해 유용하게 사용된다.
1) 프로그래밍
- 재귀적 호출이나 함수의 호출에 대한 복귀주소 저장
- 수식의 후위표기(postfix) 방식 표기
- 웹사이트의 역순 변경
- 수식의 괄호검사
- 가장 나중에 실행된 것부터 실해을 취소하는 실행 취소(undo) 작업
2) 시스템
- 인터럽트에 대한 복귀주소 저장
- 주기억 장치에서 시스템 호출을 위한 스택 영역으로 지역변수의 저장
- 함수의 매개변수 호출을 위한 시스템 스택
- 0 - 주소지정방식 명령어의 자료 저장소
- 컴파일러를 이용한 프로그래밍 언어 번역
참고
독학사 교재
댓글