노트

스택

Stack

CS#algorithm · 연결된 개념 7개

쉽게 말하면

스택은 설거지할 접시 더미예요. 맨 위에 올리고 맨 위에서 꺼내니까, 실행 취소나 뒤로 가기처럼 가장 최근에 한 일부터 되돌아가야 할 때 딱 맞아요.

비유가 깨지는 곳 접시는 높이 쌓아도 되지만 함수 호출이 쌓이는 콜 스택은 크기가 정해져 있어요. 재귀가 너무 깊어지면 넘쳐서 스택 오버플로가 나요.

나중에 넣은 것을 먼저 꺼내는(Last In, First Out) 자료구조. 접시를 쌓듯 맨 위에서만 넣고(push) 꺼낸다(pop). 넣기·꺼내기 모두 O(1)이다.

const stack: number[] = []
stack.push(1); stack.push(2)
stack.pop() // 2

JavaScript에서는 배열의 push·pop으로 충분하다. unshift·shift로 앞쪽을 쓰면 매번 원소를 밀어 O(n)이 되니 뒤쪽을 쓴다. 직접 만든다면 연결 리스트의 머리에 넣고 빼는 방식이 된다.

어디에 쓰나

  • 콜 스택(Call Stack): 함수를 부르면 실행 맥락이 쌓이고 끝나면 빠진다. 재귀가 깊어지면 넘쳐서 스택 오버플로(Stack Overflow)가 난다. 자바스크립트가 콜 스택이 빌 때 다음 작업을 꺼내는 흐름은 이벤트 루프 참고
  • 되돌리기: 편집기의 실행 취소 기록(커맨드 패턴)
  • 브라우저 뒤로 가기 기록
  • 괄호 짝 맞추기, 수식 계산, 구문 분석
  • 깊이 우선 탐색: 재귀 대신 명시적 스택으로 구현할 수 있다

먼저 넣은 것을 먼저 꺼내는 반대 구조는 큐다.

연결된 개념

이 노트를 가리키는 문서

뜻이 가까운 노트

  • 콜백

    다른 함수에 인자로 넘겨서 그 함수가 대신 불러 주게 하는 함수. 동기로도, 비동기로도 불릴 수 있다.

  • 마이크로태스크

    현재 실행 중인 코드가 끝난 직후, 다음 태스크로 넘어가기 전에 몰아서 처리되는 작은 작업. 이벤트 루프는 태스크 하나를 끝낼 때마다 마이크로태스크 큐가 빌 때까지 전부 실행한다.

  • 운영 Node 프로세스의 메모리 누수 찾기

    살아 있는 Node 서버에 inspector를 붙이고, 힙 스냅샷 두 장을 비교해 무엇이 쌓이는지, retainer로 누가 붙잡고 있는지 찾는 절차.

  • 우선순위 큐

    원소마다 우선순위가 있고, 들어온 순서와 상관없이 우선순위가 가장 높은 것부터 꺼내는 추상 자료형(Abstract Data Type, ADT). 같은 우선순위끼리의 순서는 보장하지 않는다. 응급실 대기 순서가 좋은 비유다.

  • Oracle PL/SQL

    PL/SQL(Procedural Language/SQL)은 Oracle이 SQL에 변수·조건문·반복문·예외 처리를 더한 절차형 언어(procedural language)다. DB 안에서 함수·프로시저(stored procedure)·트리거(trigger)를 만들어 로직을 데이터 가까이에서 돌린다. 다른 DB에도 비슷한 것(PostgreSQL의 PL/pgSQL 등)이 있지만 문법은 제각각이다.

보기 옵션