스택, 큐, 덱

※ ios_base::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

 

 

1. 스택(Stack)

LIFO(Last in First out) : 나중에 들어간게 먼저 나옴

: push(), pop(), top(), size(), empty()

#include<stack>

//pop,top의 경우 empty여부 확인하기
stack<int> s;

if(s.empty()) cout<< "-1\n"
else{	
	cout<< s.top() <<'\n';
    s.pop();
 }

 

2. 큐(queue)

FIFO(First iin First out) : 먼저들어간게 먼저 나옴

back에 enqueue, front에서 dequeue

: push(), pop(), front(), back(), size(), empty()

#include<queue>

pop,front,back의 경우 empty여부 확인하기

 

3. 덱

: 양쪽 끝에서 삽입과 삭제가 가능한 구조 (양방향 큐)

: push_front(), push_back(), pop_front(), pop_back(), front(), back(), empty(), size()

#include<deque>

 

4. 우선순위 큐

:우선순위가 높은 원소를 삭제하는 자료구조

ex) 최대힙

#include<queue>

priority_queue<int> q;

 

 

5. 시간복잡도

1) 스택 push,pop의 시간복잡도: O(1)

2) 큐 push,pop의 시간복잡도: O(1)

3) 덱 push_front,push_back,pop_front,pop_back의 시간복잡도: O(1)

4) 우선순위 큐 push,pop,top의 시간복잡도: push,pop->O(logN), top->O(1)