[알고리즘&자료구조] 스택 - C++/파이썬

스택이란?

먼저 들어간 원소가 나중에 나오는 자료구조(Last in First out-LIFO)

위의 그림과 같이 1->2->3의 순서로 들어가지만 나올 때는 3->2->1의 순서로 나온다.

스택을 생각할 때 엘레베이터를 생각하면 먼저 들어간 사람이 뒤로 가게 되고 마지막에 들어온 사람이 문과 가장 가까이 서게 된다고 생각하면 된다. 아니면 뚜껑이 위에 하나만 있는 용기도 마지막에 넣은 것들이 가장 먼저 나오게 된다.

*스택은 맨 위의 원소만을 고려하기 때문에 그 외의 다른 원소들은 맨 위로 오기 전까지는 그 값을 알 수 없다.

스택 메소드

스택의 메소드로는 다음과 같은 것들이 있다:

• pop - 스택의 맨 위에 있는(마지막으로 들어온) 원소를 삭제함 
• push - 스택에 새로운 원소를 추가함
• isEmpty - 스택이 비어있는지 반환: 비어있으면 1, 아니면 0
• top - 스택의 맨 위에 있는 원소를 반환
• size - 스택의 크기를 반환

언어마다 차이가 있을 수 있으나 위 메소드들은 거의 필수적으로 있다고 봐도 무방하다.

스택의 언어별 사용 - C++/파이썬

C++

스택 헤더를 통해 사용 - #include <stack>

#include <stack>

int main() {
    std::stack<int> st;
    st.push(1); // 1
    st.push(2); // 1 2
    st.pop(); // 1
    cout << st.top() << endl; // 1 출력
    cout << st.size() << endl; // 1 출력
    cout << st.empty() << endl; // 0 출력
}

파이썬

기본 데이터 타입인 리스트로 사용 가능

st = []
st.append(1) # [1]
st.append(2) # [1, 2]
st.pop() # [1]
print(st[-1]) # 1
print(len(st)) # 1
# empty의 대체방법 #
# 추천
if st: # st = [1] 일때
	print('Not Empty')
if not st: # st = [] 일때
	print('Empty')
# 비추천
if len(st) == 0:
	print('Empty')
if len(st) > 0:
	print('Not Empty')

두 언어의 메소드 차이

*파이썬의 경우 top은 -1 인덱스를 통해, size는 len 함수를 통해 같은 효과를 얻을 수 있다.

**파이썬은 기본적으로 조건문에 바로 넣어 bool을 판별할 수 있어 empty가 존재하지 않는다. 추천 방법이 파이썬과 더 맞는 방법이기에 이를 사용하기를 권장한다.

***C++의 pop은 아무것도 반환하지 않지만 파이썬의 pop은 가장 위의 원소(삭제할 원소)의 값을 반환한다.(top+pop으로 이해)

메소드별 유의 사항

pop, top등의 메소드들은 스택에 원소가 없을 경우 에러가 나기 때문에 empty를 통해 먼저 확인하는 작업이 필요할 수 있다.

*파이썬의 st[-1]도 스택에 원소가 없으면 에러가 난다.

스택 문제 - 백준

스택 - www.acmicpc.net/problem/10828 풀이 - coder38611.tistory.com/118

괄호 - www.acmicpc.net/problem/9012 풀이 - coder38611.tistory.com/121