[자료구조] 스택 (Stack)

자료구조의 스택에 대해 알아보자.

스택

스택은 쌓아놓은 더미를 뜻한다. 쌓여져 있는 데이터를 한 쪽에서만 넣고 뺄 수 있는 선형 구조로 되어 있다.
LIFO(Last in First out), FILO(First in Last out)의 순서를 따라간다.

---

특징

1. 데이터를 받는 순서대로 정렬해서 저장한다.
2. LIFO는 맨 위, 즉 마지막으로 삽입된 데이터를 먼저 사용한다.
3. FIFO는 맨 아래, 즉 먼저 삽입된 순서대로 데이터를 사용한다.

---

시간복잡도

1. 접근(Access) : 쌓여져있는 순서대로 접근할 수 있기 때문에 O(n)의 시간 복잡도를 가진다.
2. 삽입(insert) 및 삭제(delete) : 가장 위에 삽입하거나 삭제할 수 밖에 없기 때문에 O(1)의 시간 복잡도가 발생한다.
3. 검색(search) : 접근과 마찬가지로 O(n)의 시간 복잡도가 발생한다.

---

스택의 구현

스택은 배열을 사용하거나, 연결 리스트를 사용해서 구현할 수 있다.


1. 배열 : 구현하기 쉽다. 정적인 크기를 갖는다.
2. 연결리스트 : 크기가 동적이지만, 포인터를 위해 추가 메모리 공간이 필요하다.