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

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

선수 지식: JavaScript 변수·배열·조건문을 먼저 익힙니다. 객체 참조나 함수가 낯설면 아래 단계별 예제부터 시작하고, class 전체 구현은 해당 동작을 손으로 추적한 뒤 읽습니다. 각각의 코드는 독립 실행합니다.

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에서 이미 꺼냈습니다.

바로 실행해 보는 핵심 예제

독자 질문: 가장 최근 작업부터 되돌리는 기능에 왜 스택이 맞나요?

왜 쓰나요? 되돌리기는 마지막 변경부터 꺼내는 LIFO 순서가 필요합니다.

아래 바닐라 JavaScript 코드는 독립 실행 예제입니다. 본문에서 배운 개념을 새 데이터로 확인합니다. 다른 예제와 같은 콘솔에 이어 붙이지 말고 새 콘솔 또는 새 .cjs 파일에서 실행하세요.

const history = [];
history.push("제목 수정");
history.push("완료 표시");
console.log(history.pop(), history.at(-1));

실행 결과와 비용

이번 검토에서는 Node.js v24.18.0에서 위 독립 예제를 실행해 다음 출력과 일치하는지 확인했습니다.

완료 표시 제목 수정

시간·공간 복잡도: 배열 끝 push·pop은 보통 분할 상환 O(1), 맨 앞 shift는 O(n)입니다. 실제 메모리 재할당은 구현에 따라 발생합니다.

직접 풀 문제

다시 history.pop()을 실행한 뒤 history.length는 몇인가요?

풀이와 기대 결과

0입니다. 다음 pop은 undefined이므로 빈 상태를 먼저 처리합니다.

원자료의 다른 학습 순서 (선택)

자료구조 과정 원래 순서의 다음 글: 05 큐에서 먼저 들어온 작업부터 처리

검증 범위: 위 독립 예제의 출력만 로컬에서 확인했습니다. 이 글은 독립 자료구조 실습입니다. 실제 브라우저 표시와 모든 입력·플랫폼의 실행은 검증하지 않았습니다.

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

연결 노드로 Stack을 직접 구현해 반환값을 정합니다

배열의 push·pop 대신 top이 가리키는 연결 노드로도 같은 LIFO 규칙을 만들 수 있습니다. A를 넣은 뒤 B를 넣으면 top은 B이고 B.next는 A입니다. pop은 B의 값을 기억한 다음 top을 A로 옮깁니다. peek는 top을 옮기지 않습니다. 아래 Stack은 push가 새 크기를, pop과 peek가 저장한 값을 반환합니다. 노드 객체를 외부로 돌려주지 않으므로 호출자는 내부 next를 몰라도 사용할 수 있습니다.

빈 스택의 pop·peek는 undefined를 반환하고, 그 상태와 구분하기 위해 undefined 저장은 거절합니다. 0·false·null은 정상 데이터입니다. push·pop·peek는 노드 수와 무관하게 O(1), 전체 저장은 O(N)입니다. clear는 top과 size를 초기화하여 연결을 놓으며 실제 메모리 회수 시점은 실행 환경이 정합니다. 두 번 넣고 한 번 꺼냈다면 크기가 1인지, 모두 비운 뒤 다시 넣어도 가장 최근 값이 나오는지 함께 확인해 보세요.

추가 예제 전체 코드와 실행 방법 펼치기

개념 확인 뒤 직접 실행할 때만 펼쳐 보세요. Node.js 시작 안내를 준비한 뒤 supplement-linked-stack.mjs로 저장합니다.

class Stack {
  constructor() { this.top = null; this.size = 0; }
  push(value) {
    if (value === undefined) throw new TypeError('undefined는 빈 스택 표시로 예약합니다.');
    this.top = {value,next:this.top};
    return ++this.size;
  }
  peek() { return this.top === null ? undefined : this.top.value; }
  pop() {
    if (this.top === null) return undefined;
    const removed = this.top;
    this.top = removed.next;
    this.size--;
    return removed.value;
  }
  isEmpty() { return this.size === 0; }
  clear() { this.top = null; this.size = 0; }
}

const stack = new Stack();
stack.push('A'); stack.push('B');
console.log(JSON.stringify({peek:stack.peek(),pop:stack.pop(),size:stack.size}));
stack.clear();
console.log(JSON.stringify({empty:stack.isEmpty(),emptyPop:stack.pop() === undefined}));

파일이 있는 폴더의 터미널에서 실행합니다.

node supplement-linked-stack.mjs

기대 출력

{"peek":"B","pop":"B","size":1}
{"empty":true,"emptyPop":true}

이어서 공부할 개념

• 재귀의 종료 조건: 작은 문제와 기저 조건으로 거듭제곱 계산하기
• 그래프 DFS: 방문 표시로 순환을 멈추고 연결을 따라가기

첨부 test_stack.mjs에서 pop과 peek의 Node 반환을 추적합니다

dev.zip의 dev/test_stack.mjs는 이름에 test가 있지만 assert로 통과·실패를 판정하는 자동 테스트가 아닙니다. console.log와 출력용 메서드로 결과를 관찰하는 시연 파일입니다. 아래에서 호출 뒤 남은 상태와 함수가 반환하는 값을 따로 읽어 보세요. 원본은 상대 모듈을 가져오므로 코드 한 조각만 콘솔에 붙이면 독립 실행되지 않습니다.

원본 Stack은 단방향 리스트의 맨 앞을 스택의 꼭대기로 사용합니다. push(1)부터 push(4)까지 호출하면 head부터 4→3→2→1입니다. 배열 예제의 왼쪽부터 쓴 [1,2,3,4]와 물리적 표현은 달라도 “마지막에 넣은 4부터 꺼낸다”는 LIFO 규칙은 같습니다.

test_stack.mjs의 두 시연을 분리해서 읽기

원본 호출	반환·출력	호출 뒤 head부터 읽은 상태 / count
첫 구간: push(1), push(2), push(3), push(4)	push 반환은 undefined이며 원본은 출력하지 않습니다.	[4,3,2,1] / 4
pop().data 네 번	4, 3, 2, 1을 각각 출력합니다. pop 자체의 반환은 각 Node입니다.	[3,2,1] → [2,1] → [1] → [] / 3 → 2 → 1 → 0
둘째 구간: 1부터 4까지 다시 push, peek().data	4를 출력합니다. peek는 꼭대기 Node를 읽기만 합니다.	[4,3,2,1] / 4
pop() 한 번, peek().data	제거된 4는 출력하지 않고 새 꼭대기 3을 출력합니다.	[3,2,1] / 3
isEmpty(), pop() 세 번, isEmpty()	isEmpty: false, 이어서 isEmpty: true입니다.	[3,2,1] → [] / 3 → 0
마지막 console.log(stack.pop())	null을 출력합니다.	빈 상태 / 0 유지

원본은 pop()이 deleteAt(0)의 Node를 그대로 돌려주므로 시연에 .data가 붙습니다. peek()도 Node를 돌려주되 목록은 바꾸지 않습니다. 같은 꼭대기에서 peek 뒤 pop을 하면 두 결과는 같은 Node 객체입니다. push는 새 크기를 반환하지 않으므로 그 반환값으로 삽입 성공 여부를 판단하지 않습니다.

비었을 때의 동작은 구현별로 확인합니다

구현	pop / peek	호출자가 읽는 방법
첨부 Stack	빈 pop은 예외를 catch하여 null입니다. 빈 peek는 getNodeAt의 예외가 그대로 나옵니다.	비었는지 확인한 뒤 Node.data를 읽습니다. null.data를 읽으면 오류입니다.
기존 보강의 연결 Stack	pop과 peek는 저장한 값, 빈 상태는 둘 다 undefined입니다. push는 새 size입니다.	반환값에 .data를 붙이지 않습니다. undefined 데이터는 이 구현에서 거절합니다.
본문의 배열 push/pop	배열 pop은 저장한 값, 빈 상태는 undefined입니다. push는 새 length입니다.	배열과 첨부 클래스의 이름이 같아도 계약이 자동으로 같아지지 않습니다.

원본 시연은 빈 pop을 확인하지만 빈 peek는 호출하지 않습니다. 따라서 마지막 null 한 줄이 빈 peek의 안전성까지 보장하지 않습니다. 자동 검증으로 옮길 때에는 순서 [4,3,2,1], peek 전후 count 불변, 마지막 head=null·count=0, 빈 pop=null, 빈 peek의 예외를 각각 assert 대상으로 정해야 합니다. 이 연결 방식의 push·pop·peek는 맨 앞만 다루므로 O(1)입니다.

자기 확인: 둘째 구간의 peek 두 번이 4, 3인 이유는 무엇인가요?

첫 peek가 꺼낸 것이 아니라 사이의 pop이 4를 제거했기 때문입니다. 첫 peek 직후 count=4, pop 직후 count=3이며 두 번째 peek 뒤에도 3입니다.