CS/자료구조
[자료구조]2. 스택
kimyunseok
2021. 7. 19. 18:54
STACK ADT, 스택 추상자료형
- 스택 추상자료형은 필요한 타입에 맞는 정보를 저장한다.
- 삽입과 삭제가 후입선출 구조로 이루어진다.
- 스택의 주요 기능은 다음과 같다.
- push(object) : element를 삽입한다.
- pop() : 마지막으로 push된 element를 꺼낸다(return하고 삭제한다).
- 스택의 추가적인 기능은 다음과 같다.
- top() : 마지막으로 push된 element를 보여준다.
- size() : 저장된 elements의 수를 알려준다.
- empty() : 스택이 비어있는지 확인한다.
- 예외 처리에서는 pop()과 top() 메서드를 사용할 때 Stack Empty 예외처리를 사용한다.
- Stack을 사용한 프로그램 예시에는 다음이 있다.
- 웹 브라우저 방문 기록
- 텍스트 편집기 되돌리기
- C++ run-time 함수
가 있다.
C++ 런-타임 스택
- 함수가 호출되면 시스템은, 지역변수와 리턴값을 포함하고 프로그램 카운터를 포함하는 프레임을 스택에 푸시한다.
- 함수가 끝나면 프레임은 스택에서 pop되고 스택의 맨 위에 있는 프레임이 실행된다.
- 재귀함수도 마찬가지이다.
배열 기반 스택
- 배열을 사용하는 것이 스택을 구현하는 가장 간단한 방법이다.
- 맨 오른쪽 부분을 top이라고 생각하면 된다.
- 배열을 사용하다 보면 배열이 가득찰 수 있는데, 이 때 StackFull 예외처리를 해줘야 한다.
push() 메서드. 가득찬 경우를 대비해서 StackFull 예외처리를 해준다. - 만일 링크드 리스트로 구현한다면 top을 head로 바꿔서 생각하면 된다. (top이 tail이 아니라 head인 이유는 head에서 삽입하면 이전 head가 뒤로 밀려나기 때문이다.)
성능과 제약
스택에서 n개의 요소가 있을 때,
- O(n)의 공간을 사용하고
- 각각 탐색, 삽입, 삭제는 O(1) 시간이 걸린다.
제약 조건으로는
- 배열로 구현한 스택의 최대 사이즈는 사전에 정의되어야 하고, 이는 바꿀 수 없게된다.
- 이미 가득 찬 스택에 element를 삽입하려 할 경우 예외가 발생한다.
