[자료구조]2. 스택

STACK ADT, 스택 추상자료형

• 스택 추상자료형은 필요한 타입에 맞는 정보를 저장한다.
• 삽입과 삭제가 후입선출 구조로 이루어진다.
• 스택의 주요 기능은 다음과 같다.

1. push(object) : element를 삽입한다.
2. pop() : 마지막으로 push된 element를 꺼낸다(return하고 삭제한다).

• 스택의 추가적인 기능은 다음과 같다.

1. top() : 마지막으로 push된 element를 보여준다.
2. size() : 저장된 elements의 수를 알려준다.
3. empty() : 스택이 비어있는지 확인한다.

• 예외 처리에서는 pop()과 top() 메서드를 사용할 때 Stack Empty 예외처리를 사용한다.
• Stack을 사용한 프로그램 예시에는 다음이 있다.

1. 웹 브라우저 방문 기록
2. 텍스트 편집기 되돌리기
3. C++ run-time 함수

가 있다.

C++에서의 스택 인터페이스

C++ 런-타임 스택

 

C++에서의 런타임 스택

• 함수가 호출되면 시스템은, 지역변수와 리턴값을 포함하고 프로그램 카운터를 포함하는 프레임을 스택에 푸시한다.
• 함수가 끝나면 프레임은 스택에서 pop되고 스택의 맨 위에 있는 프레임이 실행된다.
• 재귀함수도 마찬가지이다.

 

배열 기반 스택

• 배열을 사용하는 것이 스택을 구현하는 가장 간단한 방법이다.
• 맨 오른쪽 부분을 top이라고 생각하면 된다.

배열로 스택을 만든 경우

size()와 pop() 메서드. pop()메서드에서는 비었을 때를 대비해서 StackEmpty 예외처리를 한다.

• 배열을 사용하다 보면 배열이 가득찰 수 있는데, 이 때 StackFull 예외처리를 해줘야 한다.

  

  push() 메서드. 가득찬 경우를 대비해서 StackFull 예외처리를 해준다.

• 만일 링크드 리스트로 구현한다면 top을 head로 바꿔서 생각하면 된다. (top이 tail이 아니라 head인 이유는 head에서 삽입하면 이전 head가 뒤로 밀려나기 때문이다.)

 

성능과 제약

스택에서 n개의 요소가 있을 때,

1. O(n)의 공간을 사용하고
2. 각각 탐색, 삽입, 삭제는 O(1) 시간이 걸린다.

 

제약 조건으로는

1. 배열로 구현한 스택의 최대 사이즈는 사전에 정의되어야 하고, 이는 바꿀 수 없게된다.
2. 이미 가득 찬 스택에 element를 삽입하려 할 경우 예외가 발생한다.

 

스택 자료구조의 예시. 출처-위키피디아 : https://en.wikipedia.org/wiki/Stack_(abstract_data_type)