[D-26] 자료구조 - 스택 & 큐

✅ 스택과 큐

스택(stack) : 후입선출(LIFO, Last In First Out) = 단방향, push(top) / peek(top) / pop(top)
큐(queue) : 선입선출(FIFO, First In First Out) = 양방향, add(rear) / peek(front) / poll(front) 

자료구조 - 스택과 큐

---

📍 스택(stack)

삽입과 삭제 연산이 후입선출(LIFO, Last In First Out)로 이뤄지는 자료구조를 말한다.
후입선출은 삽입과 삭제가 한쪽에서만 일어나는 특징이 있다.

stack - LIFO

✅  스택 용어

위치
top : 삽입과 삭제가 일어나는 위치를 뜻한다.

 

연산
push : top 위치에 새로운 데이터를 삽입하는 연산이다.
pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다.
peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산이다.

 

 

✅  스택 사용처

깊이 우선 탐색(DFS, Depth First Search)
백트래킹
후입선출은 재귀 함수 알고리즘 원리와 일맥상통한다.

 

---

📍 큐(queue)

삽입과 삭제 연산이 선입선출(FIFO, First In First Out)로 이뤄지는 자료구조를 말한다.
선입선출은 삽입과 삭제가 양쪽에서 일어나는 특징이 있다.
먼저 들어온 데이터가 먼저 나간다.

queue - FIFO

✅  큐 용어

위치
rear : 큐에서 가장 끝 데이터를 가리키는 영역이다. / 삽입이 일어나는 위치를 뜻한다.
front : 큐에서 가장 앞의 데이터를 가리키는 영역이다. / 삭제가 일어아는 위치를 뜻한다.

 

연산
add : rear 부분에 새로운 데이터를 삽입하는 연산이다.
poll : front 부분에 현재 있는 데이터를 삭제하고 확인하는 연산이다.
peek : 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산이다.

 

✅  큐 사용처

너비 우선 탐색(BFS, Breadth First Search)

 

---

📍우선순위 큐(priority queue)

값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조를 말한다.
큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다.
일반적으로 힙(heap, tree 종류 중 하나)을 이용해 구현한다.