[자료 구조] 스택(Stack)

스택이란 처음에 들어간 데이터가 가장 나중에 나오게 설계된 자료구조이다.
이를 FILO(First in last out) 또는 LIFO(Last in first out)이라고 한다.
요소의 삽입과 삭제가 자료구조의 한쪽 끝에서만 이루어지는 것이 특징이다.

쉽게 말하면 한 쪽만 열리는 셔틀콕 케이스를 생각하면 이해하기 쉬울 것 같다.
셔틀콕 케이스에 셔틀콕을 하나 넣고, 그 다음에 다른 셔틀콕들을 넣으면 처음에 넣은 서틀콕을 사용하기 위해선, 위에 쌓인 셔틀콕들을 모두 사용한 이후에나 사용이 가능하다.
이 형태가 스택 자료구조의 형태라고 볼 수 있다.

성능

• 탐색의 성능은 구현하는 방식에 따라 다르다.
  연결 리스트로 했을 경우는 O(n)의 시간복잡도를 가진다.
• 추가/제거에 대해서는 O(1)의 시간복잡도를 가진다.

장점

• 구현이 쉽다.

단점

• 입/출력에 제한을 받는다.

Code

• Github에서 연결 리스트로 구현한 스택 코드 보기
• Github에서 스택 계산기 코드 보기

Usage

• 자동 메모리
• 대부분의 네트워크 프로토콜 (tcp 등)
• 텍스트 분석 프로그램