[Stacks]10. Stack ADT(스택)

목차

1. Abstract Data Types(ADTs, 추상 자료형)

2. Stack ADT(스택)

3. Applications of Stack(활용하는 곳)

4. Performance and Limitations

 

1. Abstract Data Types(ADTs, 추상 자료형)

 Abstract Data Types(ADTs, 추상 자료형)은 특정 자료구조에 명세된 내용을 의미합니다. 즉, 각각의 ADT는

1. 해당 ADT가 어떤 자료를 지니고 있는지

2. 해당 ADT가 어떤 기능을 취할 수 있는지(탐색, 삽입, 삭제 등...)

 이 두가지 해당사항(가이드라인)을 제시해 주는 것을 말합니다.

 

2. Stack ADT(스택)

 위에서 언급한 ADT의 한 종류인 Stack ADT(스택)은 여러 특징들을 가집니다.

 

1) 특징

- 임의의 데이터를 저장한다.

- L I F O(Last in First Out, 마지막으로 in된 것이 먼저 out한다)

- 마치 접시를 쌓아서 쓰거나, 엘레베이터에 타고 내리는 순서와 같다.

 

2) 주요 기능

- push(object): element를 insert한다.

- object pop(): 가장 마지막으로 들어온 element를 remove한다

 

3) 부가 기능

- object top(): 마지막으로 들어온 element를 반환, 별도로 삭제하지는 않는다.

- integer size(): 해당 스택의 크기를 반환한다.

- boolean empty(): 해당 스택이 비었는지 그 여부를 반환한다.

 

3. Applications of Stacks(활용하는 곳)

- 웹에서의 검색 기록 저장

- 문서 작업시, ctrl+z 기능

- c++에서 함수 호출을 할 시

 

4. Performance and Limitations

1) Performance

- n개의 데이터가 Stack ADT에 있다고 가정하면,

- 사용되는 공간은 O(n)

- 각각의 기능은 O(1)의 시간이 소모된다.

 

2) Limitations

- array로 구현 시, 최대 사이즈를 미리 지정하므로, 이를 다시 바꿀 수 없다.

- full stack array에 추가로 삽입하려고 하면, 오류가 발생할 수 있다.