[C++] Stack with Cpp

 

정의 및 특징

• 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질 - LIFO(후입선출)
• 재귀적인 함수, 알고리즘 및 웹 브라우저 방문 기록 등에 사용
• 주로 문자열 폭발, 괄호만들기, 짝찾기 키워드를 기반으로 이루어진 문제에서 사용 가능
• "교차하지 않고" 라는 문장이 나오면 스택 사용 고려

 

시간 복잡도

• 삽입 및 삭제 -> O(1)
• 탐색 -> O(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();
    }
}
/*
팅
이
화
식
준
엄
*/

 

method

 

• push(value)
  
  • 해당 value를 스택에 추가한다.
• pop()
  • 가장 마지막에 추가한 요소를 지운다 (가장 위에 있는 요소를 지운다고도 함)
• top()
  • 가장 마지막에 있는 요소를 참조 (가장 위에 있다고도 한다.)
• size()
  • 스택의 크기

 

더 많은 내용은 아래 게시물 참조(python으로 작성)

2022.09.09 - [CS/자료구조] - [자료구조] Stack with Python

[자료구조] Stack with Python