Stack(스택)

가장 마지막으로 삽입된 원소가 가장 먼저 제거되는 LIFO(Last In, First Out) 형태의 자료구조
한 쪽 끝에서만 자료를 삽입하고 삭제할 수 있는 선형구조

Stack의 연산

push(item)

• item 하나를 스택의 가장 윗 부분에 추가
• 스택이 가득 찼을때 push를 하면 스택 오버플로우가 일어남

pop()

• 스택에서 가장 위에있는 item을 제거
• 스택이 비어있을때 pop을 하면 스택 언더플로우가 일어남

peek() / top()

• 스택의 가장 위에 있는 item을 반환
• 스택이 비어있다면 연산 불가

isEmpty()

• 스택이 비어있다면 True를 반환하고 비어있지 않다면 False를 반환

size()

• 스택의 size를 반환

시간복잡도

Search(검색)

• 특정 데이터를 찾을 때는 순차적으로 접근하여 찾아야함
• 시간복잡도 O(n)

Insert(삽입)

• 맨 위에 데이터를 삽입하므로 시간복잡도 O(1)

Deletion(삭제)

• 맨 위의 데이터 삭제하므로 시간복잡도 O(1)

구현

Array

• 배열은 메모리의 연속된 공간에 데이터를 저장하므로 데이터를 빠르게 찾을 수 있어 접근 속도가 빠름
• 삽입, 삭제와 같은 변경이 일어나면 새로운 배열을 생성하고 데이터를 복사해야하므로 속도가 느려짐
• 스택의 크기에 제한이 있음

Linked List

• 메모리 주소를 통해 노드가 연결되어 있으므로 삽입, 삭제와 같은 변경에는 빠르게 반응함
• 메모리에 연속된 공간에 존재하지 않기 때문에 검색 데이터를 찾기 위해 노드를 순회해야하므로 검색 속도는 느림
• 스택의 크기에 제한이 없음

참조
https://ko.wikipedia.org/
https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html
https://medium.com/@jinseok.choi/%EC%8A%A4%ED%83%9D-stack-48a22e52268b