[면접질문] 스택, 큐, 덱(Stack, Queue, deque)개념 정리

스택, 큐, 덱(Stack, Queue, Deque)의 특징

스택(stack) : 자료의 입력과 출력을 한 곳(방향)으로 제한한 자료구조

LIFO(Last In First Out)구조

push(), pop()

함수의 콜스택에 쓰이고 문자열을 역순으로 출력할 때, 연산자 후위표기법등에 쓰인다.

 

큐(queue) : 자료의 입력과 출력을 한 쪽 끝(front, rear)으로 제한한 자료구조

FIFO(First In First Out)구조

put(), get()

컴퓨터 버퍼에서 주로 사용

마구 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킨다.

일반적인큐(빈메모리가 남아있어도 꽉 차있는것으로 판단 가능) > 원형큐(큐의 크기가 제한됨) > 링크드리스트큐(제한이 없고 삽입, 삭제가 간편)

 

덱(deque) : 자료의 입력과 출력을 양 쪽 끝에서 가능하게 하는 자료구조

스크롤(scroll) : 입력이 한쪽 끝으로만 가능하도록 제한한 덱

셸프(shelf) : 출력이 한쪽 끝으로만 가능하도록 제한한 덱