Technical Interview Master Plan [6] - Stack을 알아도 왜 괄호·히스토그램 문제에서 자꾸 막히는가

이번 챕터에서는 스택 Stack 에 대해 알아보도록 합니다.

Stack

Introduction to Stack

접시 더미를 상상해 보자. 새로운 접시는 오직 맨 위에만 올릴 수 있고, 접시가 필요할 때는 맨 위에 있는 것을 가져간다. 위에 놓인 접시들을 먼저 치우지 않고서는 맨 아래나 중간에서 접시를 꺼내는 것은 불가능하다.

접시 추가하기

        [ plate ]
           ↓
      -------------
      [ plate ]
      [ plate ]
      [ plate ]
      [ plate ]
      [ plate ]


접시 꺼내기

        [ plate ]   ↗  remove plate
      -------------
      [ plate ]
      [ plate ]
      [ plate ]
      [ plate ]
      [ plate ]

이 비유는 스택 자료구조의 본질을 잘 담고 있다. 접시를 스택의 맨 위에 올리는 것과 맨 위에서 접시를 꺼내는 행위는 스택의 두 가지 주요 연산을 물리적으로 보여 준다. Push는 원소를 스택의 맨 위에 추가하는 것이고, Pop은 스택의 맨 위에 있는 원소를 제거하고 반환하는 것이다.