Stack & Queue 개념 정리

Stack 이란? 

: Push와 pop 기능을 가진 one-ended linear data (LIFO)

 

Complexity Analysis

Pushing	O(1)
Popping	O(1)
Peeking	O(1)
Searching	O(n)
Size	O(1)

 

벽돌을 길게 쌓아서 벽돌을 넣고(push) 벽돌을 빼는(pop)을 상상하면 훨씬 이해가 잘 되는 것 같아요

 

위키백과

 

---

 

Queue 이란? 

: Enqueue 와 Dequeue  주요 기능을 가진 선형 데이터 구조 (FIFO)

 

https://www.youtube.com/watch?v=RBSGKlAvoiM&t=3514s

 

식당 줄 서는걸 생각해보면 queue와 상당히 비슷한 걸 알 수 있습니다

줄을 서고(Enqueue) 줄에서 빠지고(Dequeue) !

 

Complexity Analysis

Enqueue	O(1)
Dequeue	O(1)
Peeking	O(1)
Contains	O(n)
Removal	O(n)
Is Empty	O(1)

 

---

 

Priority Queue 이란? 

 

: 일반 Queue와 유사하지만, 우선순위를 기반으로 요소를 제거한다는 차이점이 있습니다

(우선순위 배정을 위해 Queue에 들어가는 데이터는 숫자의 대소처럼 Comparable Data여야 함)

 

Poll()  -> remove the one with highest priority (가장 우선순위가 큰 데이터 먼저 빼기)

Add(element) -> 주어진 요소의 값을 추가하기

 

 

그렇다면 컴퓨터는 어떻게 우선순위를 판별할까요??

 

--> Heap을 통해서!!

 

**단, 여기서 주의할 점은 PQ는 Abstract Data Type(ADT)로 heap외의 다른 방법으로도 PQ를 구현할 수

있습니다. 그러나, heap을 사용하는 주요한 이유는 time complexity를 고려했을 때 Heap이 효율적이기

때문입니다

 

 

---

 

Heap 이란? 

: Tree 형태의 데이터 구조로 부모/자식 노드간의 관계에 따라 Max/Min heap으로 구분됩니다

 

Complexity Analysis (Binary Heap기반의 Priority Queue)

Binary Heap Construction	O(n)
Polling	O(log(n))
Peeking	O(1)
Adding	O(log(n))

 

Heap의 종류 

: Binary Heap, Fibonacci Heap, Binomial Heap, Pairing Heap

 

 

 

↓↓↓  Heap에 대한 자세한 개념 및 활용 방법은 아래 링크를 참고해주세요  ↓↓↓

 

2022.09.21 - [Python] - Heapq 알고리즘 개념 및 활용방법 정리

Heapq 알고리즘 개념 및 활용방법 정리

 

 

자료 출처:

https://www.youtube.com/watch?v=RBSGKlAvoiM&t=3514s