개념 - 스택 stack
2018. 3. 2. 08:51
선입후출, 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 )
'프로그래밍 책 공부 > C++로 풀어쓴 자료구조' 카테고리의 다른 글
개념 - 덱 deque (0) | 2018.03.03 |
---|---|
개념 - 큐 queue (0) | 2018.03.03 |
개념 - 싱글 링크드 리스트 (0) | 2018.02.27 |
개념 - 리스트 (0) | 2018.02.25 |
개념 - 자료구조와 알고리즘의 이해 (0) | 2018.02.24 |