[자료구조] 스택 (Stack)

📚 스택 (Stack)

스택 (Stack)은 후입선출(Last In First Out; LIFO)의 순서로 데이터를 삽입, 삭제하는 자료구조이다.

• First In Last Out; FILO 로 쓰이기도 하지만 LIFO를 더 많이 씀

 

 

Overflow & Underflow

스택에 데이터가 Full 했을 때 삽입을 요청하면 Overflow 발생

반대로 데이터가 Empty 일 때 삭제를 요청하면 Underflow 발생

 

Top

스택은 기다란 상자가 세워져있는 구조이기 때문에 데이터를 제일 아래(Bottom)부터 하나씩 쌓는다.

데이터의 삽입(push) 삭제(pop)은 제일 위를 뜻하는 Top에서만 이루어진다.

---

🦋 스택의 사용사례

• 함수 콜 스택
• 웹 브라우저 방문기록(뒤로가기)
• 실행 취소(undo)
• 역순 문자열 만들기
• 후위 표기법 (postfix) 계산
• Backtracking
• 인터럽트(interrupt) 처리

---

✍🏻 스택 ADT (추상 데이터 타입)

create()	스택 생성
push(data)	void 데이터 삽입
pop()	top에 있는 데이터 삭제하면서 return
peek()	top에 있는 데이터 삭제하지 않고 return
contains(data)	원하는 데이터가 있는지 확인 true, false return
isEmpty()	스택이 비어있는지 확인 true, false return
isFull()	스택이 가득 차있는지 확인 true, false return
size()	스택의 크기 반환 int return
clear()	void 스택 모든 원소 삭제
printStack()	void 스택의 모든 원소 출력

---

⚙️ 스택 기능 & 동작원리

삽입 (push)

1. 스택이 가득 차있는지 확인 isFull()
2. 가득 차있다면 isFull()이 true를 반환하고 Overflow 발생
3. 가득 차있지 않다면 isFull()이 false를 반환하고 top을 하나 증가시킨다.
4. 증가한 top위치에 데이터 삽입(push)

// 슈도 코드

public void push(T item) {
	if (isFull()) {
    	return Overflow;
    }
    
    top++;
    Stack(top, item);
}

 

 

삭제 (pop)

1. 스택이 비어있는지 확인 isEmpty()
2. isEmpty()가 true를 반환하면 삭제할 데이터가 없기 때문에 Underflow발생 후 종료
3. isEmpty()가 false를 반환하면 top에 있는 값 temp에 보관
4. top을 하나 감소시킨다.
5. temp에 보관되어있는 값 return

// 슈도 코드

public T pop() {
	if (isEmpty()) {
    	return Underflow;
    }
    
    T temp = Stack(top);
    top--;
    return temp;
}

---

⏱️ 스택의 시간복잡도

• 삽입(Insertion) O(1)
• 삭제(Deletion) O(1)
• 검색(Search) O(n)

삽입(push)이나 삭제(pop)는 top에서만 이뤄지기 때문에 한번만 수행하면 된다. O(1)

검색은 원하는 값을 찾을 때 까지 계속 수행해야되기 때문에 최대 O(n)의 시간복잡도를 갖는다.