[알고리즘/C++] 스택

출처 : BaaaaaaaarkingDog | '강좌/실전 알고리즘' 카테고리의 글 목록 (encrypted.gg)

- stack : 먼저 들어간 원소가 가장 나중에 나오는(First In, Last Out - FILO) 자료 구조

Stack Data Structure and Implementation in Python, Java and C/C++ (programiz.com)

- 스택의 성질
  - 원소의 추가 / 제거에 O(1)
  - 제일 상단 원소 확인 시 O(1)
  - 원칙적으로는 제일 상단 외의 데이터 확인이 불가

- 스택의 구현
  - 배열을 이용한 구현

const int MAX = ...;
int data[MAX];
ins pos = 0; // 스택의 빈 공간의 인덱스를 가리킴 = 스택 원소의 수

void push(int x){
	data[pos++] = x;
} // 스택에 데이터 추가

void pop(int x){
	return data[pos--];
} // 스택의 데이터 제거 및 반환

void top(){
	return data[pos - 1];
}//최상단 데이터 반환

  - STL stack

#include <stack>

int main(void){
	stack<int> s;
    s.push(10); // 데이터 추가
    cout << s.size(); // 스택 크기 반환
    if(s.empty()) cout << "s is empty" // 스택의 비었는지 여부
    s.pop(); // 스택 최상단 데이터 제거
  	cout << s.top(); // 스택 최상단 데이터 확인
}