도입

스택(Stack)이란 후입선출 (Last In First Out - LIFO) 특성을 가지는 자료구조이다. 즉, 먼저 들어간 것이 나중에 나오고, 나중에 들어간 것이 먼저 나온다는 특성을 가지고 있다. 쌓여 있는 접시, 프링글스 등에 스택을 비유할 수 있다. 후입선출이라는 특징은 선입선출이라는 특징을 가지고 있는 큐와 비교되는 스택의 특징이다.

스택의 ADT

스택 자료구조의 ADT는 다음과 같다.

• void StackInit(Stack* pstack) : 스택의 초기화를 진행하는 함수이다. 스택 생성 후 제일 먼저 호출되어야 하는 함수이다.
• int IsEmpty(Stack* pstack) : 스택이 빈 경우 TRUE(1)을, 그렇지 않으면 FALSE(0)을 반환하는 함수이다.
• void Push(Stack* pstack, Data data) :스택에 데이터를 저장하는 함수이다. 매개변수 data로 전달된 값을 저장한다.
• Data Pop(Stack* pstack) : 마지막에 저장된 요소를 삭제하는 함수이다. 삭제된 데이터는 반환되며, 이 함수를 호출하려면 하나 이상의 데이터가 스택에 존재해야 한다.

스택의 사용 사례

• 후위 표기법 계산
• 수식의 괄호 검사
• 실행 취소 (Undo)
• 웹 브라우저 방문기록 (뒤로 가기)

스택의 구현 방법

스택을 구현하는 방법에는 두 가지가 있다.

배열 사용

• 장점 : 구현하기 쉽다.
• 단점 : 크기가 동적이 아니어서 런터임 시 필요에 따라 늘어나거나 줄어들지 않는다.

연결 리스트 사용

• 장점 : 크기가 동적이다. 런타임 시 필요에 따라 크기를 조절할 수 있다.
• 단점 : 포인터를 위한 추가 메모리 공간이 필요하다.

스택의 시간 복잡도

• 접근 : O(n)
• 탐색 : O(n)
• 삽입 (push) : O(1)
• 삭제 (pop) : O(1)

스택 자료구조는 위에서부터 차례대로 접근하거나 탐색할 수 있기 때문에 접근과 탐색의 시간 복잡도는 O(n)이다.

스택 자료구조의 삽입(push), 삭제(pop)은 항상 맨 위에서 일어난다. 따라서 push와 pop의 시간 복잡도는 O(1)이다.