#3 Stack, Queue, Deque

[Stack, Queue, Deque] 

특정 위치에서만 원소를 넣고 뺄 수 있는 제한된 '선형 자료구조(일자형태)'

c++ STL에 존재 

---

 

Stack

한 쪽 끝에서만 원소를 넣고 뺄 수 있는 자료구조입니다.

LIFO(Last In First Out) 마지막에 들어온게 가장 먼저 나갑니다.

push / pop (시간 복잡도 : O(1))

컨테이너 어댑터(Container Adaptor)의 일종입니다.

#include<stack> 라이브러리에 존재 합니다.

 

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

스택에 기본 탬플릿 입니다.

deque에서 파생되었다는 것을 알 수 있습니다.

 

push(k) : stack에 k를 추가

pop() : stack에서 제일 마지막에 넣은 원소를 제거

top() : stack에서 제일 마지막에 넣은 원소를 반환(제거 x )

size() : stack에 들어씨는 원소의 개수 반환

empty() : stack이 비어있으면 true, 아니면 false 반환

 

Ex) 웹 브라우저 뒤로가기 / 실행취소(Ctrl + z)

---

Queue

한 쪽에서는 원소를 넣고 다른 쪽에서는 뺄 수 만있는 자료구조

FIFO(First In First Out) 먼저 넣은 원소가 먼저 나갑니다.

push / pop (시간 복잡도 : O(1))

컨테이너 어댑터(Container Adaptor)의 일종

#include<queue> 라이브러리에 존재합니다.

 

template<class T, class Container = deque<T>> class queue;

큐에 기본 템블릿입니다.

deque에서 파생되었다는 것을 알 수 있습니다.

push(k) : queue에 k를 추가

pop() : queue에서 제일 먼저 넣은 원소를 제거

front() : queue의 원소 중 제일 먼저 넣은 원소를 반환(제거 x)

back() : queue의 원소 중 제일 마지막에 넣은 원소를 반환(제거 x)

size() : queue에 들어있는 원소의 개수 반환

empty() : queuerk 비어있으면 true, 아니면 false 반환

 

Ex) 프린트 작업 / 놀이공원 줄 / 은행 업무

---

Deque

스택 + 큐의 형태

양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조

순차 컨테이너(Sequence Container)의 일종(백터와 비슷)

#include<deque> 라이브러리에 존재합니다.

 

template<class T, class Allocator = std::allocator<T>> class deque;

덱의 기본 탬플릿입니다.

 

push_front(k) / push_back(k) : deque의 앞/뒤에 k를 추가(시간 복잡도 : O(1))

pop_front() / pop_back() : deque의 제일 앞/뒤의 원소 제거(시간 복잡도 : O(1))

front() / back() : deque의 원소 중 제일 앞/뒤의 원소를 반환

size() : deque에 들어있는 원소의 개수 반환

empty() : deque가 비어있으면 true, 아니면 false반환

vector에서 사용되는 기능들 (Random Access, begin/end, clear, insert 등)

백터에서 사용가능한 함수들도 대부분 Deque에서 사용가능