[C++] STL - container - stack(스택)

STL

1. container(컨테이너)

ㄴ개거체들을 저장하는 객체나 클래스

vector(배열),  list(링크드 리스트),   deque(덱),   string(문자열 전용 컨테이너), map , stack(스택)(<-지금 이거) 등

 

2. literator(반복자)

ㄴ컨테이너에 저장된 요소를 순회하고 접근하는 객체나 클래스

 

3. 알고리즘(algorithm)

ㄴ데이터를 다루기 위한 함수

find, sort, search 등

 

4. 함수 객체(function object), 함수자(functor)

ㄴ함수처럼 동작하는 객체로, operator() 연산자를 중첩한 클래스의 객체

 

 

stack

스택은 값들을 저장하되, 입력과 출력이 한 군데로만 가능한 컨테이너 중 하나입니다.

스택의 경우 LIFO(List In First Out)의 법칙을 따릅니다.

제일 마지막에 넣은 값을 꺼낼 수 있다는 것인데요.

즉, 꺼낼 수 있는 값은 그 때 가장 최근에 넣은 값으로 한정됩니다.

스택의 경우는 값을 넣는 것을 특별히 push 연산이라고 합니다.

 

꺼내는 연산은 pop 연산이라고 합니다.

 

stack을 활용하여 https://www.acmicpc.net/problem/10811

10811번: 바구니 뒤집기

이 문제를 풀었다. ( 배열의 i인덱스 부터 j인덱스 까지의 내용들을 역순으로 만드는 것을 여러 번 해야 하는데, 스택에 1 2 3 4 순서대로 쌓고 pop을 하면 4 3 2 1순서로 넣은 순서와 반대 순서로 나오니까, 이를 이용하여 역순을 만들었다. )

 

 

c++의 stack에서는 push, pop연산을 push(), pop() 함수를 통해 하며,

값의 개수를 알려주는 size(), 비어 있는지 확인하는 empty() 함수를 사용 가능하며,

제일 상단의 값을 꺼내지 않고 리턴만 하는 고유의 top() 함수도 사용 가능합니다.

그리고 스택은 이터레이터 사용이 불가능합니다.

이제 말 안 해도 아시겠지만, stack 헤더 파일이 필요합니다.

ㄴ #include <stack>

 

 

 

스택은 중간 부분에서 입출력이 안되게 하기위해서 사용한다

vector와의 차이점, vector는 중간에 접근 가능 push back으로 입력
stack은 중간에서 빼내기 불가(인덱스로 접근 자체가 불가), push로 넣기

 

 

스택의 예시는

인터넷에서 타고타고 들어갈 때,

ex) 구글에서 네이버로 들어가고, 네이버에서 네이버 뉴스에 들어가고, 네이버 뉴스에서 어떤 기사를 클릭하고, 그러면 그게 스택에 다 쌓이면서 가다가, 뒤로가기를 누르면 하나씩 빠져나오는 것이다.

 

 

 

1. stack container사용

 

#include <stack>
using namespade std;

int main(void){
	
    stack <int> Stack01;
    
	return 0;
}

c++에서 STL container stack을 사용하려면, 

#include <stack> 라이브러리와 

namespace std 가 필요하다

 

2. stack container의 자료형

struct point{
	int x;
    int y;
};

int main(void){
	
	stack <point> Stack02;

	return 0;
}

이렇게 int, char말고 구조체도 stack의 자료형으로 사용이 가능하다.

 

 

3. stack의 입출력

.push()   .empty()   .top()   .pop()  .size()

#include <iostream>
#include <stack>
using namespace std;

int main(void){
	
    // int형 stack생성
	stack <int> Stack01;
    
    // .push() 메소드로 stack에 입력
    Stack01.push(0);
    Stack01.push(1);
    Stakc01.push(2);
    
    // .top() 메소드로 stack의 맨 위의 원소 출력 ( 스택이 비었을 경우 오류 ) 
    if (Stack01.empty()==0) // .empty() 메소드로 빈 스택인지 확인
    	cout<<Stack01.top()<<endl;
     
     // .pop() 메소드로 stack의 맨 위의 원소 제거 ( 스택이 비었을 경우 오류 )
     if (Stack01.empty()==0)
     	Stack01.pop();
        
     // .size() 메소드로 stack의 크기(스택에 들어있는 원소의 개수) 알아내기
     cout<<Stack01.size()<<endl;

	return 0;
}

스택이름.push(넣을 값)	스택에 값을 입력한다. 맨 뒤에 순서대로 쌓는다.
스택이름.empty()	스택이 비었는지 확인한다. 스택이 비었다면 0, 뭐가 들어있다면 1을 리턴한다.
스택이름.top()	스택의 맨 뒤의 값을 참조한다.
스택이름.pop()	스택의 맨 뒤의 값을 제거한다. (참조하지 않고 바로 삭제한다.)
스택이름.size()	스택에 들어있는 원소의 수, 즉 스택의 크기를 알아낸다 (따라서 스택이 비어있으면 0을 리턴하고 오류가나지 않는다.)

 

 

4. 문제

https://www.acmicpc.net/problem/10828

10828번: 스택

https://www.acmicpc.net/problem/9012

9012번: 괄호

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

https://www.acmicpc.net/problem/2493

2493번: 탑

탑까지 풀면 왠만한건 다 풀린다.