thumnail.png

스택(Stack)

stack.png

스택은 단어 그대로 데이터를 쌓아놓는 자료구조 형태를 뜻한다. 쌓아논 데이터는 아래가 막혀있으니 당연히 위에서 부터 접근할 수 있고, 자연스럽게 처음에 들어온 데이터가 마지막에 나가고 나중에 들어온 데이터가 가장 먼저 나가는 LIFO(Last In First Out) 형식의 자료구조를 가지게 된다.

스택은 스택의 가장 상단에 있는 데이터를 Top, 그리고 상단에 데이터를 추가하는 작업을 Push, Top데이터를 제거하는 작업을 Pop이라고 한다.

스택을 구현하는 방법은 배열을 사용하는 방식과 링크드 리스트를 사용하는 총 2가지의 방법이 있다.

배열을 사용한 스택 구현

배열을 이용해 스택을 구현할 때는 스택을 위한 배열을 만들고 인덱스값을 조정하며 구현하면 된다. 인덱스가 0이면 스택이 비어있는 것이고, 스택에 데이터를 Push할 때는 현재 인덱스에 데이터를 넣고 인덱스를 1추가하면 된다. 반대로 스택에서 데이터를 Pop할 때는 인덱스를 1만큼 뺀 후 현재 인덱스의 데이터를 제거하면 된다.

배열을 사용한 스택 구현은 구현이 쉽고 원하는 데이터로의 접근 속도가 빠르다. 인덱스를 통해 접근하기 때문에 인덱스 값만 가지고 있다면 빠르게 원하는 데이터로 접근할 수 있다. 하지만 배열이기 때문에 최대 데이터 개수를 미리 지정해놔야 하기 때문에 스택의 크기를 확장하거나 줄일 때 효율성이 떨어지게 된다.

링크드 리스트를 사용한 스택 구현

링크드 리스트를 사용한 스택 구현 또한 간단하다. 첫 데이터의 경우 새로운 노드를 생성하면 되고, 그 이후에 새로운 데이터가 Push될 때마다 새로운 노드를 생성 후 포인터로 연결하면 된다. 반대로 제거하는 과정은 마지막 포인터에 연결된 노드를 제거하기만 하면 된다.

링크드 리스트를 사용한 스택 구현은 데이터의 최대 개수가 한정되어 있지 않고, 데이터의 삽입 삭제가 쉽다. 하지만 특정 값에 접근하기 위해서는 모든 노드를 탐색하며 접근해야 하기 때문에 효율성이 떨어지게 된다.