Queue
-
FIFO(First in First out; 선입 선출)의 특징을 가지는 자료구조
- 먼저 들어간 데이터가 먼저 나옴
-
좌우가 뚫려있는 파이프와 같이 표현
-
좌측으로 넣고, 우측으로 뺀다(한쪽 방향으로 넣고, 다른쪽으로 뺀다). 그럼 넣는 순서는 노랑->보라->파랑이 될 것 이고, 빼는 순서도 마찬가지로 노랑->보라->파랑
-
단순히 한쪽에서 넣고, 한쪽에서 뺄수만 있도록 제한 해둔것
-
모든 함수의 시간복잡도는 O(1)
함수
-
enqueue (자바의 경우 add): 한쪽 방향으로 데이터를 넣음 -
dequeue (자바의 경우 poll): 다른쪽 방향으로 데이터를 뺌- 여기서 dequeue는 덱(deque)과 다름
- deque는 double-ended queue를 줄인거고, dequeue는 de-(접두어) + queue
-
peek: dequeue로 빠질 데이터를, 큐에서 제거하진 않고 데이터만 확인 -
isEmpty: 큐가 비었는지 -
size: 큐에 들어있는 데이터 갯수 -
자바의 경우
Queue<Integer> q = new LinkedList<>();와 같이 선언해서 사용
사용처
- 데이터가 입력된 시간 순서대로 처리되어야 하는 경우 사용
- 스케쥴링
- BFS나 캐시를 구현할 때 사용
Stack
-
LIFO(Last in First out; 후입 선출)의 특징을 가지는 자료구조
-
나중에 들어간 데이터가 먼저 나옴
-
쌓아 올리는 자료구조
-
같은 구조와 크기의 자료를 정해진 방향으로 쌓을 수 있고, 한 방향으로만 접근 가능
-
상자에 뚜껑 열고 딱 맞는 책을 차곡차곡 쌓는다고 생각하면 이해하기 쉬움
-
마지막에 넣은 책이 가장 위에 있으니 가장 먼저 꺼내야 그 아래 책을 꺼낼 수 있음
-
중간의 데이터를 볼 수도 없고 수정 불가
-
스택에서 가장 위에 있는 데이터는 'top'
- push, pop을 하면서 삽입과 삭제 가능
-
모든 함수의 시간복잡도는 O(1)
함수
-
push: 스택에 데이터를 넣음 -
pop: 스택에서 데이터를 뺌 -
peek: 스택에서 데이터를 빼진 않고, 가장 위에 있는 데이터만 확인 -
isEmpty -
size -
자바의 경우
Stack<Integer> stk = new Stack<>();와 같이 선언해서 사용
사용처
-
ctrl+z 로 현재 작업중인걸 되돌리는 기능
- 작업을 하나씩 진행하고 (push), ctrl+z를 누를 때 마다 가장 마지막에 작업한게 하나씩 취소되어야 함(pop)
-
DFS나 재귀에서 사용
Deque
-
Double-ended Queue라는 의미로, 양쪽으로 넣고 뺄 수 있는 큐
-
당연히 양쪽으로 넣고 뺄 수 있는 스택으로도 쓸 수 있고, 한쪽은 스택 한쪽은 큐로 사용하는 것도 가능
- 좀 더 유연한 스택, 큐
-
리스트와 다르게 중간의 데이터를 건드릴 수 없고, 양끝단만 건드릴 수 있음
-
큐와 동일하지만 양옆에서 넣고 뺄 수 있다는 차이점 존재
-
모든 함수의 시간 복잡도는 O(1)
함수
-
addFirst(): 덱의 한쪽에 데이터 추가 -
pollFirst(): 덱의 한쪽에서 데이터 빼기 -
peekFirst(): 덱의 한쪽에서 데이터를 빼진 않고 확인만 하기 -
addLast(): 덱의 다른쪽에 데이터 추가 -
pollLast(): 덱의 다른쪽에서 데이터 빼기 -
peekLast(): 덱의 다른쪽에서 데이터를 빼진 않고 확인만 하기 -
isEmpty() -
size() -
자바의 경우
Deque<Integer> dq = new LinkedList<>();와 같이 선언해서 사용
사용처
-
일반적으로 메모리 제한이 있기 때문에 ctrl+z에는 횟수제한이 존재
-
하지만 스택의 예시에서 갯수를 제한할 수 있을까?
- 추가/삭제만 가능하기 때문에 설정해둔 갯수를 넘어가도 최근에 한 작업만 제거할 수 있음
-
addFirst와pollFirst로 스택처럼 사용하다가,size()를 확인해서 일정 수치가 넘어가면pollLast로 빼는 식으로 갯수를 제한할 수 있게 됨
