[STL] Stack, Queue

2025.0309

​

1. Adaptors

: sequence container를 가지고

각각의 자료구조(stack, queue, priorty_queue )에 맞는 인터페이스만 제공 해주는 컨테이너

=> 그래서 제한 사항이 많음.

​

iterator 제공X

중간원소 접근 X

​

* stack : top only : 보통 vector나 deque로 간단하게 이용 가능함.

* queue : front, back only : BFS에서 주로 사용 : 배열로도 구현 가능

=> 성능에 민감하면 stack이나 queue는 굳이..?

 

*priority_queue: top only

: 느리긴 하지만 직접 구현하려면 귀찮기는 해서 자주 사용하게 됨.

- 빈번한 삽입, 삭제 속에서 우선순위 구하는 경우에 사용함

- set,map에 비해 활용성 떨어짐.

- 정렬기준 가장 오른쪽 원소가 top으로 올라옴

defalt : max pq

​

2. stack

#include <stack>

Last Input, First Out

항상 top만 접근 가능함

template<
       class T,
       class Container = std::deque<T>
> class stack;

​	​	​	top()	​	​
​	​	​	​	​	​
​	​	​	​	top()	​
push(x)	​	​	​	x	​
​	​	​	top()	​	​
pop()	​	​	​	x	​

stack<T> st
st = {} //clear - clear가 따로 없어서 이렇게 클리어함.

void st.push(T)
void st.pop()
T    st.top()
int  st.size()
bool st.empty()

 

 

3. queue

#include <queue>

First Input First Out

항상 front, back만 접근 가능.

 

-> 선입

​

-> 선출

template<
       class T,
       class Container = std::deque<T>
> class stack;

 

​	front()	​	back()	​	​
​	​	​	​	​	​
​	front()	​	​	back()	​
push(x)	​	​	​	x	​
​	​	front()	​	back()	​
pop()	​	​	​	x	​

queue<T> q
q = {} //clear - clear가 따로 없어서 이렇게 클리어함.

void q.push(T)
void q.pop()
T    q.front()
T    q.back()
int  q.size()
bool q.empty()