개념 - 스택 stack

선입후출, 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/

(constructor)

Construct stack (public member function )

empty

Test whether container is empty (public member function )

size

Return size (public member function )

top

Access next element (public member function )

push

Insert element (public member function )

emplace 

Construct and insert element (public member function )

pop

Remove top element (public member function )

swap 

Swap contents (public member function )