[ Data Structure ] Stack 스택

Stack

스택은 어떤 자료구조인가 !

선형 자료구조의 일종으로 나중에 들어온 원소가 먼저 나가는 LIFO(Last-In-First-Out) 특징을 가진다

가장 먼저 들어간 원소가 제일 아래 깔리고 그 위로 차곡차곡 쌓이기 때문에

호출시에는 가장 위에 있는 원소가 호출된다 !

 

스택을 프링글스 통이라고 생각하면 이해가 쉽다 ^ㅁ^

파이썬에서는 스택 자료구조를 따로 제공하지 않아 기본 클래스 list 를 통해 구현할 수 있다

---

장점

• 구조가 단순해서 구현이 쉽다
• 데이터의 삽입 / 삭제가 빠르다

단점 ( 일반적인 스택 구현시 )

• 데이터 최대 갯수를 미리 정해야한다 파이썬의 경우 재귀함수는 1000번까지만 호출이 가능하다
• 저장 공간의 낭비가 발생할 수 있다 미리 최대 갯구 만큼 저장 공간을 확보해야한다

---

stack 구현

stack 초기화

# 빈 스택 초기화
stack = []

 

stack 원소 추가 push

# append 메소드를 이용해 리스트의 가장 마지막에 4라는 원소 추가
stack = [1,2,3]
stack.append(4)

stack 원소 제거 pop

# pop 메소드를 이용하여 마지막 원소 제거 / pop 메소드에 의해 제거한 원소를 리턴받을 수 있다
stack = [1,2,3]
top = stack.pop()

 

stack 최상단 원소 확인 top

# stack 의 top / stack 의 최상단에 존재하는 원소 확인 예시의 경우 3
stack = [1,2,3]
top = stack[-1]

 

이외에도 isEmpty() 메소드는 스택이 비어있을 경우 True 를 리턴한다

---

스택의 활용

• 재귀 알고리즘 ( 함수를 호출하는 경우 임시 데이터를 스택에 넣어준다 )
• 웹 브라우저 방문기록 ( 뒤로 가기 )
• 실행 취소(undo)
• 역순 문자열 만들기
• 수식의 괄호 검사
• 후위 표기법 계산

---

참고

https://github.com/WeareSoft/tech-interview/blob/master/contents/datastructure.md#stack

GitHub - WeareSoft/tech-interview: 🙍 tech interview