[Data Structure] Stack (스텍)

* Stack (스텍)

스택은 선형 구조이며, 마지막으로 삽입된 값이 가장 먼저 나오는 LIFO(Last in First Out)으로 되어 있습니다. 이 때 삽입하는 과정을 push라고 하며 값을 빼내는 과정을 pop이라고 합니다. 예를 들면 a, b, c 순서로 push하고 스택에 있는 값들을 모두 pop하면 c, b, a 순서로 나오게 되는 것입니다. 또한 스택에는 size, top, empty라는 함수가 있으며 size는 스택에 들어있는 값들의 수를 반환하는 함수이고, top은 마지막으로 삽입된 값을 반환하는 함수, empty는 스택이 비어 있는지 여부를 반환하는 함수입니다.

아래의 두 그림은 stack의 push, pop 과정을 보여주는 그림입니다.

(A) stack push

<그림 1> stack push

(B) stack pop

<그림 2> stack pop

그리고 이러한 스택을 만드는 방법에는 2가지 방법이 있습니다. 하나는 배열을 이용한 방법이고, 다른 하나는 링크드 리스트를 이용한 방법입니다.

1) 배열을 이용한 방법에서는 삽입될 위치인 스택의 마지막 부분을 저장하는 변수 top이 필요합니다. 이 변수를 이용하여 스택의 크기(스택에 들어있는 요소의 수)를 빠르게 알 수 있습니다. 또한 스택의 크기가 0일 경우 스택이 비어 있는 것이므로 비어 있는지 여부도 쉽게 알 수 있습니다. 따라서 배열로 구현하기 위해서는 값들을 담을 배열과 스택의 마지막 위치(삽입될 위치)를 저장하는 변수가 필요합니다.

배열로 구현한 스택의 push 와 pop 과정

<그림 3> stack implemented as an array

2) 링크드 리스트를 이용한 방법에서는 값과 다음 노드의 위치를 저장하는 스택 노드들을 이용할 것이며 마지막으로 삽입된 노드의 위치를 저장하는 노드형 포인터 top과 노드들의 수를 저장하는 변수 size가 필요합니다. Head 초기화 시 처음에 널 값을 넣어주고, push할 경우 새로 삽입되는 노드의 next가 이전의 top이 되고, NewNode가 top이 됩니다.

링크드 리스트로 구현한 스택의 push 와 pop 과정

<그림 4> stack implemented as linked list

* 출처 & 참고 링크

Samsung CodeGround

Stack & Queue & PriorityQueue