스택 (stack)
- FILO(first in - last out)
- LIFO (last in - first out)
- 성능
- Push : O(1)
- Pop : O(1)
- stack 자체는 push(insert), pop(delete) 기능만 제공하고 search는 따로 없다.
- 차례대로 들어왔다가 역순으로 나가는 것을 이용해 어떤 목적을 달성할 수 있는 자료구조이다.
- stack을 배열 또는 연결리스트 혹은 그 외의 것을 이용하여 구현할 수 있다.
stack 자체는 정의이기 때문에 다양한 자료구조를 통해 구현 가능하다!
추가자료 주소 : www.programiz.com/dsa/stack
Stack Data Structure
A stack is a useful data structure in programming. It is just like a pile of plates kept on top of each other. Stack representation similar to a pile of plate Think about the things you can do with such a pile of plates Put a new plate on top Remove the to
www.programiz.com
큐 (queue)
- FIFO (first in - first out)
- LILO (last in - last out)
- 성능
- insert : O(1)
- delete : O(1)
- 차례대로 들어왔다 차례대로 나가는 것을 이용해 어떤 목적을 달성할 수 있는 자료구조이다.
추가자료 구조 : www.programiz.com/dsa/queue
Queue Data Structure
A queue is a useful data structure in programming. It is similar to the ticket queue outside a cinema hall, where the first person entering the queue is the first person who gets the ticket. Queue follows the First In First Out(FIFO) rule - the item that g
www.programiz.com
stack과 queue를 통해 할 수 있는 것?
- 미로찾기
- BFS 구현 (breadth first search)
- queue를 이용하여 구현할 수 있다.
- 내가 현재 있는 위치에서 이동할 수 있는 위치를 queue에 모두 넣고 꺼내는 식으로 풀이 가능
- DFS 구현 (depth first search)
- stack을 이용하여 구현할 수 있다.
- 내가 현재 있는 위치에서 이동할 수 있는 위치를 stack에 모두 넣고 꺼내는 식으로 풀이 가능
- BFS 구현 (breadth first search)
- 유효한 괄호
'다전공_컴퓨터공학 > 자료구조, 알고리즘' 카테고리의 다른 글
| [자료구조] 우선순위 큐 (priority queue) (0) | 2020.12.20 |
|---|---|
| [자료구조] 데크 (double ended queue) (0) | 2020.12.20 |
| [자료구조] 연결 리스트 (linked list) (0) | 2020.11.18 |
| [자료구조] 배열 (array) (0) | 2020.11.13 |
| [자료구조] 파이썬 리스트, 딕셔너리 (0) | 2020.11.02 |