[Section 3] 스택(Stack)의 종류와 개념 이해하기

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

선형 자료구조는 자료를 순차적으로 구성하였기 때문에 그 정보에 접근하기 위한 알고리즘은 역시 순차적이다. 이러한 선형 자료구조의 종류에는  리스트, 스택 그리고 큐 존재한다. 만약 연결 리스트의 알고리즘 개념에 기반하여 자료 구조를 이해했다면, 지금 부터는 그 종류와 개념만으로 스스로 구현해 볼 수 있을 것이다. 이번 시간에는 스택(Stack)의 종류와 그 개념을 이해해 보도록 한다.

1. 스택 자료 구조의 이해

스택(Stack)은 연결 리스트와 아주 유사한 자료 구조 개념이다. 이는 연결 리스트를 수직으로 쌓아 올린 것과 비슷하다. 다음의 그림을 참고하자.

 

스택 개념의 이해 _ LIFO와 FILO

 

왼쪽의 그림은 LIFO(Last In First Out)로 나중에 넣은 데이터가 제일 먼저 나간다는 의미이고, 오른쪽 그림은 FILO(First In Last Out)로 먼저 넣은 데이터가 제일 마지막에 나간다는 의미이다. 이해를 돕기 위해서 LIFO를 기준으로 데이터의 삽입과 삭제 과정을 다음과 같이 비교해보자. 일반적으로 스택 구조에서 데이터의 삽입을 푸시(Push)라고 하며, 삭제를 팝(Pop)이라고 한다.

 

LIFO 스택의 데이터 삽입과 삭제 방식

 

위 과정을 보면 가장 마지막에 넣은 데이터(D)가 제일 먼저 삭제된다는 것을 이해할 수 있다.

2.  스택의 종류와 ADT _ 배열 스택, 연결 리스트 스택

스택은 연결 리스트와 아주 유사하기 때문에, 배열로 구현이 가능하다. 이 배열 스택은 가장 단순한 형태의 스택으로 데이터의 삽입과 삭제에 해당하는 시간 복잡도가 모두 O(1)이다. 하지만, 배열의 고정적 사이즈 때문에 존재하는 메모리 한계를 가지고 있다.  

 

위 단점을 커버하기 위해서 만들어진 것은 놀랍게도 연결 리스트와 동일하다. 단지, 삽입과 삭제의 순서가 정해져 있는 연결 리스트일 뿐이다. 시간 복잡도 측면에서는 연결 리스트로 구현된 스택과 배열 스택 모두 동일하다. 

 

스택을 구현하기 위한 주 ADT 기능은 역시 팝(Pop)과 푸시(Push)에 있다. 보조 ADT는 스택의 크기 기능과 LIFO 혹은 FILO 방식을 바꾸는 기능 등의 사용자 편의에 맞게 생성하면 된다.