개요
스택이란 자료구조는 사전적 정의인 '쌓다' '더미' 와 같습니다. 쉽게 설명하자면, 밑이 막힌 상자를 생각하시면 됩니다. 밑이 막혔으니 위로만 물건을 집어 넣을 수 있고, 뺄 수가 있겠죠? 이러한 구조 때문에 먼저 들어온 물건은 나중에 나갈 수 있고, 나중에 들어온 물건은 먼저 나갈 수 있게 됩니다. 이러한 구조를 '선입후출' '후입선출' 이라고 합니다.
자료구조를 공부하는 데 있어 코드로 구현하는 것도 중요하지만, 그보다 중요한 것은 자료구조를 어떻게 사용할지 아는 것이 더 중요합니다. 모든 자료구조는 [삽입],[삭제],[읽기]를 기본으로 가집니다. 따라서 앞으로 자료구조의 사용법은 이 세가지 위주로 알아보겠습니다.
스택 용도 및 예제
스택은 많은 곳에서 사용됩니다.
우리가 많이 사용하는 브라우저를 생각해봅시다. 인터넷 서핑을 하다가 뒤로가고 싶을 때, 뒤로가기 버튼을 사용합니다. '뒤로가기'버튼이 바로 스택으로 구현된 메쏘드(method) 중 하나입니다.
앞서 스택은 밑이 막힌 상자라고 하였습니다. 상자에 들어 갈 물건들은 그 동안 서핑하였던 인터넷 페이지들 입니다. 그러면 제일 마지막에 봤던 페이지는 가장 위에 쌓여져 있겠지요? (참고로, 우리 눈에 보여지는 페이지는 가장 위에 있는 페이지입니다.) 상자에 들어있는 물건을 빼는 것이 '뒤로가기'입니다. 즉 물건을 빼면 가장 최근에 본 페이지가 빠지겠지요. 그럼 가장 위에 쌓여져 있는 물건은 그 전에 봤던 페이지입니다. 따라서 '뒤로가기'버튼을 누르면 지금 보고 있는 페이지(스택의 최상위)가 빠져나가면서, 이전에 봤던 페이지가 보여지게 됩니다. 이렇게 '뒤로가기' 버튼은 스택의 구조로 구성되어 있습니다.
스택 사용법
다음 그림은 스택 자료구조의 사용법을 쉽게 설명해 줍니다.
(1) 삽입 (Push) : 그림과 같이 물건을 집어 넣는 것을 Push라 합니다. Push는 스택의 구조상 마지막 데이터 위치에 삽입이 됩니다. 나중에 코딩 할 때, 마지막 데이터 위치를 기억하기 위해 top이라는 변수를 만듭니다. 삽입을 한다면 top은 +1이 되겠죠?
(2) 삭제 (Pop) : Push와 반대로 물건을 빼는 것을 Pop이라 합니다. Pop도 Push와 마찬가지로 마지막 데이터 위치에서 삭제가 됩니다. Pop을 하게 된다면 top의 위치는 -1이 됩니다.
(3) 읽기 (Peek) : 마지막 위치(top)에 해당하는 데이터를 읽습니다. 이 때, top의 변화는 없습니다.
*정의된 용어들은 무조건 저렇게 써야된다는 법은 없습니다. 하지만 코드는 가독성이 좋아야 합니다. 많은 사람들이 약속한 용어로 코딩을 하면 변수나 함수명만 봐도 무슨 기능을 갖고 있는지 금방 알 수 있겠죠?
구현에 앞서
스택의 구현 방법은 배열을 사용하는 것과 연결 리스트를 사용하는 것 두 가지가 있습니다. 스택은 밑이 막힌 상자라 하였는데, 이 상자를 배열로 구현할 것인가, 아니면 연결 리스트를 사용하여 구현할 것인가 입니다.
두 방법 모두 장단점이 존재합니다. 배열의 장점은 구현이 쉽고, 원하는 데이터의 접근 속도가 빠릅니다. 만약 내가 원하는 데이터가 배열의 3번째 위치에 있으면 arr[2]를 사용한다면 한번에 접근이 가능하기 때문입니다. 하지만 단점으로는 데이터 최대 개수를 미리 정해야 합니다. 또한 데이터의 삽입과 삭제에 있어 매우 비효율 적입니다. 아래의 그림을 보면, 두번째 위치에 x라는 데이터를 삽입하려고 합니다. 그러면 2,3,4,5,6 데이터들(두번째 위치부터 마지막 데이터까지)은 모두 한칸씩 옮겨 두 번째 칸을 비워놔야 합니다. 칸을 비워놔야 삽입이 가능하기 때문이죠. 만약 100,000,000개의 데이터가 있는데 첫 번째 위치에 데이터를 삽입하려 하면, 그 뒤에 있는 모든 데이터(100,000,000개)를 한칸씩 옮겨야 합니다. 이것은 시간적으로나 비용적으로나 엄청난 손해입니다.
연결 리스트의 장점으로는 데이터의 최대 개수가 한정되어 있지 않고, 데이터의 삽입 삭제가 용이합니다. 연결리스트의 구조는 배열과 다르게 데이터들이 순차적으로 나열되어 있지 않습니다. 아래 그림처럼 연결리스트를 구성하고 있는 요소를 노드라고 합니다. 이 노드는 데이터와 다음 위치에 해당하는 노드의 주소값을 갖습니다. 이러한 구조 때문에 연결리스트 중간에 데이터를 삽입하는 방법은 쉽습니다. 다음 위치에 해당하는 노드의 주소값만 바꿔주면 되기 때문이죠. 하지만 치명적인 단점은 배열과 다르게 한번에 원하는 데이터의 접근이 불가능합니다. 연결되어 있는 링크를 따라 차근차근 하나씩 확인하며 데이터를 찾아야 하기 때문이죠.
이처럼 배열, 연결리스트 각각의 장단점이 있습니다. 배열은 데이터 양이 많지만 삽입/삭제가 거의 없고, 데이터의 접근이 빈번히 이뤄질 때 유리합니다. 반대로 연결리스트는 삽입/삭제가 빈번히 이뤄지고, 데이터의 접근이 거의 없을 때 유리합니다. 각각의 상황에 맞게 배열을 사용할지, 연결리스트를 사용할지는 개발자의 몫인 것 같습니다.
구현
'Programming > Algorithm' 카테고리의 다른 글
| [알고리즘] 2.2.자료구조 : 배열을 이용한 큐(Queue) 구현 (2) | 2017.02.16 |
|---|---|
| [알고리즘] 2.1. 자료구조 : 연결리스트 기반 스택(Stack) 구현 (1) | 2017.02.07 |
| [알고리즘] 2.1. 자료구조 : 배열 기반 스택(Stack) 구현 (0) | 2017.02.07 |
| [알고리즘] 2.3.자료구조 : 트리(Tree) 이해하기와 구현 (1) | 2017.02.02 |
| [알고리즘] 2.2.자료구조 : 큐(Queue) 이해하기 (0) | 2017.01.30 |
