[C++ STL] std::stack (컨테이너 어댑터)

std::stack

std::stack은 LIFO구조를 가지는 Stack 자료구조의 컨테이너. 

 -> LIFO(Last In First Out) : 마지막에 삽입된 것이 가장 먼저 나온다. 

컨테이너 어댑터는 다른 컨테이너 클래스들을 상속받아 특정한 인터페이스를 제공한다.

 -> 다른 컨테이너와 달리 top, front 등의 함수와 pop(삭제) 함수를 함께 사용하여야만 요소에 접근 가능하다.

 -> 위와 같은 특징으로 반복자(Iterator)를 제공하지 않고 범위기반 for문의 사용이 불가능하다.

 

std::stack은 vector, deque, list를 기반으로 내부적으로 구현이 되어있으며 자료구조인 stack의 기능을 제공한다.

 -> 디폴트로 deque기반으로 구현.

저장하는 컨테이너가 디폴트로 deque인 모습.

먼저 std::stack 컨테이너를 사용하기 위해서는 <stack> 헤더 파일을 추가해야 한다.

기본적인 생성 방법

// 기본 생성 방식.
std::stack<int> stack1;
//stack의 기능을 제공하는 컨테이너이기에 미리 생성해둔다는 개념은 x
std::stack<int> stack2(10); // 이렇게 생성은 불가능
//내부 컨테이너 구조를 vector컨테이너로 변경.
std::stack<int,std::vector<int>> stack3; 
//내부 컨테이너 구조를 list컨테이너로 변경
std::stack<int,std::list<int>> stack4; 
//복사 생성자는 지원한다.
std::stack<int> stack5(stack1);  

 

이제 멤버 함수를 보자. 

 -> 이미 stack으로 동작하는 인터페이스를 제공하기에 내부 멤버 함수는 많지 않다.

 

1. push, top 함수

std::stack<int> stack1;
stack1.push(10);
stack1.push(20);
stack1.push(30);
stack1.push(40);
 
std::cout << stack1.top(); // 40

먼저 push함수.

단순히 std::stack 컨테이너를 생성할 때 템플릿 인자로 넘긴 자료형 타입에 맞는 인자를 넣어주면 내부적으로 저장한다.

그다음 top함수. std::stack 컨테이너는 Stack 자료구조. 즉 LIFO의 구조를 가진다. 그렇기에 가장 마지막에 들어간 40을 반환. (제일 마지막 -> 제일 꼭대기(top))

 -> 삽입 시 top은 방금 들어온 데이터의 위치를 가리킨다.

 

출처 -&amp;amp;amp;amp;amp;amp;nbsp;https://iq.opengenus.org/stack-cpp-stl/

위 그림과 같은 구조인 것.

 

2. pop, empty 함수

std::stack<int> stack1;
stack1.push(10);
stack1.push(20);
stack1.push(30);
stack1.push(40);
std::cout << stack1.top() << std::endl; // 40 출력
stack1.pop(); // 가장 마지막의 데이터인 40 제거.
std::cout << stack1.top() << std::endl; // 30 출력
stack1.pop(); // 가장 마지막의 데이터인 30 제거.
std::cout << stack1.top() << std::endl; // 20 출력
stack1.pop(); // 가장 마지막의 데이터인 20 제거.
std::cout << stack1.top() << std::endl; // 10 출력
stack1.pop(); // 가장 마지막의 데이터인 10 제거.
 
if (stack1.empty()) // 비어있다면 true를. 아니라면 false반환
    std::cout << "스택은 빈 상태" << std::endl;

실행 결과는

단순하다. push가 데이터를 삽입하는 것이었다면, pop은 top이 가리키는 원소를 삭제한다.

empty함수는 stack 컨테이너가 저장한 요소의 수가 0이라면 true를 아니라면 false를 리턴한다.

 

3. size 함수

std::stack<int> stack1;
stack1.push(10);
stack1.push(20);
stack1.push(30);
stack1.push(40);
 
std::cout << stack1.size(); // 4를 출력

현재 std::stack에 저장된 요소의 수를 반환한다.

 

 

 

정리.

std::stack은 앞에서 소개한 컨테이너와는 특성이 다르기에 장단점을 논할 수 없다.(해당 컨테이너의)

 -> 컨테이너 어댑터는 자료를 어떻게(메모리가 연속적인지, 비연속적인지, 트리 형태의 비선형적인지.. 등) 저장하는지가 중요한 게 아니라 어떠한 인터페이스를 제공하는지가 주목적.

 -> 가장 대표적인 예로 그래프 알고리즘인 DFS(깊이 우선 탐색)에서 LIFO구조를 사용.

 

참고로 컨테이너 어댑터 함수들은 clear함수를 제공하지 않아, 저장된 모든 요소를 삭제하려면 일일이 pop처리를 해야 한다.