스택(Stack)

LIFO: Last-In-First-Out
가장 최근에 들어온 데이터가 먼저 나가는 자료구조

c++ stack containercontainer

#include <stack>

empty()

스택이 비어있는지 확인할 있다

size()

스택의 사이즈를 반환해준다

top()

스택의 맨 위에 있는 인자를 반환한다

push(데이터)

데이터를 삽입한다

pop()

스택의 맨 위에 있는 인자를 삭제한다
반환값이 없다!

큐(Queue)

FIFO: First-In-First-Out
먼저 들어온 데이터가 먼저 나가는 자료구조이다

enqueue

데이터를 뒤에 삽입할 수 있다

dequeue

앞의 데이터를 삭제할 수 있다

c++ queue container

#include <queue>

empty()

큐가 비어있는지 확인할 있다

size()

큐의 사이즈를 반환해준다

front()

큐의 첫 번째 원소에 접근해서 반환한다

back()

큐의 마지막 원소에 접근해서 반환한다

push(데이터)

데이터를 뒤에 삽입한다

pop()

큐의 맨 앞에 있는 인자를 삭제한다
반환값이 없다!

선형 큐 (Linear queue)

단점

삽입과 삭제가 반복되면 배열의 앞이 비어있게 된다 데이터를 계속 삽입하기 위해서는 앞의 비어있는 공간으로 뒤에 있는 요소들을 이동시켜야하는 비효율적인 방법을 사용하게 된다

이를 해결하기 위해서 등장한 것이 원형 큐이다!

원형 큐

덱(deque)

deque=double-ended queue
front에서도 삽입과 삭제가 가능하고 rear에서도 삽입과 삭제가 가능한 큐

c++ deque container

#include <deque>

empty()

덱이 비어있는지 확인할 있다

size()

덱의 사이즈를 반환해준다

front()

덱의 첫번째 원소에 접근해서 반환한다

push_front(데이터)

덱의 첫 번째 원소 앞에 데이터를 삽입한다

pop_front()

덱의 첫 번째 원소를 삭제한다

back()

덱의 마지막 원소에 접근해서 반환한다

push_back(데이터)

덱의 마지막 원소 앞에 데이터를 삽입한다

pop_back()

덱의 마지막 원소를 삭제한다
반환값이 없다!