선입후출, FILO 자료구조다. 

개념상으로 쉽고 구현도 간편하다. 어디에 쓰일까?

책에서 나온 용도는 다음과 같다. 


1. 프로그램의 Ctrl + z (undo) 

2. 스택메모리

코드를 읽어가다가 새 함수호출을 만나면 스택에 활성 레코드(스택 프레임)와 복귀주소인 프로그램 카운터값이 저장되어 푸쉬된다. (이 때의 인덱스 정보를 스택 포인터라고 한다)이를 통해 함수 호출이 끝나면 원래자리로 되돌아올 수 있다.

3. 소스코드나 문장에서 괄호 닫기가 정상적인지 검사하는 프로그램

4. 계산기 프로그램에서 연산순서를 중위에서 후위로 변환할 때

5. 미로에서의 출구 찾기에서 갈 수 있는 경로를 스택 위에서부터 하나씩 가보는 것


스택, 큐, 덱은 배열로 만들 수도 있고 연결리스트로 만들 수도 있다.


스택의 ADT

push(x)

pop()

isEmpty()

peek()

isFull()

size()

display()

출처 : C++로 쉽게 풀어쓴 자료구조


코드:

 배열기반 스택 구현

스택으로 후위 계산

스택으로 중위 계산


STL에서의 stack

std::stack는 컨테이너를 위한 어댑터(인터페이스) 역할을 한다. 벡터나 리스트도 queue 형식으로 사용할 수 있다는 뜻이다. 기본적으로는 std::deque를 컨테이너 클래스로 사용한다.


http://www.cplusplus.com/reference/stack/stack/



'프로그래밍 책 공부 > C++로 풀어쓴 자료구조' 카테고리의 다른 글

개념 - 덱 deque  (0) 2018.03.03
개념 - 큐 queue  (0) 2018.03.03
개념 - 싱글 링크드 리스트  (0) 2018.02.27
개념 - 리스트  (0) 2018.02.25
개념 - 자료구조와 알고리즘의 이해  (0) 2018.02.24