스택(Stack), 큐(Queue), 덱 (Deque)

스택(Stack)

LIFO (Last In First Out) : 마지막에 들어간 것이 첫번째로 나오는 구조 Stack에 데이터를 넣고 뺄 때 항상 top에 있는 것이 먼저 나옴

자료가 없을 때 pop -> stack underflow, 크기 이상의 자료를 push -> stack overflow

 

데이터의 삽입과 삭제가 빠르며 (O(1)), 괄호 검사, 역순 문자열 만들기, 후위 표기법으로의 변환 문제에 사용한다.

 

 

큐(Queue)

FIFO(First In First Out) : 맨 처음 들어간 것이 첫번째로 나오는 구조

선형 큐의 경우 Front와 Back을 둘 다 이동하면서 삽입, 삭제를 할 경우 배열의 끝에 저장되어 있는 상황이 되면 Back을 더 이상 이동시킬 수 없어서 overflow가 발생한다

 

FIFO 구조를 가지고 있기 때문에 데이터를 입력된 순서대로 처리해야 할 경우 사용할 수 있다.

BFS (너비 우선 탐색)을 구현할 때 사용한다.

BFS, 대기열 문제, 프로세스 관리 문제에 사용한다.

 

덱(Deque)

Double Ended Queue 의 준말로 큐를 구현했는데 양쪽에서 출력할 수 있어야 할 경우, 스택을 구현했는데 양쪽에서 입력하고 싶을 경우에 덱을 사용한다고 한다. (주로 스케줄링에 사용)

front 와 end 에서 삭제와 삽입 모두 가능하다.

크기가 가변적이고, index로 임의 원소 접근이 가능하며, 새로운 원소를 삽입할 때, 새로운 단위의 메모리 블록을 할당하여 삽입(메모리 재할당하고 복사X)

 

 

 

Baekjoon 10828, 10845, 10866 차례로 스택 큐 덱 기본 개념 문제이다.