edubun English
홈›프로그래밍›자료 구조

스택

{[()()]}의 괄호 짝이 맞는지 확인하는 데는 스택 하나와 괄호마다 한 번씩, 넣기와 꺼내기 8번이면 됩니다.

나중에 넣은 것이 먼저

접시 더미를 떠올려 봅시다. 깨끗한 접시는 맨 위에 올리고, 필요할 때도 맨 위에서 가져갑니다. 마지막에 올린 접시가 가장 먼저 나옵니다. 스택은 바로 이 규칙을 따르는 자료 구조로, 이 규칙을 후입선출(LIFO, last in first out)이라고 합니다. 주요 연산은 두 가지입니다. push는 맨 위에 값을 올리고, pop은 맨 위 값을 빼서 돌려줍니다. 많은 스택에는 맨 위 값을 빼지 않고 보기만 하는 peek도 있습니다.

MIT 6.006 강의 노트에서 스택은 순서열 인터페이스의 특별한 경우로, insert last(x)와 delete last()만 쓰는 것입니다. 이것만 봐도 만드는 방법이 보입니다. 값을 동적 배열에 담고 배열의 끝을 맨 위로 삼습니다. 지난 단원에서 끝쪽이 싼 쪽이었으므로 push와 pop은 각각 1단계입니다(가끔 옮겨 적는 일이 있어 분할 상환 기준입니다). 스택의 크기는 상관이 없습니다. 값이 3개인 스택에서 꺼내든 300만 개인 스택에서 꺼내든 똑같이 한 단계입니다.

const stack = [];
stack.push(4);
stack.push(8);
stack.push(5);
console.log(stack.pop());           // 5, the last one pushed
console.log(stack[stack.length - 1]); // peek: 8
console.log(stack.length);          // 2
불러오는 중

끌어서 돌리고, 휠이나 두 손가락으로 확대하세요.

더미 모양으로 그린 스택입니다. 넣기와 꺼내기는 맨 위에서만 일어납니다. 괄호 문자열을 고르고 괄호 검사를 누르면 스택이 짝이 맞는지 판단하는 과정이 보입니다.

괄호 짝 검사

스택의 대표적인 쓰임새는 괄호의 짝이 맞는지 검사하는 일로, 모든 코드 편집기와 컴파일러가 이 일을 합니다. 글을 왼쪽부터 읽습니다. 여는 괄호 (, [, {는 스택에 넣습니다. 닫는 괄호는 스택 맨 위의 여는 괄호와 짝이 맞아야 합니다. 맞으면 그 여는 괄호를 꺼내고, 스택이 비었거나 맨 위가 다른 종류라면 짝이 맞지 않는 문자열입니다. 다 읽었을 때 스택이 비어 있어야 합니다. 그렇지 않으면 닫히지 않은 여는 괄호가 있는 것입니다.

실험실에서 문자열을 바꿔 가며 해 보세요. {[()()]}는 넣기 4번, 꺼내기 4번으로 모두 8단계이고, 끝에 스택이 비어 있습니다. ([)]는 세 번째 글자에서 실패합니다. 맨 위에 [가 있는데 )가 오기 때문입니다. (()는 끝까지 읽어도 ( 하나가 남습니다. 왜 이 일에 스택이 맞을까요? 괄호는 겹겹이 들어가고, 가장 최근에 연 괄호가 가장 먼저 닫혀야 합니다. 그것이 바로 후입선출입니다.

스택이 쓰이는 다른 곳

  • 호출 스택. 함수 a가 b를 부르고 b가 c를 부르면 컴퓨터는 호출마다 기록을 넣습니다. c가 끝나면 그 기록을 꺼내고 b가 멈춘 곳에서 이어 갑니다. 끝나지 않는 재귀가 이 스택을 가득 채우면 「스택 오버플로」 오류가 납니다.
  • 되돌리기. 편집기는 바꾼 내용을 하나씩 넣어 두고, 되돌리기를 누르면 가장 최근 것을 꺼내 되돌립니다.
  • 뒤로 가기. 브라우저는 떠나는 페이지를 넣어 두고, 뒤로 가기를 누르면 마지막 페이지를 꺼냅니다.
  • 깊이 우선 탐색. 알고리즘 과정에서 미로를 갈 수 있는 데까지 깊이 들어갔다가 되돌아올 때 스택을 썼습니다.
배경계산에 쓰는 스택이라는 생각은 흔히 뮌헨의 프리드리히 L. 바우어와 클라우스 자멜존에게서 시작되었다고 봅니다. 두 사람은 산술식을 번역하는 방법을 연구하면서 미뤄 둔 연산을 마지막에 넣은 것이 먼저 나오는 저장소에 보관했고, 이 저장소를 독일어로 지하실이라는 뜻의 켈러(Keller)라고 불렀습니다. 두 사람은 1957년에 이 방법으로 특허를 출원했고, 미국 특허는 1962년에 나왔습니다. 비슷한 시기에 RAND 연구소의 앨런 뉴얼, 클리프 쇼, 허버트 사이먼이 만든 리스트 처리 프로그램도 재귀가 많아 스택에 기댔습니다.
  1. 스택은 값을 어떤 순서로 돌려줄까요?
    • 먼저 넣은 것부터
    • 나중에 넣은 것부터
    • 작은 것부터
    • 아무 순서로나
  2. 빈 스택에서 4 넣기, 8 넣기, 5 넣기, 꺼내기, 2 넣기를 했습니다. 맨 위 값은?
    • 4
    • 8
    • 5
    • 2
  3. 그 연산들이 끝난 뒤 스택에 값이 몇 개 있을까요?
  4. A, B, C 순서로 넣고 빌 때까지 꺼냅니다. 꺼낸 값을 순서대로 놓으세요.
  5. 괄호 검사 방법으로 {[()()]}를 검사하면 넣기와 꺼내기가 모두 몇 번일까요?
  6. ([)]를 왼쪽부터 검사하면 어디서 실패할까요?
    • 첫 (
    • [
    • )
    • 마지막 ]
  7. (()는 무엇이 문제일까요?
    • 스택이 빈 채로 닫는 괄호가 온다
    • 끝났을 때 ( 하나가 스택에 남는다
    • 대괄호가 없다
    • 문제없이 짝이 맞는다
  8. 동적 배열로 만든 스택에 값이 1,000개 있을 때 꺼내기는 몇 단계일까요?
  9. main이 draw를 부르고, draw가 line을 부릅니다. line이 실행되는 동안 호출 스택 맨 위의 기록은?
    • main
    • draw
    • line
    • 없음
  10. 바우어와 자멜존이 스택 방법으로 특허를 출원한 해는?
    • 1946년
    • 1957년
    • 1962년
    • 1972년
핵심 정리
  • 스택은 후입선출입니다. 맨 위에 넣고 맨 위에서 꺼냅니다.
  • 동적 배열의 끝을 쓰면 넣기와 꺼내기는 각각 1단계입니다.
  • 괄호 검사는 여는 괄호를 넣고 닫는 괄호마다 꺼냅니다. {[()()]}는 8단계입니다.
  • 호출 스택, 되돌리기, 뒤로 가기 단추가 스택입니다.
이 과정의 출처 (5)
  • MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon), lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append), 4 Hashing (chaining, pigeonhole collisions, chain length n/m), 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
  • MDN Web Docs, Array.prototype.shift (shifts all values left by 1), Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
  • ECMAScript 2025 Language Specification (tc39.es/ecma262), 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements"), Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
  • D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
  • "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).

확인한 날: 2026-10-18