스택

후입선출(LIFO, Last In First Out) 구조이다.

스택은 한 쪽 끝에서만 자료를 삽입 / 제거 가능한 구조이다.

• 맨 위에 자료를 삽입하는 연산을 push 라고 부르고,
• 맨 위의 자료를 삭제하는 연산을 pop 이라고 부른다.

C++ STL

#include <stack>
stack<int> s;

기본 함수로는
push pop top size empty 가 있다.

push: 데이터를 스택에 삽입한다.

s.push(x);

pop: 가장 최근에 삽입된 데이터를 스택에서 제거한다.

s.pop();

top: 가장 최근에 삽입된 데이터를 반환한다.

data = s.top();

size: 스택의 크기를 반환한다.

int sz = s.size();

empty: 스택이 비어있으면 1, 아니면 0을 반환한다.

bool isEmpty = s.empty();

C Code 배열 기반 구현

#define SIZE 10000
#define EMPTY 0x3f3f3f3f

int s[SIZE];
int sz = 0;

void push(int x) {
	if (SIZE <= sz) return;
	s[sz++] = x;
}

void pop(void) {
	if (sz == 0) return;
    sz--;
}

int top(void) {
	if (sz == 0) return EMPTY;
	return s[sz - 1];
}

int size(void) {
	return sz;
}

int empty(void) {
	return sz == 0;
}

추천 문제

백준 9012번: 괄호
백준 1918번: 후위 표기식
백준 2800번: 괄호 제거