[C++] 스택 / 큐

스택

LIFO

연산이 한 쪽에서만 이루어진다.

스택의 끝을 위(Top), 스택의 시작을 밑(Bottom)이라 한다.

큐

선입선출

삽입이 일어나는 쪽을 뒤(Rear), 삭제가 일어나는 쪽을 앞(Front)라고 한다.

 

큐 (Queue)

std::queue

입력과 출력이 한방향으로 이루어지는 구조

 

데크 (Double-ended Queue)

std::deque

입력과 출력이 양방향으로 이루어지는 구조

 

청크 리스트 (Chunk List)

선형 리스트 + 연결 리스트

데이터 접근이 용이한 선형 리스트와, 데이터 삽입/삭제가 용이한 연결리스트의 장점을 활용

고정된 길이의 연속된 메모리를 연결해 놓은 형태로

청크의 크기가 크지 않아 데이터의 삽입/삭제가 용이하고, 청크 단위로 접근하여 접근에도 용이하다.

 

Stack과 Queue는 기본 컨테이너로 Deque를 사용한다.

 

순차 자료구조로 구현한 큐 (원형 큐)

 

 

연결 자료구조로 구현한 큐

이전 원소를 알 필요가 없기 때문에 단일 연결 리스트로 구현하는 것이 효율적

다만 삭제를 위해 마지막 원소를 가리키는 데이터가 필요하다.