자료구조 스택 쉽게 이해하기: push pop으로 문제 풀이 감 잡기

배열 []과 변수만 알고 시작해도 괜찮습니다. 뒤에서 사용하는 반복문과 조건문은 코드 옆에서 설명합니다. 예제는 각각 독립적입니다. 브라우저 개발자 도구의 Console에서 한 블록씩 실행하세요. 같은 이름의 변수를 다시 선언했다는 오류가 나오면 페이지를 새로고침한 뒤 해당 블록을 실행하면 됩니다. console.log는 결과를 화면에 확인하기 위한 명령입니다.

1. 책을 쌓았을 때 어떤 책부터 꺼낼까요?

책상에 A, B, C 순서로 책을 쌓았다고 생각해 보세요. A는 맨 아래, C는 맨 위에 있습니다. 위에서 한 권을 꺼내면 C가 나옵니다. 다시 한 권 꺼내면 B입니다. 마지막에 들어간 것이 먼저 나오는 규칙을 스택이라고 합니다.

한 일	쌓인 책: 아래 → 위	꺼낸 책
A를 올림	A	없음
B를 올림	A → B	없음
C를 올림	A → B → C	없음
위에서 한 권 꺼냄	A → B	C
다시 한 권 꺼냄	A	B

영어로는 LIFO(Last In, First Out)라고 합니다. 약자를 먼저 외우기보다 “맨 마지막에 넣은 C부터 나온다”를 기억하면 됩니다. 실행 취소도 가장 최근 작업부터 되돌린다는 점에서 같은 규칙을 사용합니다.

2. push로 넣고 pop으로 꺼내 봅니다

JavaScript에서는 배열의 오른쪽 끝을 책 더미의 위쪽으로 생각하면 됩니다. push는 그 끝에 추가하고, pop은 그 끝에서 하나를 꺼냅니다.

const books = [];
books.push('A');
books.push('B');
books.push('C');
console.log(books.pop());
console.log(books.join(', '));

출력:

C
A, B

첫 줄은 빈 배열을 만듭니다. 다음 세 줄을 실행하면 배열은 ['A', 'B', 'C']가 됩니다. books.pop()은 C를 결과로 돌려주면서 배열에서도 C를 제거합니다. 그래서 꺼낸 결과는 C이고, 남은 배열에는 A와 B만 있습니다.

join(', ')은 남은 값을 쉼표로 이어 보기 좋게 출력할 뿐입니다. 스택의 규칙과는 관계없습니다. 이 예제에서 꼭 이해할 코드는 push와 pop 두 가지입니다.

3. 보기만 하는 것과 꺼내는 것은 다릅니다

책의 제목만 확인하고 그대로 두고 싶을 수도 있습니다. 배열 번호는 0부터 시작하므로 세 권이면 번호가 0, 1, 2입니다. 마지막 번호는 언제나 length - 1입니다. length는 배열에 든 값의 개수입니다.

const books = ['A', 'B', 'C'];
console.log(books[books.length - 1]);
console.log(books.length);
books.pop();
console.log(books.length);

출력:

C
3
2

두 번째 줄은 마지막 값 C를 읽기만 합니다. 그래서 개수는 여전히 3입니다. 이후 pop()을 실행하면 실제로 제거되어 개수가 2가 됩니다. 비어 있는 배열에서 pop을 호출하면 꺼낼 값이 없어 undefined가 나옵니다.

잠깐 확인: 빈 스택에 A, B를 넣고 하나를 꺼낸 뒤 C를 넣었습니다. 다음에 꺼낼 값은 무엇일까요?

정답과 과정 보기

C입니다. [] → [A] → [A, B] → [A] → [A, C] 순서로 변합니다. B는 앞선 pop에서 이미 꺼냈습니다.

4. 괄호 문제에서는 무엇을 쌓을까요?

이제 책 대신 아직 짝을 만나지 못한 여는 괄호를 쌓아 보겠습니다. 이번에는 (와 )만 있는 문자열을 다룹니다. (가 나오면 저장하고, )가 나오면 저장해 둔 ( 하나를 꺼내 짝을 맞춥니다.

예를 들어 (())는 다음 순서로 읽습니다. 코드를 보기 전에 표의 스택이 어떻게 바뀌는지 따라가 보세요.

읽은 위치와 문자	하는 일	남은 여는 괄호
1번째: (	여는 괄호를 push	[‘(‘]
2번째: (	여는 괄호를 push	[‘(‘, ‘(‘]
3번째: )	최근 여는 괄호를 pop	[‘(‘]
4번째: )	최근 여는 괄호를 pop	[]

끝까지 읽었고 남은 괄호도 없으므로 짝이 맞습니다. 반대로 )(는 첫 글자부터 실패합니다. 닫을 괄호가 나왔는데 앞에서 열어 둔 괄호가 없기 때문입니다. (()는 끝에 여는 괄호 하나가 남아서 실패합니다.

5. 표에서 한 일을 코드로 옮깁니다

먼저 정상 입력 (())만 넣어 움직임을 출력해 보겠습니다. for...of는 문자열에서 문자를 하나씩 꺼내는 반복문입니다. 아래 코드는 동작 관찰용이며 아직 잘못된 입력을 판정하는 완성 함수는 아닙니다.

const stack = [];
for (const ch of '(())') {
  if (ch === '(') {
    stack.push(ch);
  } else {
    stack.pop();
  }
  console.log(stack.length);
}

각 문자를 처리한 뒤 남은 개수:

1
2
1
0

if (ch === '(')는 “지금 문자가 여는 괄호인가?”라는 질문입니다. 맞으면 저장하고, 아니면 닫는 괄호이므로 하나를 꺼냅니다. else는 앞 조건이 맞지 않을 때 실행할 부분입니다. 표에서 했던 일을 순서대로 적은 것입니다.

여기에 두 가지 검사만 붙이면 됩니다. 첫째, 닫는 괄호를 읽었을 때 스택이 이미 비어 있으면 바로 실패합니다. 둘째, 전부 읽은 뒤 스택에 여는 괄호가 남아 있으면 실패합니다.

6. 전체 코드: 두 가지 실패 조건을 붙입니다

아래 함수에는 (와 )로만 이루어진 문자열을 넣습니다. return은 결과를 돌려주고 함수를 끝냅니다. true는 짝이 맞음, false는 맞지 않음입니다.

function isBalanced(text) {
  const stack = [];
  for (const ch of text) {
    if (ch === '(') {
      stack.push(ch);
    } else {
      if (stack.length === 0) {
        return false;
      }
      stack.pop();
    }
  }
  return stack.length === 0;
}
console.log(isBalanced('(())'));
console.log(isBalanced(')('));
console.log(isBalanced('(()'));
console.log(isBalanced(''));

출력:

true
false
false
true

검사 순서도 중요합니다. 빈 상태인지 먼저 확인한 다음 pop을 해야, 짝 없이 닫는 괄호가 나온 순간을 놓치지 않습니다. 마지막 stack.length === 0은 남은 여는 괄호가 없는지 확인합니다. 빈 문자열은 짝이 틀린 괄호가 없으므로 여기서는 true로 정했습니다.

직접 해 보기: 위 함수에 ()()와 ())(를 넣기 전에 결과를 예상해 보세요.

정답과 이유 보기

()()는 true입니다. 스택 개수가 1 → 0 → 1 → 0이 됩니다. ())(는 false입니다. 세 번째 문자에서 이미 스택이 빈 상태인데 닫는 괄호가 나오므로, 마지막 문자까지 기다리지 않고 실패합니다.

7. 다음 문제로 넘어가기 전에

지금은 “여는 괄호를 왜 저장하는가?”, “닫는 괄호가 나왔을 때 왜 가장 최근 것을 꺼내는가?”, “왜 마지막에 빈 상태를 검사하는가?”를 설명할 수 있으면 충분합니다. 코드를 외우는 대신 이 세 질문에 답해 보세요.

코딩테스트: 올바른 괄호 판별로 연결해 연습하세요. 해당 문제에서는 괄호 개수만 세는 카운터 풀이도 볼 수 있습니다. 괄호 종류가 하나이면 개수로도 풀 수 있고, []와 {}까지 섞이면 최근 괄호의 종류도 기억해야 합니다. 여러 종류의 검사는 이 글의 기본 실습을 이해한 다음 확장하면 됩니다.

먼저 온 작업부터 처리하는 구조는 스택이 아니라 큐와 FIFO입니다. 스택은 최근 것부터, 큐는 먼저 온 것부터라는 차이를 비교해 보세요.

더 알아보기: 처리량을 O(N)으로 표현하는 이유

문자가 4개이면 네 번, 100개이면 백 번 읽습니다. 이처럼 입력 길이에 비례해 일이 늘어나는 것을 O(N)이라고 씁니다. N은 문자 개수입니다. 모두 여는 괄호이면 스택에도 N개가 쌓일 수 있습니다. 배열 끝의 push·pop은 일반적인 동적 배열 모델에서 여러 번의 작업을 합쳐 볼 때 한 번당 상수 비용으로 분석하지만, 개별 push의 배열 확장 비용까지 모두 같다는 뜻은 아닙니다. 처음 읽을 때는 문자마다 한 번씩 처리한다는 점만 이해해도 됩니다.

참고 자료

• MDN: 배열 끝에 추가하는 push
• MDN: 배열 끝에서 꺼내는 pop