SMALL
스택(Stack)
마치 접시를 차곡차곡 쌓았다가 맨 위의 접시부터 다시 꺼내어 사용하는 것처럼, 추가된 데이터 원소들을 끄집어내면 마지막에 넣었던 것부터 넣은 순서의 역순으로 꺼내지는 자료구조를 스택(stack)이라고 한다.
- 스택은 후입선출(LIFO; Last-In First-Out)자료구조
그러면 이러한 스택은 어디에 쓰일까??
컴퓨터 내부에서 프로그램이 실행할 때 함수 호출이 일어나고 함수들이 리턴하면 마지막 호출된 곳으로 동작을 구현하는 데에도 스택이 이용되고, 이러한 일은 컴퓨터의 동작에 핵심적인 것이기 때문에 컴퓨터 하드웨어(프로세서)는 어떤 방식으로든 스택을 내부적으로 관리하는 기능을 갖고 있습니다. 쉽게 이야기하면
재귀함수가 줄줄이 호출되었다가 리턴하는 모습을 생각하면 편합니다.
- 스택의 응용 - 수식의 후위 표기법(Postfix Notation)
- 들어있는 연산자가 push할 연산자 보다 낮으면 -> push
- 들어있는 연산자가 push할 연산자 보다 높거나 같으면 -> pop -> push
- 닫는 괄호 만나면 -> 여는 괄호 만날 때까지 pop
- 수식 끝이면 -> 연산자 모두 pop
본 문서는 프로그래머스 어서와! 자료구조와 알고리즘 강의를 수강하고 정리했습니다.
'알고리즘 단련장 > 자료구조와 알고리즘 강의' 카테고리의 다른 글
| 트리(Tree) (0) | 2022.09.02 |
|---|---|
| 큐(Queue) (1) | 2022.09.02 |
| 양방향 연결 리스트(Doubly Linked Lists) (0) | 2022.09.02 |
| 연결리스트(Linked Lists) (0) | 2022.09.02 |
| 알고리즘의 복잡도(Complexity of Algorithms) (0) | 2022.09.02 |