스택

접시를 차곡차곡 쌓아 올리듯이 자료를 하나씩 쌓아 올린 형태의 자료구조이다. 가장 먼저 입력된 데이터는 맨 아래에 놓이고 그 다음 입력되는 데이터가 그 위에 쌓이는 구조이다. 따라서 스택의 맨 위에는 가장 최근에 입력된 데이터가 놓이게 된다.

스택에서는 맨 위의 데이터만 입 · 출력을 할 수 있으며, 스택의 중간에서는 데이터를 삽입하거나 삭제할 수 없다. 입 · 출력이 이루어지는 부분을 스택 상단(top) 이라고 하고, 반대쪽인 바닥 부분을 스택 하단(bottom) 이라고 한다.

top의 위치에서만 데이터를 삽입하므로 먼저 삽입한 데이터는 밑에 쌓이고 나중에 삽입한 데이터는 위에 쌓인다. 맨 마지막에 삽입한 데이터는 맨 위에 있다가 가장 먼저 삭제되는데 이러한 구조를 후입선출(LFO: Last-In First-Out) 구조라고 한다.

스택은 선형 자료구조의 한 종류로, 모든 데이터들의 삽입과 삭제가 한 쪽 끝에서만 이루어지는 제한된 리스트 구조이다.

스택은 스택의 크기를 벗어나는 오버플로우와 언더플로우가 발생할 수 있다.

오버플로우(overflow) : 데이터를 저장할 수 있는 공간이 가득차서 더 이상 삽입할 수 없는 상태임에도 삽입 연산이 일어나는 경우 발생한다.
언더플로우(underflow) : 스택에 삭제할 데이터가 남아있지 않은 비어있는 상태임에도 삭제 연산이 일어나는 경우 발생한다.