[자료구조] - 스택(Stack)

Seong Hyeon Kim·2022년 9월 23일

CS스터디

목록 보기

6/9

1. 스택이란?

스택은 "쌓다" 라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조 입니다.

또한 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 제한적으로 접근할 수 있는 후입선출(Last-In-First-Out) 형태의 선형 자료구조이다.

2. 스택의 사용 및 사례

대표적으로 일상에서 가장 많이 사용하는 사례는 ctrl + Z 로 사용하는 실행취소(되돌리기) 입니다.

그 외에도

재귀함수
- 재귀에 따른 함수 호출을 생각해 보면 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조이므로, 후입선출 구조의 스택을 이용하여 수행 순서를 관리한다.
실행 취소(undo)
- 가장 나중에 실행된 것부터 실행을 취소한다.
웹 브라우저 방문기록(뒤로 가기)
- 가장 나중에 열린 페이지부터 다시 보여준다.
역순 문자열 만들기
- 가장 나중에 입력된 문자부터 출력한다.
수식의 괄호 검사
- 연산자 우선순위 표현을 위한 괄호검사.
괄호의 짝 검사
- 괄호의 짝, 괄호의 순서 검사.

3. 스택의 연산

스택 제공 연산 종류

pop() : 스택에서 가장 위에 있는 항목을 제거한다.
push(item) : item 하나를 스택의 가장 윗 부분에 추가한다.
peek() : 스택의 가장 위에 있는 항목을 반환한다.
isEmpty() : 스택이 비어 있을 때 true를 반환한다.

const arr= [];		/// arr 가 하나의 스택으로 볼수 있음

const push= (data)=>{
  arr.push(data);
};
const pop= ()=>{
  return arr.pop();
}


push(1);
//arr= [1]

push(2);
//arr= [1,2]

pop();
//arr= [1]

스택의 구조

Bottom : 가장 밑에 있는 데이터 또는 인덱스
Top : 가장 위에 있는 데이터 또는 인덱스
Capacity : 스택에 담을 수 있는 데이터의 총 용량
Size : 현재 스택에 담겨져있는 데이터의 개수

4.스택의 시간 복잡도

시간복잡도란?

알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은
‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’라는 말이다.

효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 이야기이다.
그리고 이 시간 복잡도는 주로 빅-오 표기법을 사용해 나타낸다.

시간복잡도 상세 설명

시간복잡도에서 중요하게 보는것은 가장큰 영향을 미치는 n의 단위이다.

빅-오 표기법 간단한 설명

O(1) - 일정한 복잡도(constant complexity) :
입력값이 증가하더라도 시간이 늘어나지 않는다. 문제를 해결하는데 오직 한 단계만 처리함.
O(log n) – 로그 복잡도(logarithmic complexity) :
문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬. O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다. (2진 탐색 생각하면 됨)
O(n) – 선형 복잡도 :
선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
O(n^2) – 2차 복잡도 :
문제를 해결하기 위한 단계의 수는 입력값 n의 제곱 이며 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.
O(2n) - 기하급수적 복잡도 :
Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.
종이를 42번 접으면 그 두께가 지구에서 달까지의 거리보다 커진다는 이야기를 들어보신 적 있으신가? 고작 42번 만에 얇은 종이가 그만한 두께를 가질 수 있는 것은, 매번 접힐 때마다 두께가 2배 로 늘어나기 때문이다.

아래표는 실행시간이 빠른순으로 입력 N값에 따른 서로 다른 알고리즘의 시간복잡도이다

Complexity (입력값)	1	10	100
O(1)	1	1	1
O(log N)	0	2	5
O(N)	1	10	100
O(N log N)	0	20	461
O(N^2)	1	100	10000
O(2^N)	1	1024	1267650600228229401496703205376
O(N!)	1	3628800	화면에 표현할 수 없음!

스택의 시간복잡도

만약 스택이라는 자료 구조를 활용하여 자료를 삽입하고 삭제하고 검색한다면 시간 복잡도는 어떻게 되는지 알아보겠습니다.

사용되는 메소드	시간복잡도
Insertion (삽입 - push)	O(1)
Deletion (삭제 - pop)	O(1)
Search (검색)	O(n)

삽입 - 스택에 자료를 추가하는 것은 스택의 맨 위에 하나를 올리기(push)를 하면 됩니다. 즉, 스택이 무수히 커도, 자료를 삽입하기 위해 한 번의 노력만 하면 됩니다. 이를 생각해보면 시간 복잡도는 O(1)으로 표현할 수 있습니다.
삭제 - 스택이 끝없이 크더라도 맨 위의 자료를 삭제(pop)하면 되므로, 시간 복잡도는 O(1)로 표현할 수 있습니다.
검색 - 만약 스택에 10개의 블록이 쌓여있다고 생각해보겠습니다. 만약 가장 맨 위에 올려져 있는 자료를 검색한다면, 우리는 별도의 노력 없이 바로 데이터를 찾을 수 있습니다.
하지만 가장 밑에 있는 자료를 검색한다면, 모든 자료를 모두 검색해봐야 합니다. 이럴 경우 모든 자료를 찾아봐야 하므로, 시간 복잡도는 O(n)으로 표현할 수 있습니다.

5. 결론

스택은 후입선출의 특성을 갖는 자료구조다.
함수 호출의 Call Stack이나 실행취소(Ctrl+Z)나 재귀의 작동방식 등이 스택이다.
스택은 자바스크립트에 내장된 자료구조가 아니다. 하지만 위에서 살펴본 것처럼 간단한 스택을 코딩하기에 어렵지는 않다.
스택을 이용하여 탐색, 접근하는 것이 중요하다면 배열이나 다른 자료구조를 활용하는 것이 낫다.
아주 많은 데이터에 대하여 삽입과 제거를 위주로 작업한다면, 스택 자료구조가 적합할 수 있다.

출처 및 참고

Seong Hyeon Kim

삽질도 100번 하면 요령이 생긴다. 부족한 건 경험으로 채우는 백엔드 개발자