[자료구조] 스택(Stack)
스택은 마지막에 들어온 것이 먼저 나가는 LIFO(Last In First Out) 구조를 가진 자료 구조입니다. 일상 생활에서 책을 쌓고, 책을 꺼내는 것과 브라우저에서 서핑 후 뒤로가기 버튼을 누르는 것과 같습니다.
스택에서 데이터를 넣는 것을 push , 데이터를 꺼내는 것을 pop 이라고 합니다. 그리고 push와 pop을 하는 위치를 top이라고 하고, 스택의 가장 아랫부분을 bottom이라고 합니다.
스택 구현
스택은 Array 또는 Linked List 로 구현 할 수 있습니다.
Array 기반 스택은 접근 속도가 빠르지만 변경이 용이하지 않습니다. 배열은 생성할 때, 메모리의 연속된 공간에 데이터를 저장합니다. 그렇기 때문에 검색할 때는 데이터를 빠르게 찾을 수 있지만, 변경이 일어났을 때는 새로운 배열을 생성하고, 생성된 배열에 데이터를 복사해야하기 때문에 느려집니다. 복사해야할 데이터가 많지 않다면, 크게 상관 없지만 데이터가 많아질수록 점점 더 느려질 것입니다.
반면에 Linked List 기반 스택은 메모리 주소를 통해 노드가 연결되어 있어, 가르키는 메모리 주소만 변경하면 되므로, 등록, 수정과 같은 변경에는 빠르게 반응할 수 있습니다. 하지만, 메모리에 연속된 공간에 존재하지 않기 때문에 검색 데이터를 찾기 위해 노드를 순회해야하므로 검색 속도는 좋지 않습니다.
그래서 검색이 자주 일어나고, 등록, 수정 등 변경이 자주 일어나지 않는다면, 배열 스택으로 구현하는 것이 좋습니다. 반대로 검색보다는 등록, 수정이 빈번히 일어나는 경우에는 연결리스트 스택을 사용하는 것이 좋습니다.
Array Stack 구현
구현에 앞에 필요한 기능을 정의하면, 아래와 같습니다.
- 사용자는 임의의 사이즈를 가진 스택을 생성할 수 있다.
- 사용자는 데이터 한개를 추가할 수 있다.
- 사용자는 데이터 한개를 삭제할 수 있다.
- 사용자는 스택을 비울 수 있다.
- 사용자는 현재 추가된 데이터의 개수를 알 수 있다.
- 사용자는 마지막에 추가된 데이터를 알 수 있다.
- 사용자는 스택 안에 데이터가 비어있는지 확인 할 수 있다.
- 사용자는 스택이 가득 차 있는지 확인 할 수 있다.
- 사용자는 특정 인덱스에 있는 데이터를 알 수 있다.
이 요구사항으로 아래와 같이 스택을 구현할 수 있다.
Linked List Stack 구현
Linked List Stack 은 Array Stack 과 다르게 크기에 대한 제한이 없다. capacity() , isFull(), indexOf() 메서드를 구현할 필요가 없다. 다만, 데이터 연결을 위한 노드를 구현해야한다.
실제 구현된 코드는 https://github.com/metocherry/data-structure-and-algorithms에서 확인할 수 있습니다.