무냐의 개발일지
[Coursera] Data Structure _Week1 / Stacks & Queues 본문
1. Stacks (LIFO)
쌓여있는 형태 (책을 쌓아놓은 형태)
나중에 들어간게 먼저 나온다
Abstract data type
- Push (Key) : adds key to collection
- Key Top() : returns most recently-added key
- Key Pop() : removes and returns most recently-added key
- Boolean Empty() : are there any elements?
stack은 이 balance를 track 하기 좋은 방법이다
이용 : compiler, 많은 알고리즘에 사용된다
모든 짝이 맞을 때 pop하면서 사라지는 코드
Push(a) - Push(b) - Top() : b - Push(c) - Pop() : c .... 꽉 찼을 때 Push 하면 -> Error , Empty() : False
| Stack Implementation with Linked List
Push(a) 이후에 Push(b)하면 b가 더 앞으로 온다... 이런 식으로 Push(d), Push(e) 하면 앞으로 쌓임.
Pop을 할 때도 앞에것부터 사라짐
- Liked list : fixed amount of overhead를 가지고 있다. (화살표의 데이터 공간도 필요하니까), don't have maximum size
-Array : have a maximum size
2. Queue (FIFO)
줄 서있는것과 같다. 먼저 쌓인것이 먼저 나간다.
- Enqueue(Key) : adds key to collection
- Key Dequeue() : removes and return least recently-added key
- Boolean Empty() : are there any elements ?
| Queue Implementation with Linked List
Enqueue(a) - Euqueue(b) 하면, a 뒤에 b가 온다
Dequeue() 하면 가장 먼저 온 a가 return되고 사라진다
다 끝내고 마지막에 Empty() 하면 True가 나온다. head = null
| Queue Implementation with Array
- write : 다음 euqueue 가 어디 일어나야 되는지 지정
- read : 다음 dequeue 가 어디서 일어나야 되는지 지정
Enqueue(a) - Enqueue(b) - Enqueue(c) 여기서 Dequeue하면, read index(0) 가 있는 a가 return & 삭제된다 - 또 Dequeue하면, read index가 있는 b자리가 return & remove 된다 - 다시 Enqueue(d) 하면 c뒤에 d가 입력되고, 끝까지 하면 write는 다시 맨 처음으로 지정된다
여기서 Enqueue(g)하면 read index 자리가 비어있음에도 Error 발생
왜냐면 그렇게 하는 순간, Read & Write index 가 동시에 2가 되기 때문
Therefore, we have a buffer of at least one element that can't be written to
계속 Dequeue를 해서 read = write index 되면, 이 때 Empty 라고 볼 수 있다 : Empty() -> True
| Summary
3. Tree
* 구조 : Parents (ancestor) - Child (descendant) tree
* 용어 :
Root : 맨 위에 있는 애 the top node in the tree
Siblings : nodes sharing the same parent
Leaf : node with no children
Interior node : non-leaf
Level : 1 + number of edges(선) between root and node - Root의 level = 1, 그 아래는 2 ...
Height : max depth of subtree node and farthest leaf - 가장 아래에 있는 노드의 깊이
Forest : collection of trees
| Binary Search Tree
아래 있는 가지들을 Child tree 라고 부른다
| Walking a Tree
깊이 먼저 vs 넓이 먼저
- Depth First
1. 왼쪽먼저 쭉 ~ 도는거다 (left child - node - right child)
2. Node - Left - Right (중심부터 돌고, 왼쪽 - 오른쪽)
3. 먼저 left - right 다 돌고서, node로 돌아온다
Q) If we have an expression tree and we want to evaluate that tree in order to compute the value of the expression, we want to evaluate the children before evaluating the arithmetic operator at an internal node. What traversal method does this mean we should use?
A)
-Breadth-first
Queue는 처리되기를 기다리고 있는거다 - print되면 output으로 들어간다
| Summary
| Quiz
Array는 특정 위치 address로 바로 접근이 가능하댔어
List는 중간에 넣을 때 한번의 연산만 필요하댔어 (반면, array는 여러번 필요하지. 앞뒤로 계속 밀리니까)
