스택 자료구조는 접시에 음식을 쌓아올리듯 데이터를 차곡차곡 쌓아올린 형태로 자료를 구성한다. 이러 형태는 뷔페에 쌓아 둔 접시, 책상 위에 쌓아 둔 책, 채점을 하지 않은 채로 쌓아 둔 리포트, 제기에 차곡차곡 쌓아올려진 음식 등 주변에서 흔히 볼 수 있다.

이와 같이 일상에서 사용하는 쌓아올리는 방식을 추상화하여 자료구조로 정의한 것이 스택이다. 스택은 같은 구조와 같은 크기의 데이터를 정해진 방향으로만 쌓을 수 있고, top으로 정한 한 곳으로만 접근하도록 제한되어 있다. 따라서 top을 통해 들어온 데이터가 일정한 방향, 즉 아래에서 위로 차곡차곡 쌓이게 된다.

스택에서 top은 삽입과 삭제가 일어나는 위치로, 현재 스택의 가장 위에 있는 데이터 위치가 된다. 새로 삽입되는 데이터는 top 위치에 있는 데이터 위에 쌓이게 되는데, 그러면 삽입된 데이터가 스택에서 가장 위에 있는 데이터가 되므로 top은 새로 삽입된 데이터의 위치로 갱신된다. 따라서 top은 항상 스택의 가장 위에 있는 데이터, 즉 가장 마지막에 삽입된 데이터의 위치를 의미하는 상태를 유지한다. 스택에서 자료를 삭제할 때도 top을 통해서만 가능하기 때문에 top에 있는 데이터, 즉 가장 위에 있는 데이터가 삭제된다. 스택은 top으로 정한 곳에서만 삽입과 삭제가 가능하다는 원리에 따라 삽입한 순서대로 데이터가 아래에서 위로 쌓이게 되어, 가장 마지막에 삽입된 데이터가 가장 먼저 삭제된다는 구조적 특징을 갖는다. 이러한 스택의 동작 구조를 후입선출이라고 한다.

연탄불에 삼겹살을 굽는 식당을 떠올려 보자. 삼겹살을 시키면 먼저 연탄을 넣어 주는데, 연탄을 넣을 수 있는 입구는 하나뿐이므로 연탄을 하나씩 순서대로 넣어야 한다. [ 그림 5-3 ] 과 같이 먼저 1번 연탄을 넣고, 그 위에 2번, 3번 연탄을 순서대로 넣는다. 다 탄 연탄을 꺼낼 때도 연탄을 넣었던 구멍으로 하나씩 꺼내야 한다. 제일 나중에 넣어서 가장 위에 있는 3번 연탄을 꺼내고, 그 다음 2번, 1번 연탄을 순서대로 꺼낸다. 가장 늦게 넣은(Last-In) 연탄을 가장 먼저 꺼냈으니(First-Out) 연탄 아궁이는 스택의 LIFO 구조라 할 수 있다.

슈퍼맨이 옷을 갈아입는 순서도 스택의 LIFO 구조라 할 수 있다. 슈퍼맨이 옷을 벗는 순서는 장화, 망토, 빨간 팬츠, 파란 옷의 순서이다. 다시 옷을 입을 때는 벗을 때와 반대로 파란옷, 빨간 팬츠, 망토, 장화의 순서가 된다. 마지막에 벗은 파란 옷을 가장 먼저 입었으니 LIFO 구조인 셈이다.

스택에서 데이터가 삽입되고 삭제되는 순서를 결정하는 LIFO 구조는 반드시 지켜져야 한다. 만약 슈퍼맨이 빨간 팬츠, 파란옷 순서로 벗었다가 빨간 팬츠, 파란 옷 순서로 입고 출동하여 슈퍼맨을 상징하는 파란 옷 위의 빨간 팬츠가 보이지 않으면, 누가 그를 슈퍼맨이라고 부르겠는가?

스택에서 top을 통한 삽입 연산을 push라 하고, top을 통한 삭제 연산을 pop이라고 한다. 출근 시간에 만원 지하철을 경험해 본 사람이라면 push와 pop의 이해가 쉬울 것이다. 만원 지하철에 타려면 출입문에 있는 사람들을 밀고 들어가거나 푸시맨의 도움을 받아야 한다. 그리고 지하철 문이 열리면 내리려는 사람들 때문에 출입문 근처에 있던 사람, 즉 가장 마지막에 타서 출입문 가까이 있던 사람이 먼저 밖으로 튕겨 나가게 된다.

공백 스택에 데이터를 삽입하고 삭제하는 동안의 스택을 살펴보면 다음과 같다.

스택에 데이터를 A, B, C 순서로 삽입하면, 삭제 순서는 C, B, A가 된다. 스택의 LIFO 동작 특성으로 인해 스택에서의 삭제 순서는 삽입 순서의 역순이 된다.