Stack(C++)(알고리즘)

위 글은 큰돌의 터전 님의 강의자료를 참조해서 정리하고 제가 알고리즘을 풀면서 더 추가적으로 사용할 만한 내용들을 정리한 글입니다.

알고리즘 풀이 강의로 큰돌의 터전님의 강의 강력 추천드립니다.

강의링크

stack이란

스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질인 후입선출(LIFO, Last In First Out)을 가진 자료 구조입니다. 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰입니다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸립니다. 탐색에 O(n)이 걸리는 이유는 n번째 요소를 찾는다고 가정하면 계속해서 앞에 있는 요소를 끄집어내는 과정을 n 번 반복해야 찾을 수 있기 때문입니다.

예시 코드

#include<bits/stdc++.h> 
using namespace std; 
stack<string> stk; 
int main()
{ 	
	ios_base::sync_with_stdio(false); 	
    cin.tie(NULL); 	stk.push("엄"); 	
    stk.push("준"); 	stk.push("식"); 	
    stk.push("화"); 	stk.push("이"); 	
    stk.push("팅"); 	
    while(stk.size())
    { 		
    	cout << stk.top() << "\n"; 		
        stk.pop(); 	
    } 
} 
/* 
팅 
이 
화 
식 
준 
엄 */

키워드

스택은 주로 문자열 폭발, 아름다운 괄호만들기, 짝찾기 키워드를 기반으로 이루어진 문제에서 쓰일 수 있습니다. 또한, “교차하지 않고” 라는 문장이 나오면 스택을 사용해야 하는 것은 아닐까? 염두해야 합니다.

메소드

push(value) : 해당 value를 스택에 추가합니다.

pop() : 가장 마지막에 추가한 요소를 지웁니다. (가장 위에 있는 요소를 지운다고도 합니다.)

top() :가장 마지막에 있는 요소를 참조합니다. (가장 위에 있다고도 합니다.)

size() : 스택의 크기입니다.

Uploaded by

N2T