[자료 구조 #4] 스택(stack)

기회는 준비된 자에게 온다 !

스택의 정의

스택(stack)이란 무엇일까?

단어 뜻에서 느껴지듯 무엇인가를 차곡차곡 쌓는다는 느낌이다.

따라서 차곡차곡 쌓으면 제일 아래 쪽에 위치한 녀석은 제일 마지막에 나온다.

쉽게 생각해서 프링글스 통이라고 생각하자.

제일 늦게 넣은 과자가 제일 빨리 튀어나오는 구조인 LIFO(Last In First Out)구조를 띠고 있다.

정확하게 이전 포스트인 큐(queue)와 반대 동작을 한다.

스택의 연산

앞선 모든 자료 구조에서는 4가지 동작 (읽기, 검색, 삽입, 삭제)의 기본 연산을 지원한다.

스택에서 많이 사용되는 메소드는 다음과 같다.

큐와 비슷하지만 세 번째 불릿만 다르다.

• push() : 스택에 원소를 삽입, 이 때 크기가 1 증가
• pop() : 스택에서 가장 상단에 위치한 원소를 뺀다. 이 때 크기가 1 감소
• top() : 스택에서 제일 꼭대기에 저장된 원소를 반환한다. pop()은 원소 반환을 하지 않음
• empty() : 스택이 비었는 지 검사하여 bool 값을 반환
• size() : 현재 스택에 저장된 데이터의 개수를 반환

스택 사용법 (C++)

기본적인 선언은 아래와 같이 한다.

큐와 똑같이 해주면 된다.

#include <stack>

std::stack<int> num_stack;

이렇게 되면 큐에 [3 6 9] 순서대로 쌓인다.

num_stack.push(3);
num_stack.push(6);
num_stack.push(9);

따라서 스택에 제일 늦게 들어간 순서대로 반환이 되는데,

auto num = num_stack.front();
num_stack.pop();
std::cout << "num: " << num << std::endl;

스택에서 단지 제일 꼭대기에에 저장된 데이터가 보고 싶을 때는 top()를 사용하지만, 그 데이터를 프링글스 통에서 없애고 싶을 때는 pop() 해주는 것을 잊지 말자.

스택도 clear() 기능이 없다.

그래서 일일히 없애줘야 한다.

스택 clear() 구현

간단하다. 비어 있지 않으면? pop()을 계속 하자!

while (!num_stack.empty()) num_stack.pop();

스택의 사용 사례

배열(array)와 비슷한 느낌이긴 한데, 어떤 문제를 푸냐에 따라 배열보다 스택이 효율적일 수 있다.

왜냐하면,

• 배열과 달리 스택은 중간에 저장된 데이터에 바로 접근할 수 없다.
• 배열처럼 삽입 operation 시 원소들을 하나씩 옆으로 밀어 줄 필요가 없다.

재귀 알고리즘(recursive algorithm) 사용 시 스택이 유용하다.

다음은 스택의 사용 예시들이다.

• 웹 브라우저 방문기록 혹은 뒤로가기
• 실행 취소
• 재귀 알고리즘
  • 재귀적으로 함수를 호출해야 하는 경우 임시 데이터를 스택에 넣어줌
  • 재귀 함수를 빠져 나와 퇴각 검색(backtracking)을 할 때는 스택에 넣어둔 임시 데이터를 빼줘야함
  • 스택은 이런 행위를 직관적으로 가능하게 해줌

Reference

• [자료구조] 스택(stack)이란