[C++]STL stack

개요

stack 자료구조가 가지는 성질과 stl stack의 사용법을 정리해봤다.

Stack

Stack은 배열이나 연결리스트에서 마지막에 원소를 추가하거나 삭제, 접근할 수 있다는 제약조건이 들어간 자료구조이다.

처음들어간 원소가 제일 늦게 나온다는 의미의 "FILO" 자료구조라고 한다.

Stack의 성질은 다음과 같다.

• 원소 추가 O(1)
• 원소 제거 O(1)
• 상단 원소 확인 O(1)
• 상단이 아닌 나머지 원소들의 확인 변경 원칙적으로 불가능

구현

배열로 간단하게 구현할 수 있다.

필요한 요소는 원소를 삽입할 배열과 index를 저장할 top만 있으면 된다.

int stack[100];
int top = 0;

top은 원소가 삽입될 index를 가리키고 있다.

따라서

• push : stack[top] = data;
• pop : top--;
• top : stack[top-1]

로 쉽게 구현 가능하다.

STL stack

비어있을때 top(), pop()을 하면 런타임 에러

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

int main(){
	stack<int> S;
    
    //원소 삽입
    S.push(10);
    S.push(20);
    S.push(30);
    
    //stack 크기
    cout << S.size() << "\n";
    
    //비었는지 확인
    if(S.empty()) cout << "stack is empty\n";
    
    //원소 제거
    S.pop();
    
    //원소 확인
    cout << S.top() << "\n";
}

 

Reference

https://cplusplus.com/reference/stack/stack/pop/

https://cplusplus.com/reference/stack/stack/pop/